10
$\begingroup$

In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph such that the number of edges between S and the complement of S is as large as possible.

Max-Cut is APX-complete on bounded-degree graphs [PY91], and in fact APX-complete on cubic graphs (i.e. graphs of degree 3) [AK00].

Max-Cut is NP-complete on triangle-free graphs of degree at most 3 [LY80] (triangle-free means that the input graph does not contain K_3, the complete graph on 3 vertices, as a subgraph).

Question: Is Max-Cut APX-complete on triangle-free graphs? (Note: arbitrary degrees allowed)

Thank you.

UPDATE: An answer has been found, but I would still be interested in a reference for this result, if there is any.

References:

[AK00] P. Alimonti and V. Kann: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1-2): 123-134, 2000. doi: 10.1016/S0304-3975(98)00158-3

[LY80] J.M. Lewis and M. Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci. 20(2): 219-230, 1980. doi: 10.1016/0022-0000(80)90060-4

[PY91] C.H Papadimitriou and M. Yannakakis: Optimization, Approximation, and Complexity Classes, J. Comput. System Sci., 43(3): 425-440, 1991. doi: 10.1016/0022-0000(91)90023-X

$\endgroup$
1

1 Answer 1

15
$\begingroup$

Yes, by a reduction from MaxCut to triangle-free MaxCut. Here is what Wikipedia calls an L-reduction

Given an instance $G$ of Max-Cut, construct the 3-stretch $G'$ by subdividing each edge into three edges. Then the order of the maximum cut of $G'$ is the order of the maximum cut of $G$ plus twice the number of edges in $G$. Since the size of a max cut is always at least half the number of edges, the error ratio only gets worse by a constant factor.

$\endgroup$
1
  • 9
    $\begingroup$ Thank you Colin! While looking for an answer, I've discovered the same trick you call "3-stretch", also known as 2-subdivision. From what I've found, it probably first appeared in this paper: Svatopluk Poljak: A note on stable sets and colouring of graphs, Comment. Math. Univ. Carolinae 15 (1974) 307-309 (available here: dml.cz/handle/10338.dmlcz/105554) $\endgroup$ Commented Oct 16, 2011 at 19:38

Your Answer

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

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