<p>I realize that this might not directly answer your question (about references), but I would like to outline a possible approach for showing NP-hardness without the 2-connected condition. There are two things that are missing: one is a proof of the NP-hardness of the 'source problem', so to speak, and the other is that I'm reducing to a 'colored' version of H-cut that may or may not be useful. As for the first bottleneck, I believe I have a proof in my mind that I am being lazy about formalizing, so I hope I will get around to that soon. I've thought some about reducing the colored version to the one you present, however, with little luck so far. I am also very curious about your proof in the event that H is 2-connected, could you possibly supply some details?</p>

<p>So the colored version is the following: each vertex in the graph is equipped with a list of colors from a palette P (a fixed, finite set). We are required to find a cut so that no partition induces a monochromatic copy of H, that is, there is no subset of |H| vertices that induces a copy of H, and the corresponding list of colors have a non-empty intersection.  </p>

<p>Here's a reduction from a restricted variant of d-SAT, where d is |H|. (Notice that this obviously wouldn't work when d = 2). </p>

<p>The restricted variant of d-SAT is the following: </p>

<ol>
<li><p>Every clause has either only positive or only negative literals, let me refer to such clauses as P-clauses and N-clauses respectively,</p></li>
<li><p>Every P-clause can be paired off with a N-clause such that the two clauses involve the same set of variables.</p></li>
</ol>

<p>(I have some idea about why this seemingly restricted version might be hard - a very closely related restriction is hard, and I can imagine a reduction from there, although I could be easily mistaken!)</p>

<p>Given this problem, the reduction perhaps suggests itself. The graph has a vertex for every variable of the formula. For every clause C_i, induce a copy of H on the set of variables that participate in the clause, and add the color i to this set of vertices. This completes the construction.</p>

<p>Any assignment naturally corresponds to a cut:</p>

<p>L = set of all variables that were set to 0,
R = set of all variables that are set to 1.</p>

<p>The claim is that a satisfying assignment corresponds to a monochromatic-H-free cut. </p>

<p>In other words, (L,R), when given by a satisfying assignment, would be such that neither L or R induce a monochromatic copy of H. If L has such a copy, then notice that the corresponding P-clause must have had all its variables set to 0, which contradicts the fact that the assignment was satisfying. Conversely, if R has such a copy, then the corresponding N-clause must have had all its variables set to 1, contradiction again.</p>

