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.


closed as off-topic by Yuval Filmus, Sasho Nikolov, Kaveh, R B, Ryan Williams Nov 8 '15 at 4:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Yuval Filmus, Sasho Nikolov, Kaveh, R B, Ryan Williams
If this question can be reworded to fit the rules in the help center, please edit the 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 '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.