# H-free cut problem

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 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)?

• "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? Aug 17 '10 at 2:05
• @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. Aug 17 '10 at 2:27

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 and 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].

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

• @Moron: Actually, an answer in the H-free partition question is much more relevant than my answer! cstheory.stackexchange.com/questions/884/h-free-partition/…
– RJK
Feb 15 '11 at 17:25
• 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. Feb 15 '11 at 17:31
• @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
Feb 15 '11 at 17:56
• You are right. I was just going by the abstract. In fact, apparently the paper 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? Feb 15 '11 at 18:19
• The other paper pdf is here: www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf Apr 24 '13 at 19:07

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.

• 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). Aug 29 '10 at 15:30
• 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. Aug 29 '10 at 16:24
• It was the monotone version of nae-3sat. Thanks for the encouragement! Glad to see it has garnered your interest :-) Aug 29 '10 at 19:27
• RJK pointed me to an answer which links to a paper which has this reference: users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf Feb 15 '11 at 18:26