Many one and One many reductions

Question

I do not have enough complexity theory background, but I was wondering about the kind of reductions that we normally do to show NP-Completeness. I think all of the reductions that I have seen are one-to-one; in that, given an instance $I_1$ of problem $P_1$, they map it to instance $I'_1$ of problem $P'_1$ such that $I'_1$ is a yes instance of $P'_1$ iff $I_1$ is a yes instance of $P_1$.

But I have never seen any reduction which can, say map an instance $I_1$ of $P_1$ to say $2$ or more instances of $P_2$ (in some sense, the mapping should involve creating some structure in $I_2$ where we have $2$ or more choices and we could pick any one arbitrarily). This will be kind of surprising (to me) if it exists, but nevertheless the following question bothers me even more.

Leaving that aside, I have never seen any reduction which might map $2$ or more (say YES instances) of a problem $P$ to the same instance of some problem $Q$.

I would appreciate if you can exhibit these reductions for NP-Complete problems.

NOTE: I understand that this is more of a cstheory question. But since this is certainly not research level, I decided to post it here.

Thanks,

-Akash

Answer 1

For an example of one to many, from my answer here: Reduction from Hamiltonian cycle to Hamiltonian path

For a reduction from Hamiltonian Cycle to Hamiltonian Path.

Given a graph $G$ of which we need to find Hamiltonian Cycle, for a single edge $e = \{u,v\}$ add new vertices $u'$ and $v'$ such that $u'$ is connected only to $u$ and $v'$ is connected only to $v$ to give a new graph $G_e$.

$G_e$ has a hamiltonian path if and only if $G$ has a hamiltonian cycle with the edge $e=\{u,v\}$.

Run the Hamiltonian path algorithm on each $G_e$ for each edge $e \in G$. If all graphs have no hamiltonian path, then $G$ has no hamiltonian cycle. If at least one $G_e$ has a hamiltonian path, then $G$ has a hamiltonian cycle which contains the edge $e$.

Answer 2

The easiest way to get a many-to-one reduction is to partially solve the original problem.

For example, suppose we want to reduce CLIQUE to 3COLORABILITY. We get as input a pair $(G,k)$ and need to output $G'$ where $G'$ is 3-colorable iff $G$ has a clique of size exactly $k$.

We will proceed as follows.

1. If $k\leq 10$, solve CLIQUE by brute force in time O(n^10). If $G$ contains a clique of size $k$ output the trivial graph. Otherwise, output $K_4$.
2. If $k>10$, then use the standard reduction.

Every graph of the form $(G,k)$, $k\leq 10$, reduces to the same 2 graphs.

I realize that this seems artificial (because it is). The reason that you rarely see such reductions in practice is that it's often easier to reason about a 1-1 reduction. After all, you're trying to show that $x\in P \Leftrightarrow f(x)\in Q$ and so the reverse implication is often easier that way.