<p>Conversely, consider any cut, and set the variables on one side to 1 and the other to 0 (notice that it doesn't matter which way you do it - given the kind of formula we're working with, an assignment and it's flipped version are equivalent as far as satisfiability goes). If a clause isn't satisfied by this assignment, then we can trace it back to a monochromatic copy of H on one of the sides, contradicting the monchromatic-H-freeness of the cut. </p>

<p>The reason one has to indulge in the coloring is because copies of H can interfere to create spurious copies of H that don't correspond to clauses, in a direct reduction attempt. Indeed, it fails - badly - even when H is something as simple as a path.</p>

<p>I've had no luck in getting rid of the colors, and I am not sure that I have made the problem any simpler. However, I do hope that - if correct - it might be a start. </p>

CC BY-SA 2.5
2010-08-29T15:30:03.583Z
Thank you for the answer. As to the proof I had, I started with not all equal 3 sat which was transformed to an expression with some structure and then constructed a few complicated (to describe and draw) gadgets exploiting that structure. If I have time I might write up and put up the paper somewhere (and post a link).
Aryabhata
CC BY-SA 2.5
2010-08-29T16:24:43.177Z
Ah, ok. I did try starting with not-one-in-3-sat, but without much luck (don't know why I even expected it to work). I would love to look at the details if/when you have them, sounds like good work! I mean to keep at this for some more, FWIW.
Neeldhara
CC BY-SA 2.5
2010-08-29T19:27:50.523Z
It was the monotone version of nae-3sat. Thanks for the encouragement! Glad to see it has garnered your interest :-)
Aryabhata
CC BY-SA 2.5
2011-02-15T18:26:47.003Z
RJK pointed me to an answer which links to a [paper](http://www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf) which has this reference: http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf
Aryabhata
CC BY-SA 2.5
2010-08-29T05:37:40.163Z
2010-08-29T05:37:40.163Z
Neeldhara
<p>You could look for the term "bipartition" or "vertex partition" or "coloring" rather than "cut".  Various generalizations of the chromatic number along the lines you hint at have been considered since the mid-80s (or possibly earlier). There are some early hard-to-find references in Canadian combinatorics conferences, but you might want to check out Cowen, Goddard and Jesurum (JGT or SODA 1997) and related references/citations.</p>

<p><strong>Edited 15/02/2011</strong></p>

<p>As pointed out by <a href="https://cstheory.stackexchange.com/questions/884/h-free-partition/4107#4107">Aravind</a> and <a href="https://cstheory.stackexchange.com/users/126/moron">Moron</a> (in the comments below),
the following references show that the $H$-free cut problem is NP-hard except in the trivial cases.</p>

<p>D. Achlioptas.  The complexity of $G$-free colourability. Discrete Math. 165/166 (1997) 21-30.<a href="http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf" rel="nofollow noreferrer"> [pdf]</a>.</p>

<p>A. Farrugia.  Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard.  Electron. J. Combin. 11 (2004) #R46 (9 pp).</p>

CC BY-SA 3.0
2013-04-24T19:07:54.497Z
The other paper pdf is here: www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf
Aryabhata
CC BY-SA 2.5
2011-02-15T17:25:09.410Z
@Moron: Actually, an answer in the H-free partition question is much more relevant than my answer!  http://cstheory.stackexchange.com/questions/884/h-free-partition/4107#4107
RJK
CC BY-SA 2.5
2011-02-15T17:31:13.950Z
I looked at that and it seemed to be about classes of graphs which include subgraphs etc. This problem relates to freeness of specific graph.
Aryabhata
CC BY-SA 2.5
2011-02-15T17:56:17.997Z
@Moron: The Farrugia paper includes cases in which each part is additive induced, i.e. closed under disjoint union and vertex deletion.  H-freeness is an additive induced property.
RJK
CC BY-SA 2.5
2011-02-15T18:19:41.097Z
You are right. I was just going by the abstract. In fact, apparently the paper http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf is also relevant to the question as asked! Do you mind if I edit your answer to add those links?
Aryabhata
CC BY-SA 3.0
2010-08-17T08:18:26.977Z
2013-04-24T19:11:43.660Z
2017-04-13T12:32:28.117Z
RJK
<p>Suppose you are given a connected, simple, undirected graph H.</p>

<p>The H-free cut problem is defined as follows:</p>

<blockquote>
  <p>Given a simple, undirected graph G, is
  there a cut (partition of vertices
  into two non-empty sets, L,R) such
  that graphs induced by the cut-sets (L
  and R) both do not contain a subgraph
  isomorphic to H.</p>
</blockquote>

<p>For example, when H is the graph with two vertices connected by a single edge, the problem is the same as determining if a graph is bipartite and is in P.</p>

<p>In case H is a triangle, this is like the vertex version of the <a href="http://en.wikipedia.org/wiki/Monochromatic_triangle" rel="nofollow">Monochromatic Triangle</a> problem.</p>

<p>I think I have been able to show that when H is 2-connected with at least three vertices, the H-free cut problem is NP-Complete. </p>

<p>I haven't been able to find any references to this problem (and so, any results).</p>

<p>Can we drop the 2-connectedness condition and still prove NP-Completeness?</p>

<p>Does anyone know of any known results which would imply the above or a stronger result (or you think might be relevant)?</p>

CC BY-SA 2.5
2010-08-17T02:05:53.497Z
"I think I have been able to show that when H is 2-connected with at least three vertices, the H-free cut problem is NP-Complete."

Does this mean that for every two-connected H with three or more vertices, H-free cut is NP-complete? And likewise, if we drop 2-connectedness, we want to prove that for every H with three or more vertices, H-free cut is NP-complete?
Evgenij Thorstensen
CC BY-SA 2.5
2010-08-17T02:27:30.043Z
@Evgenij: Yes, for every such H, it is NP-Complete. So it is a class of NP-Complete problems. Yes to the other question too.
Aryabhata
<cc.complexity-theory><reference-request><graph-theory><np-hardness>
H-free cut problem
Aryabhata
# H-free cut problem

(Asked by: username_0 on 2010-08-16)

Suppose you are given a connected, simple, undirected graph H.

The H-free cut problem is defined as follows:

> Given a simple, undirected graph G, is
> there a cut (partition of vertices
> into two non-empty sets, L,R) such
> that graphs induced by the cut-sets (L
> and R) both do not contain a subgraph
> isomorphic to H.

For example, when H is the graph with two vertices connected by a single edge, the problem is the same as determining if a graph is bipartite and is in P.

In case H is a triangle, this is like the vertex version of the [Monochromatic Triangle](http://en.wikipedia.org/wiki/Monochromatic_triangle) problem.

I think I have been able to show that when H is 2-connected with at least three vertices, the H-free cut problem is NP-Complete.

I haven't been able to find any references to this problem (and so, any results).

Can we drop the 2-connectedness condition and still prove NP-Completeness?

Does anyone know of any known results which would imply the above or a stronger result (or you think might be relevant)?

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-hardness
> **Comments:**
> **username_1**: "I think I have been able to show that when H is 2-connected with at least three vertices, the H-free cut problem is NP-Complete."  Does this mean that for every two-connected H with three or more vertices, H-free cut is NP-complete? And likewise, if we drop 2-connectedness, we want to prove that for every H with three or more vertices, H-free cut is NP-complete?  
> **username_0**: @Evgenij: Yes, for every such H, it is NP-Complete. So it is a class of NP-Complete problems. Yes to the other question too.  

---

## 2 answers

### Answer by username_3 on 2010-08-17. Score: 9 | Accepted answer

You could look for the term "bipartition" or "vertex partition" or "coloring" rather than "cut". Various generalizations of the chromatic number along the lines you hint at have been considered since the mid-80s (or possibly earlier). There are some early hard-to-find references in Canadian combinatorics conferences, but you might want to check out Cowen, Goddard and Jesurum (JGT or SODA 1997) and related references/citations.

**Edited 15/02/2011**

As pointed out by [Aravind](https://cstheory.stackexchange.com/questions/884/h-free-partition/4107#4107) and [Moron](https://cstheory.stackexchange.com/users/126/moron) (in the comments below),
the following references show that the $H$-free cut problem is NP-hard except in the trivial cases.

D. Achlioptas. The complexity of $G$-free colourability. Discrete Math. 165/166 (1997) 21-30. [[pdf]](http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf).

A. Farrugia. Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Combin. 11 (2004) #R46 (9 pp).

> **Comments:**
> **username_3**: @Moron: Actually, an answer in the H-free partition question is much more relevant than my answer!  http://cstheory.stackexchange.com/questions/884/h-free-partition/4107#4107  
> **username_0**: I looked at that and it seemed to be about classes of graphs which include subgraphs etc. This problem relates to freeness of specific graph.  
> **username_3**: @Moron: The Farrugia paper includes cases in which each part is additive induced, i.e. closed under disjoint union and vertex deletion.  H-freeness is an additive induced property.  
> **username_0**: You are right. I was just going by the abstract. In fact, apparently the paper http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf is also relevant to the question as asked! Do you mind if I edit your answer to add those links?  
> **username_0**: The other paper pdf is here: www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf  

---

### Answer by username_2 on 2010-08-29. Score: 2

I realize that this might not directly answer your question (about references), but I would like to outline a possible approach for showing NP-hardness without the 2-connected condition. There are two things that are missing: one is a proof of the NP-hardness of the 'source problem', so to speak, and the other is that I'm reducing to a 'colored' version of H-cut that may or may not be useful. As for the first bottleneck, I believe I have a proof in my mind that I am being lazy about formalizing, so I hope I will get around to that soon. I've thought some about reducing the colored version to the one you present, however, with little luck so far. I am also very curious about your proof in the event that H is 2-connected, could you possibly supply some details?

So the colored version is the following: each vertex in the graph is equipped with a list of colors from a palette P (a fixed, finite set). We are required to find a cut so that no partition induces a monochromatic copy of H, that is, there is no subset of |H| vertices that induces a copy of H, and the corresponding list of colors have a non-empty intersection.

Here's a reduction from a restricted variant of d-SAT, where d is |H|. (Notice that this obviously wouldn't work when d = 2).

The restricted variant of d-SAT is the following:

1. Every clause has either only positive or only negative literals, let me refer to such clauses as P-clauses and N-clauses respectively,
2. Every P-clause can be paired off with a N-clause such that the two clauses involve the same set of variables.

(I have some idea about why this seemingly restricted version might be hard - a very closely related restriction is hard, and I can imagine a reduction from there, although I could be easily mistaken!)

Given this problem, the reduction perhaps suggests itself. The graph has a vertex for every variable of the formula. For every clause C\_i, induce a copy of H on the set of variables that participate in the clause, and add the color i to this set of vertices. This completes the construction.

Any assignment naturally corresponds to a cut:

L = set of all variables that were set to 0,
R = set of all variables that are set to 1.

The claim is that a satisfying assignment corresponds to a monochromatic-H-free cut.

In other words, (L,R), when given by a satisfying assignment, would be such that neither L or R induce a monochromatic copy of H. If L has such a copy, then notice that the corresponding P-clause must have had all its variables set to 0, which contradicts the fact that the assignment was satisfying. Conversely, if R has such a copy, then the corresponding N-clause must have had all its variables set to 1, contradiction again.

Conversely, consider any cut, and set the variables on one side to 1 and the other to 0 (notice that it doesn't matter which way you do it - given the kind of formula we're working with, an assignment and it's flipped version are equivalent as far as satisfiability goes). If a clause isn't satisfied by this assignment, then we can trace it back to a monochromatic copy of H on one of the sides, contradicting the monchromatic-H-freeness of the cut.

The reason one has to indulge in the coloring is because copies of H can interfere to create spurious copies of H that don't correspond to clauses, in a direct reduction attempt. Indeed, it fails - badly - even when H is something as simple as a path.

I've had no luck in getting rid of the colors, and I am not sure that I have made the problem any simpler. However, I do hope that - if correct - it might be a start.

> **Comments:**
> **username_0**: Thank you for the answer. As to the proof I had, I started with not all equal 3 sat which was transformed to an expression with some structure and then constructed a few complicated (to describe and draw) gadgets exploiting that structure. If I have time I might write up and put up the paper somewhere (and post a link).  
> **username_2**: Ah, ok. I did try starting with not-one-in-3-sat, but without much luck (don't know why I even expected it to work). I would love to look at the details if/when you have them, sounds like good work! I mean to keep at this for some more, FWIW.  
> **username_0**: It was the monotone version of nae-3sat. Thanks for the encouragement! Glad to see it has garnered your interest :-)  
> **username_0**: RJK pointed me to an answer which links to a [paper](http://www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf) which has this reference: http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf  

---

