Polynomial-Time Many-One Reductions

What a Many-One Reduction Does

A reduction translates instances of one decision problem into instances of another. The translation is useful when it can be computed efficiently and when it preserves the answer exactly: an input is a yes-instance of the first problem if and only if its translated input is a yes-instance of the second. Thus, solving the second problem would also let us solve the first.

We treat a decision problem as a language: a set of finite strings over $\{0,1\}$, using fixed encodings for the instances. A string in the language is a yes-instance; a string outside it is a no-instance. For graph problems, an encoding records the graph and any additional data, such as two specified vertices. Invalid encodings are no-instances. The encoding conventions are fixed, so an algorithm's running time is measured in the length of the input string.

Definition: Let $A,B\subseteq\{0,1\}^*$ be decision problems. A polynomial-time many-one reduction from $A$ to $B$, written $A\leq_p B$, is a total function $f:\{0,1\}^*\to\{0,1\}^*$ that is computable in polynomial time and satisfies, for every string $x$, $$ x\in A \quad\Longleftrightarrow\quad f(x)\in B. $$ The function $f$ is the reduction. The equivalence is required for every input, not just for yes-instances.

“Many-one” means that one input is mapped to one input; the answer to the original instance is determined by the answer to that single translated instance. A reduction need not translate solutions or certificates, and it does not require the two problems to have the same kinds of instances. Its essential condition is the yes/no equivalence.

A Graph Construction: Reachability to Strong Connectivity

Consider the directed $s$-$t$ reachability problem: given a finite directed graph $D=(V,A)$ and distinct specified vertices $s,t\in V$, decide whether there is a directed path from $s$ to $t$. A directed graph is strongly connected if, for every ordered pair of vertices $u,v$, there is a directed path from $u$ to $v$. We construct a reduction from directed $s$-$t$ reachability to the decision problem of strong connectivity.

Construction: Keep the vertex set $V$ and all the original arcs of $D$. Add an arc $v\to s$ for every $v\ne s$, and add an arc $t\to v$ for every $v\ne t$. If an added arc is already present, keep just one copy. Call the resulting directed graph $H$.

The construction has a useful shape: any vertex can get to $s$, and $t$ can get to any vertex. The only possible missing link is a directed route from $s$ to $t$. That link is exactly the original reachability question.

Worked Example: A Yes-Instance of Reachability

Let $V=\{1,2,3\}$, let $A=\{1\to2,2\to3\}$, and take $s=1,t=3$. The source instance is yes because $1\to2\to3$ is a directed path.

Add $2\to1$ and $3\to1$, since these are the arcs $v\to s$ for $v=2,3$. Add $3\to1$ and $3\to2$, since these are the arcs $t\to v$ for $v=1,2$. The arc $3\to1$ was added twice, so it appears only once. The output has vertex set $\{1,2,3\}$ and arc set $\{1\to2,2\to3,2\to1,3\to1,3\to2\}$.

To check strong connectivity, vertex $1$ reaches $2$ by $1\to2$ and $3$ by $1\to2\to3$. Vertex $2$ reaches $1$ by $2\to1$, and reaches $3$ by $2\to3$. Vertex $3$ reaches $1$ by $3\to1$ and $2$ by $3\to2$. Thus every vertex reaches every other vertex.

Check: the output is a yes-instance of strong connectivity, matching the yes-answer for reachability. The added arcs provide the routes into $1$ and out of $3$; the original route $1\to2\to3$ completes the connection.

Worked Example: A No-Instance of Reachability

Let $V=\{1,2,3\}$, let $A=\{1\to2\}$, and again take $s=1,t=3$. There is no directed path from $1$ to $3$: the only arc leaving $1$ goes to $2$, and there is no original arc leaving $2$.

Add $2\to1$ and $3\to1$ for the vertices different from $s$. Add $3\to1$ and $3\to2$ for the vertices different from $t$, retaining only one copy of $3\to1$. The output arc set is $\{1\to2,2\to1,3\to1,3\to2\}$.

