patternMajor
What are common techniques for reducing problems to each other?
Viewed 0 times
eachwhatarereducingotherforproblemscommontechniques
Problem
In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as some other problem $L_2$ by mapping instances from $L_2$ to solution-equivalent ones in $L_1$. Essentially, we show that any solver for $L_1$ can also solve $L_2$ if we allow it to use the reduction function as preprocessor.
I have performed my share of reductions over the years, and something keeps bugging me. While every new reduction requires a (more or less) creative construction, the task can feel repetitive. Is there a pool of canonical methods?
What are techniques, patterns and tricks one can regularly employ for constructing reduction functions?
This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!
I have performed my share of reductions over the years, and something keeps bugging me. While every new reduction requires a (more or less) creative construction, the task can feel repetitive. Is there a pool of canonical methods?
What are techniques, patterns and tricks one can regularly employ for constructing reduction functions?
This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!
Solution
The Special Case
Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity function. The intuition behind this is clear: the general case is at least as hard as the special case.
In "practice", we are given $L_2$ and are stuck with the problem of picking a good reduction partner $L_1$, i.e. finding a special case of $L_2$ that has proven to be $R$-hard.
Simple Example
Assume we want to show that KNAPSACK is NP-hard. Luckily, we know that SUBSET-SUM is NP-complete, and it is indeed a special case of KNAPSACK. The reduction
$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$
suffices; $(V,W,v,w)$ is the KNAPSACK instance that asks whether we can achieve at least value $v$ with item values in $V$ so that the corresponding weights from $W$ remain beneath $w$ in total. We don't need the weight restrictions for simulating SUBSET-SUM, so we just set them to tautological values.
Simple exercise problem
Consider the MAX-3SAT problem: given a propositional formula $\varphi$ and integer $k$, decide whether there is an interpretation of $\varphi$ that fulfills at least $k$ clauses. Show that it is NP-hard.
3SAT is a special case; $f(\varphi) = (\varphi, m)$ with $m$ the number of clauses in $\varphi$ suffices.
Example
Assume we are investigating the SUBSET-SUM problem and want to show that it is NP-hard.
We are lucky and know that the PARTITION problem is NP-complete. We confirm that it is indeed a special case of SUBSET-SUM and formulate
$\qquad \displaystyle f(A) = \begin{cases}
\left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\
\left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else}
\end{cases}$
where $A$ is the input set of PARTITION, and $(A,k)$ is an instance for SUBSET-SUM that asks after a subset of $A$ summing to $k$. Here, we have to take care of the case that there is no fitting $k$; in that case, we give an arbitrary infeasible instance.
Exercise Problem
Consider the problem LONGEST-PATH: given a directed graph $G$, nodes $s,t$ of $G$ and integer $k$, decide whether there is a simple path from $s$ to $t$ in $G$ of length at least $k$.
Show that LONGEST-PATH is NP-hard.
HAMILTON-CYCLE is a well-known NP-complete problem and a special case of LONGEST-PATH; $f(G) = (G,v,v,n)$ for arbitrary node $v$ in $G$ suffices.
Note in particular how reducing from HAMILTON-PATH requires more work.
Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity function. The intuition behind this is clear: the general case is at least as hard as the special case.
In "practice", we are given $L_2$ and are stuck with the problem of picking a good reduction partner $L_1$, i.e. finding a special case of $L_2$ that has proven to be $R$-hard.
Simple Example
Assume we want to show that KNAPSACK is NP-hard. Luckily, we know that SUBSET-SUM is NP-complete, and it is indeed a special case of KNAPSACK. The reduction
$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$
suffices; $(V,W,v,w)$ is the KNAPSACK instance that asks whether we can achieve at least value $v$ with item values in $V$ so that the corresponding weights from $W$ remain beneath $w$ in total. We don't need the weight restrictions for simulating SUBSET-SUM, so we just set them to tautological values.
Simple exercise problem
Consider the MAX-3SAT problem: given a propositional formula $\varphi$ and integer $k$, decide whether there is an interpretation of $\varphi$ that fulfills at least $k$ clauses. Show that it is NP-hard.
3SAT is a special case; $f(\varphi) = (\varphi, m)$ with $m$ the number of clauses in $\varphi$ suffices.
Example
Assume we are investigating the SUBSET-SUM problem and want to show that it is NP-hard.
We are lucky and know that the PARTITION problem is NP-complete. We confirm that it is indeed a special case of SUBSET-SUM and formulate
$\qquad \displaystyle f(A) = \begin{cases}
\left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\
\left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else}
\end{cases}$
where $A$ is the input set of PARTITION, and $(A,k)$ is an instance for SUBSET-SUM that asks after a subset of $A$ summing to $k$. Here, we have to take care of the case that there is no fitting $k$; in that case, we give an arbitrary infeasible instance.
Exercise Problem
Consider the problem LONGEST-PATH: given a directed graph $G$, nodes $s,t$ of $G$ and integer $k$, decide whether there is a simple path from $s$ to $t$ in $G$ of length at least $k$.
Show that LONGEST-PATH is NP-hard.
HAMILTON-CYCLE is a well-known NP-complete problem and a special case of LONGEST-PATH; $f(G) = (G,v,v,n)$ for arbitrary node $v$ in $G$ suffices.
Note in particular how reducing from HAMILTON-PATH requires more work.
Context
StackExchange Computer Science Q#11209, answer score: 21
Revisions (0)
No revisions yet.