<p>Yes, by a reduction from MaxCut to triangle-free MaxCut. Here is what Wikipedia calls an <a href="http://en.wikipedia.org/wiki/L-reduction" rel="noreferrer">L-reduction</a></p>

<p>Given an instance $G$ of Max-Cut, construct the 3-stretch $G&#39;$ by subdividing each edge into three edges. Then the order of the maximum cut of $G&#39;$  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.</p>

CC BY-SA 3.0
2011-10-16T19:38:28.123Z
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: http://dml.cz/handle/10338.dmlcz/105554)
Standa Zivny
CC BY-SA 3.0
2011-10-16T17:10:40.837Z
2011-10-16T17:10:40.837Z
Colin McQuillan
<p>In the <strong>Max-Cut</strong> 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. </p>

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

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

<p><strong>Question:</strong> Is Max-Cut APX-complete on triangle-free graphs? (Note: arbitrary degrees allowed)</p>

<p>Thank you.</p>

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

<p>References:</p>

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

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

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

CC BY-SA 3.0
2011-10-17T16:10:08.087Z
If you don't find a reference, and it seems like this is an original argument, then do consider posting it here: http://meta.cstheory.stackexchange.com/questions/784/original-proofs-generated-on-the-parent-site
Suresh Venkat
<cc.complexity-theory><approximation-algorithms><approximation-hardness><max-cut>
Is Max-Cut APX-complete on triangle-free graphs?
Standa Zivny
# Is Max-Cut APX-complete on triangle-free graphs?

(Asked by: username_0 on 2011-10-16)

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

**Tags:** cc.complexity-theory, approximation-algorithms, approximation-hardness, max-cut
> **Comments:**
> **username_1**: If you don't find a reference, and it seems like this is an original argument, then do consider posting it here: http://meta.cstheory.stackexchange.com/questions/784/original-proofs-generated-on-the-parent-site  

---

## 1 answers

### Answer by username_2 on 2011-10-16. Score: 15 | Accepted answer

Yes, by a reduction from MaxCut to triangle-free MaxCut. Here is what Wikipedia calls an [L-reduction](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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: http://dml.cz/handle/10338.dmlcz/105554)  

---

