7
$\begingroup$

I am referring to Computational Complexity by Arora and Barak for my course. In the section on NP-completeness reductions, the book has a diagram that is represents how one NP-complete problem language can be reduced to other problem(s) language(s). This is the picture from the book: enter image description here

However, even after thinking for quite some time, I can't think of a reduction from Vertex Cover to Max-Cut. Nor could I find any resource online. My question is, is there any (non-trivial*) reduction? Or is it some kind of misprint?

*Non-trivial meaning that it's not of the forms: 1) Vertex Cover -> SAT -> ... -> Max-Cut using Cook-Levin Theorem, or 2) Vertex Cover -> L -> ... -> Max-Cut, where L is some really unrelated language to both VC and Max-Cut.

Note: Even though the arrow reads Ex 2.16, the actual Ex 2.16 just asks to prove that Max-Cut is NP-complete. Also, this is not a homework question.

$\endgroup$
  • 1
    $\begingroup$ @MohammadAl-Turkistany: "Vice versa, if you have a partition with the maximum cut, then the smaller set in the partition constitutes the minimum vertex cover." So, you claim that in any optimal cut, the bigger set is an (maximum) independent set ?! $\endgroup$ – In Theory Nov 7 '15 at 15:31
  • 4
    $\begingroup$ Why close the question? How exactly does this question differ from a research-level question? If someone has shown a reduction, then you could just describe it. I'm not asking something as simple as time complexity of binary search. I've tried to think and (then) search about it before asking it here. $\endgroup$ – taninamdar Nov 9 '15 at 15:50
  • 3
    $\begingroup$ @MohammadAl-Turkistany: you are mistaken. $\endgroup$ – In Theory Nov 9 '15 at 18:49
  • 2
    $\begingroup$ There is a simple direct reduction e.g. here: people.engr.ncsu.edu/mfms/Teaching/CSC505/wrap/Lectures/… $\endgroup$ – Jukka Suomela Nov 24 '15 at 1:36
  • 1
    $\begingroup$ @taninamdar: Did you read the slides? Forget about graph partitioning, on pages 4–9 there is a reduction from independent set to max-cut. (Which, of course, directly gives a reduction from vertex cover to max cut.) $\endgroup$ – Jukka Suomela Nov 24 '15 at 10:48

Browse other questions tagged or ask your own question.