What are common techniques for reducing problems to each other?
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) &amp;, \sum_{a \in A} a\mod 2 = 0 \\
  \left(A, 1 + \sum_{a \in A} |a|\right) &amp;, \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.