This output is not strongly connected: vertex $1$ cannot reach vertex $3$. In fact, the only arc leaving $1$ is $1\to2$, and the only arc leaving $2$ is $2\to1$, so a path starting at $1$ cannot reach $3$.

Check: the output is a no-instance of strong connectivity, matching the no-answer for reachability. In particular, the added arcs do not create a new route from $s$ to $t$.

Why the Construction Preserves the Answer

Theorem: The construction above is a polynomial-time many-one reduction from directed $s$-$t$ reachability to strong connectivity.

Proof. Assume the input is a valid instance with $s\ne t$, and let $H$ be the constructed graph. First suppose there is a directed path from $s$ to $t$ in $D$. For any $x,y\in V$, if $x\ne s$, the added arc $x\to s$ takes $x$ to $s$; if $x=s$, no initial arc is needed. Follow the given path from $s$ to $t$. If $y\ne t$, the added arc $t\to y$ then reaches $y$; if $y=t$, no final arc is needed. Hence every $x$ reaches every $y$, and $H$ is strongly connected.

Conversely, suppose $H$ is strongly connected. Then $H$ has a directed path from $s$ to $t$. The added arcs entering $s$ have head $s$, and the added arcs leaving $t$ have tail $t$. Since $s\ne t$, none of these added arcs enters $t$ from a different vertex. Therefore the first time this path reaches $t$, its final arc must be an original arc of $D$. Before that first arrival, the path cannot use an added arc leaving $t$, because it has not yet reached $t$; and an added arc entering $s$ only returns to $s$. Removing any such returns to $s$ leaves a directed route from $s$ to $t$ using original arcs. Thus $D$ has an $s$-to-$t$ path.

The construction adds at most $2|V|$ arcs. Copying the input and listing these arcs takes time polynomial in the input length. For an invalid encoding, define the reduction to output a fixed no-instance of strong connectivity, such as the two-vertex directed graph with no arcs. Parsing the input and making this check takes polynomial time. Therefore the map is defined on all strings, is computable in polynomial time, and preserves yes- and no-instances. $\square$

This proof illustrates why both directions matter. Showing that a source yes-instance produces a target yes-instance is not enough: a reduction must also prevent source no-instances from becoming target yes-instances.

Composition and Transitivity

Theorem (Transitivity): If $A\leq_p B$ and $B\leq_p C$, then $A\leq_p C$.

Proof. Let $f$ be a polynomial-time reduction from $A$ to $B$, and let $g$ be a polynomial-time reduction from $B$ to $C$. Define $h(x)=g(f(x))$. For every string $x$, the reduction properties give $$ x\in A \quad\Longleftrightarrow\quad f(x)\in B \quad\Longleftrightarrow\quad g(f(x))\in C. $$ Thus $h$ preserves yes- and no-instances. It remains to check its running time. Suppose $f$ takes at most $p(n)$ steps on inputs of length $n$, and $g$ takes at most $q(m)$ steps on inputs of length $m$, for polynomials $p,q$. A computation cannot output more symbols than the number of steps it takes, so $|f(x)|\le p(|x|)$. Computing $f(x)$ and then $g(f(x))$ takes at most $p(n)+q(p(n))$ steps, which is polynomial in $n=|x|$. Hence $h$ is a polynomial-time reduction from $A$ to $C$. $\square$

Transitivity lets us follow a chain of translations. If one problem reduces to a second, and the second reduces to a third, each original instance can be translated all the way to the third problem while keeping its answer unchanged. The proof also relies on polynomial output length: the second reduction is applied to $f(x)$, so its input length must be bounded by a polynomial in the original length.

Using the Direction of a Reduction

Proposition: If $A\leq_p B$ and $B$ has a polynomial-time decision algorithm, then $A$ has a polynomial-time decision algorithm.

