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
    $\begingroup$ Have you tried proving that this gadget works for Max Cut? $\endgroup$ – Yuval Filmus Jun 16 '16 at 13:46
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, privacy policy and cookie policy

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