1
$\begingroup$

I have been reading Alimonti and Kann's paper "Some APX-Completeness results for cubic graphs" and I don't understand why the degree-reduction gadgets for Max Cut and Min Vertex Cover have to be different.

Here are the two gadgets in question. The Min Vertex Cover gadget simply divides a degree $n$ node $v$ into a chain of nodes $v_1,u,v_2$, where $v_1$ and $v_2$ share the edges of $v$, increasing the Min Vertex Cover by 1 in the process. The Max Cut gadget on the other hand is rather more complicated and involves cycles. What I don't understand is why the simple Min Vertex Cover gadget can't be used for Max Cut?

Consider a degree 4 vertex $v$ in Max Cut. If you unfold the vertex as $v_1,u,v_2$ (as in the Min Vertex Cover example) you are adding 2 edges to the graph, both of which can be cut by placing $u$ on the opposite side of the cut to $v_1$ and $v_2$, so wouldn't the Max Cut just increase by 2? I'm probably missing something but I don't know what it is.

$\endgroup$
1
  • 1
    $\begingroup$ Have you tried proving that this gadget works for Max Cut? $\endgroup$ Jun 16, 2016 at 13:46

1 Answer 1

2
$\begingroup$

This is a counterexample.

Suppose you have this graph:

Graph 1

The maximum cut in this graph has four edges. If you follow the procedure used for vertex cover you get this cut:

Graph 2

In the image, the maximum cut has seven edges.

$\endgroup$

Your Answer

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

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