Proof. On input $x$, compute $f(x)$, where $f$ is the reduction from $A$ to $B$, and run the polynomial-time algorithm for $B$ on $f(x)$. By the reduction equivalence, that algorithm answers yes exactly when $x\in A$. The computation of $f$ takes polynomial time, and $|f(x)|$ is polynomially bounded in $|x|$, so the time used by the algorithm for $B$ is also polynomial in $|x|$. The combined algorithm is therefore polynomial-time and decides $A$. $\square$

The direction is important: reducing $A$ to $B$ means that an efficient solver for $B$ gives an efficient solver for $A$. The reduction itself is not a claim that the two problems are equally difficult, and it does not prove that either problem lacks a polynomial-time algorithm.

Worked Example: Connectedness to Having a Spanning Tree

For a finite undirected graph with at least one vertex, consider the connectedness problem and the problem of deciding whether the graph has a spanning tree. A spanning tree is a subgraph that contains every vertex and is both connected and acyclic. Use the identity map: the output graph is the input graph itself. This map takes polynomial time.

To verify answer preservation, first suppose $G$ is connected. Among the connected subgraphs with vertex set $V(G)$, choose one with the fewest edges; such a subgraph exists because $G$ is finite. It cannot contain a cycle: if an edge on a cycle were removed, the rest of that cycle would still provide a route between the edge's endpoints, so the subgraph would remain connected with fewer edges. Thus this subgraph is a spanning tree.

Conversely, if $G$ has a spanning tree, then $G$ is connected: between every two vertices the tree contains a path, and that path is also in $G$. So the identity map sends a connected graph to a yes-instance of the spanning-tree problem and a disconnected graph to a no-instance.

For a concrete yes-instance, let $V=\{1,2,3,4\}$ and $E=\{12,23,31,34\}$. The graph is connected, and the edges $\{12,23,34\}$ form a spanning tree: they include all four vertices, connect them in the order $1,2,3,4$, and contain no cycle. For a no-instance, let $V=\{a,b,c\}$ and $E=\{ab\}$. Vertex $c$ has no incident edge, so the graph is disconnected and no subgraph on all three vertices can be connected.

Check: the identity transformation leaves both graphs unchanged. The first has a spanning tree and is connected; the second has no spanning tree and is disconnected. The two answers agree in each case, as required by the reduction.

Common Pitfall: Reversing or Skipping the Equivalence

A plausible-looking transformation is not a reduction unless it preserves the answer for every input. For example, simply outputting the original directed graph while forgetting the specified vertices does not reduce $s$-$t$ reachability to strong connectivity. Take $V=\{1,2\}$, $A=\{1\to2\}$, $s=1,t=2$. There is a path from $s$ to $t$, so the source answer is yes. But the unchanged graph is not strongly connected, since $2$ cannot reach $1$. The proposed map sends a yes-instance to a no-instance.

The correction is to use a construction that addresses both directions of travel and then prove the equivalence. In the earlier construction, the added arcs let every vertex reach $s$ and let $t$ reach every vertex. Strong connectivity then holds exactly when the original graph supplies the missing $s$-to-$t$ route. The proof, rather than the appearance of the output graph, is what verifies the reduction.

When checking a proposed many-one reduction, ask three questions:

Is the output a valid instance of the target problem for every input?
Is the map computable in time polynomial in the input length?
Have both implications been proved: source yes implies target yes, and target yes implies source yes?

Check Your Understanding

For each question, use the definition of a many-one reduction and state which direction of the answer-preservation condition is relevant.

In the reachability-to-strong-connectivity construction, why must $s$ and $t$ be distinct?
Explain why a polynomial-time reduction from $A$ to $B$, together with a polynomial-time algorithm for $B$, gives a polynomial-time algorithm for $A$.
Suppose $f$ preserves every yes-instance of $A$, but some no-instance of $A$ maps to a yes-instance of $B$. Why is $f$ not a many-one reduction?
State the function that composes reductions $f:A\to B$ and $g:B\to C$, and explain why its output length is polynomially bounded.
For the graph with $V=\{1,2,3\}$ and $E=\{12\}$, explain why the identity map preserves the no-answer for connectedness and having a spanning tree.