<p>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 <strike>problem</strike> language can be reduced to other <strike>problem(s)</strike> language(s). This is the picture from the book:
<a href="https://i.sstatic.net/WLl2U.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WLl2U.png" alt="enter image description here"></a></p>

<p>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?</p>

<p>*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 <em>really unrelated language</em> to both VC and Max-Cut.</p>

<p>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.</p>

CC BY-SA 3.0
2015-11-07T10:24:35.193Z
VC corresponds to MC. Take any vertex cover C (not the minimum), then (C, V\C) is a partition that defines a cut (edges that cross the partition). Now, minimizing the size of the cover |C| leads to the maximum cut size. So, if there is a way of moving vertices out of C to get the minimum vertex cover then we get the maximum cut size. Vice versa, if you have a partition with the maximum cut, then the smaller set in the partition constitutes the minimum vertex cover.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-11-07T15:31:02.253Z
@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 ?!
In Theory
CC BY-SA 3.0
2015-11-09T15:50:33.560Z
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.
taninamdar
CC BY-SA 3.0
2015-11-09T18:49:54.867Z
@MohammadAl-Turkistany: you are mistaken.
In Theory
CC BY-SA 3.0
2015-11-10T11:18:22.720Z
Aha, yes there is a mistake.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-11-24T01:36:27.747Z
There is a simple direct reduction e.g. here: http://people.engr.ncsu.edu/mfms/Teaching/CSC505/wrap/Lectures/week14.pdf
Jukka Suomela
CC BY-SA 3.0
2015-11-24T02:53:00.057Z
@JukkaSuomela unless I'm mistaken, the reduction seems to be from Graph Partition to Max Cut. I am interested in the reduction from Vertex Cover to Max Cut.
taninamdar
CC BY-SA 3.0
2015-11-24T10:48:46.813Z
@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.)
Jukka Suomela
CC BY-SA 3.0
2015-11-24T14:56:43.567Z
@JukkaSuomela Oops, you're right. I missed that part. Thank you!
taninamdar
<np-hardness><max-cut>
Reduction from Vertex Cover to Max-Cut?
taninamdar
# Reduction from Vertex Cover to Max-Cut?

(Asked by: username_0 on 2015-11-05)

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](https://i.sstatic.net/WLl2U.png)](https://i.sstatic.net/WLl2U.png)

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.

**Tags:** np-hardness, max-cut

> **Comments:**
> **username_1**: VC corresponds to MC. Take any vertex cover C (not the minimum), then (C, V\C) is a partition that defines a cut (edges that cross the partition). Now, minimizing the size of the cover |C| leads to the maximum cut size. So, if there is a way of moving vertices out of C to get the minimum vertex cover then we get the maximum cut size. Vice versa, if you have a partition with the maximum cut, then the smaller set in the partition constitutes the minimum vertex cover.  
> **username_2**: @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 ?!  
> **username_0**: 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.  
> **username_2**: @MohammadAl-Turkistany: you are mistaken.  
> **username_1**: Aha, yes there is a mistake.  
> **username_3**: There is a simple direct reduction e.g. here: http://people.engr.ncsu.edu/mfms/Teaching/CSC505/wrap/Lectures/week14.pdf  
> **username_0**: @JukkaSuomela unless I'm mistaken, the reduction seems to be from Graph Partition to Max Cut. I am interested in the reduction from Vertex Cover to Max Cut.  
> **username_3**: @username_0: 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.)  
> **username_0**: @JukkaSuomela Oops, you're right. I missed that part. Thank you!  

---

## 0 answers

