4
$\begingroup$

In Cormen's Algorithms book on NP-completeness they prove various problems are NP-complete by reducing a previously proved NP-complete problem (call $K$) to current problem (call $L$). Each proof involves some clever construction which reduces all instances of $K$ to few instances of $L$. Here is the proof order they follow. CIRCUIT-SAT, SAT, 3 CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP. e.g. in reducing VERTEX-COVER to HAM-CYCLE they use a widget which does the trick.

After this previous question of mine, I think one can reduce back. i.e. one can reduce HAM-CYCLE to VERTEX-COVER problem. I tried searching web for such reductions, but most of the link return the normal reduction order. I'm interested to see if one can reduce in reverse order. i.e. TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

I'm looking for reverse constructive proofs. I know all of these problems belong to NP-complete hence equivalent.

You don't have to give complete proof as an answer. Proof sketches are fine too. If you can point me where these proofs are available online, that's completely fine too. I'm just trying to lean how constructions are leveraged among problems that look so different on surface. Thanks!

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Well I found most reductions interesting because they are construction proofs. It's hard to think out-of-the-box constructions. So I wanted to see if reverse construction is possible. $\endgroup$
    – Ankush
    Commented Aug 17, 2012 at 14:34
  • 1
    $\begingroup$ What have you tried? All stated problems are $\mathsf{NP}$-Complete. Thus every problem in $\mathsf{NP}$ can be reduced to your problems (by definition of $\mathsf{NPC}$). Hint: Start reducing TSP to HAM-CYCLE. $\endgroup$
    – Christopher
    Commented Aug 17, 2012 at 14:40
  • 1
    $\begingroup$ @Chris As of now nothing. I mean till yesterday I was under impression that above isn't possible. Let me start with TSP to HAM-CYCLE :) $\endgroup$
    – Ankush
    Commented Aug 17, 2012 at 15:13
  • 1
    $\begingroup$ Note that not all NPC problems are equally hard, see e.g. weakly vs strongly NP-completeness. Therefore, not all reductions are equally simple; those from strong to weak problems have to be complex enough to prevent e.g. efficient approximations to carry over (unless P=NP). $\endgroup$
    – Raphael
    Commented Aug 18, 2012 at 6:16
  • 1
    $\begingroup$ I'd offer you to read Garey & Johnson book, they provide iff proof for some of problems, proof techniques are not easy and you can't expect to solve them yourself in few days. $\endgroup$
    – user742
    Commented Aug 18, 2012 at 18:32

1 Answer 1

Reset to default
2
$\begingroup$

A couple of the ones you're looking at here are pretty simple actually (at least to sketch!). For all of these, there are many other ways to do it, even many other sensible ways, so these are just attempts to pick the simpler approaches (we'll see if I succeed).

As mentioned in one of the comments on the question, $3SAT$ to $SAT$ is trivial, an instance of $3SAT$ is already and instance of $SAT$, so there's no work needed at all.

To get from $VERTEX$ $COVER$ $(VC)$ to $CLIQUE$ we can do a couple of short jumps, that'll also put another problem in the loop. $VC$ is the dual of $INDEPENDENT$ $SET$ $(IS)$, that is, we can find a vertex cover of size $k$ in a graph $G$ iff we can find an independent set of size $n-k$ in $G$. Play around with this a little and you'll see why this is true. If we then take the edge-complement graph $\bar{G}$ of $G$, an independent set of size $t$ in $G$ is the same as a clique of size $t$ in $\bar{G}$, so that gets us to $CLIQUE$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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