Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
If you don't find a reference, and it seems like this is an original argument, then do consider posting it here: meta.cstheory.stackexchange.com/questions/784/… –  Suresh Venkat Oct 17 '11 at 16:10
add comment

1 Answer 1

up vote 14 down vote accepted

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.

share|improve this answer
9  
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) –  Standa Zivny Oct 16 '11 at 19:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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