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.



  • $\begingroup$ This really belongs in cstheory.stackexchange.com $\endgroup$ – Fixee Feb 25 '11 at 1:27
  • $\begingroup$ @Fixee No he's right to post here, but sadly, there seems to be of a bit of lacuna in the StackExchange network for anyone interested in intermediate-level questions on CSTheory... $\endgroup$ – Uticensis Feb 25 '11 at 1:48

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$.

  • $\begingroup$ Cool...thanks Moron. Thats pretty clever thinking! And I thought there should not be one to many kind of reductions. Can you also suggest some many to one? It seems more natural to me that these should exist $\endgroup$ – Akash Kumar Feb 25 '11 at 2:58
  • $\begingroup$ @Akash: Many to one seems more unnatural to me :-) Normally when you are trying to reduce problem $A$ to $B$, you begin with a specific instance of input for $A$. For example in the above, we started with just one graph for which we need to find existence of Hamiltonian Cycle... $\endgroup$ – Aryabhata Feb 25 '11 at 3:01

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.

  • $\begingroup$ lol..thats clever but I do not know what to say, thats also evil :P. please do not mind..i am just joking...but yes, thats clever. thanks $\endgroup$ – Akash Kumar Feb 25 '11 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.