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.

  • 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, 2015 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, 2015 at 15:50
  • 3
    $\begingroup$ @MohammadAl-Turkistany: you are mistaken. $\endgroup$
    – In Theory
    Nov 9, 2015 at 18:49
  • 2
    $\begingroup$ There is a simple direct reduction e.g. here: people.engr.ncsu.edu/mfms/Teaching/CSC505/wrap/Lectures/… $\endgroup$ Nov 24, 2015 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$ Nov 24, 2015 at 10:48


Browse other questions tagged or ask your own question.