<p>I think there is a number of hard problems that become easy for triangle-free graphs; especially those deal directly with triangles such as Partition Into Triangles (Does G have a partition into triangles?). Other less trivial examples include:</p>

<ul>
<li><p>Stable Cutset Problem (Does G have an independent set S such that G-S is disconnected?). See: <i> On stable sutsets in graphs,</i> Discrete Applied Math. 105 (2000) 39-50.  </p></li>
<li><p>Intersection Graph Basis (Is G the intersection graph of subsets of a k-element ground set?). See: Problem [GT59] in: Garey &amp; Johnson, <i>Computers and Intractability: A Guide to the Theory of NP-Completeness. </i></p></li>
</ul>

CC BY-SA 3.0
2014-06-14T12:03:17.263Z
2014-06-14T14:43:06.887Z
2014-06-14T14:43:06.887Z
Mon Tag
<p>Here are some additional examples to Mon Tag's answer :</p>

<ul>
<li><p>The Disconnected Cutset problem (Does $G$ admit a set of vertices $S$ such that $G-S$ and the subgraph of $G$ induced by $S$ are disconnected) is NP-complete (see <a href="http://dx.doi.org/10.1007/978-3-642-23786-7_43">here</a>). It is easy to see that this problem is polynomially solvable for triangle-free graphs (hence also the Stable Cutset problem as mentioned by Mon Tag). </p></li>
<li><p>Recognizing triangular line graphs is NP-complete (see <a href="http://www.sciencedirect.com/science/article/pii/S0012365X11005449">here</a>), It is also 
easy to see that this problem becomes polynomially for triangle-free input graphs.  </p></li>
<li><p>Computing the maximum connected matching is hard (see <a href="http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1206">here</a>. 
A matching is connected if, for any pair of the matching edges, there is another edge of the graph incident to both of them). 
It can be proved that this problem is polynomially solvable for $(C_3, C_4, C_5)$-free graphs.</p></li>
</ul>

CC BY-SA 3.0
2014-06-18T09:11:02.307Z
Thank you. So some problems remain hard and others don't.
joro
CC BY-SA 3.0
2014-06-17T17:08:12.517Z
2014-06-17T17:58:16.420Z
2014-06-17T17:58:16.420Z
vb le
<p>From the comment above: in <a href="http://arxiv.org/abs/1208.0142" rel="noreferrer">Stefan Kratsch, Pascal Schweitzer, Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs</a>: GI is polynomial time (trivially) solvable for $(K_s,I_t)\text{-free}$ graphs, but also (less trivially) for $(K_s,K_{1,t})\text{-free}$ graphs.</p>

<p><strong>EDIT</strong>: as noted in the comment, $K_{1,t}$ doesn't contain a cycle (I read the introduction of the paper too quickly).</p>

<p>After thinking a little bit about it, it seems easy to prove the following (original?):</p>

<p><strong>NEGATIVE RESULT:</strong> <i>for every finite set $\{H_1,...H_k\}$ in which every $H_i$ contains a cycle, the problem of graph isomorphism (GI) restricted to the class $\mathcal{C}$ of $(H_1,...,H_k)\text{-free}$ graphs is GI-complete.</i></p>

<p><em>Proof:</em> Fixed a class of $(H_1,...,H_k)\text{-free}$ graphs in which each $H_i$ contains a cycle, and given $G_1,G_2$, let $r$ be the length of the longest cycle of the $H_i$s. Replace each edge $(u,v)$ of $G_1,G_2$ with a path of length $l = \lceil r/3 \rceil$  adding $l$ new nodes $(u,p_1,p_2,...,p_l,v)$ (see figure below). By construction the new graphs $G'_1, G'_2$ are $(H_1,...,H_k)\text{-free}$ indeed the possible shortest cycles are those formed by a triangle that must have length $3\lceil r/3 \rceil + 3 &gt; r$; and it is easy to prove that they are isomorphic if and only if the original $G_1,G_2$ are isomorphic.</p>

<p><img src="https://i.sstatic.net/IoPq3.png" alt="enter image description here">
<br>
<strong>Figure</strong>: a graph $G_1$ on the left, and the equivalent $(H_1,...,H_k)\text{-free}$ graph $G'_1$ on the right (suppose that the longest cycle of the $H_i$ has length $r=15$, so every edge of $G_1$ is replaced with a path of length $l = 5$.</p>

<p>We can also extend the negative result to Hamiltonian cycle NPC problem, indeed it is an immediate corollary to the following (original?):</p>

<p><strong>Theorem</strong>: for any $k \geq 3$, the Hamiltonian cycle problem remains NP-complete even if we the graph $G$ does not contain cycles of length $\leq k$.</p>

<p><em>Proof</em> We know that the Hamiltonian cycle problem is NPC even on a planar directed graph $G$ with each node $v$ satisfying: $outdeg(v) + indeg(v) \leq 3$ (Papdimitriou and Vazirani, On Two Geometric Problems Related to the Travelling Salesman Problem).
We can transform the graph $G$ to an undirectde graph $G'$ simply adding a node on the incoming edge of nodes $v$ that have $indeg(v )=1$, and to the outgoing edge of nodes $v$ that have $indeg(v)=2$.
Then we can replace the nodes of $G'$ with the gadget in the figure below. It is easy to see that there are only two valid traversals (<em>zigzags</em>) that visit each node of the gadget exactly once (red and green paths in the figure): the gadgets cannot be traversed from top-to-bottom, otherwise the horizontal (incoming or outgoing) path would be cut out.
Furthermore we can place enough nodes on the vertical/horizontal segments of the gadgets, and extend the number of its zigzags, to ensure that no cycle of length $\geq k$ is possible  in the gadget or in a triangle of 3 gadgets linked together. This assures that  if the resulting graph $G''$ has an Hamiltonian cycle, then the original graph $G$ has also an Hamiltonian cycle (the converse is immediate by construction of the gadget).</p>

<p><img src="https://i.sstatic.net/uw6oT.png" alt="enter image description here"></p>

<p><strong>Corollary:</strong> Hamiltonian cycle and path problems remain NP-complete even if restricted to  $(H_1,...,H_k)\text{-free}$ graphs, where every $H_i$ contains a cycle.</p>

CC BY-SA 3.0
2014-06-14T06:49:30.760Z
Thank you. $K_{1,t}$ is tree, so it is not cyclic or am I missing something?
joro
CC BY-SA 3.0
2014-06-14T10:02:15.637Z
You're right! I came up with a negative result ... see if it can work, or if it is completely wrong :-S :-S
Marzio De Biasi
CC BY-SA 3.0
2014-06-14T10:56:01.260Z
Thanks. So you got alleged negative result for GI AND Hamiltonian cycle?
joro
CC BY-SA 3.0
2014-06-14T11:03:25.730Z
Hope this is correct, this will solve a lot unknown to graphclasses.org problems.
joro
CC BY-SA 3.0
2014-06-14T11:03:37.457Z
Yes, the negative result extends to Hamiltonian cycle/path and probably to other related classes of NPC problems (e.g. TSP). ... mmm ... but if it solves *a lot of unknown problems* then (by experience) there are high chances that it is wrong :-) :-)
Marzio De Biasi
CC BY-SA 3.0
2014-06-14T11:05:13.813Z
If I find the paper it will give negative result for IS and Dominating set.
joro
CC BY-SA 3.0
2014-06-14T11:15:50.203Z
Let me know if it can be interesting/new: I already used similar gadgets (similar to the one in the bottom figure) for planar graphs, and I can try to sketch a formal proof.
Marzio De Biasi
CC BY-SA 3.0
2014-06-14T11:34:26.460Z
I though about replacing edges with gadgets too. To my knowledge this is original and interesting (and graphclasses.org suggests this is original). What about 3-COLOR gadget?
joro
CC BY-SA 3.0
2014-06-14T14:58:15.923Z
I asked a question about your GI paper. If you exclude sufficiently large graphs it becomes poly :)))
joro
CC BY-SA 3.0
2014-06-14T23:11:02.527Z
@joro: I'll think about 3-coloring, too!!! What do you mean with "if you exclude sufficiently large graphs it becomes poly"?
Marzio De Biasi
CC BY-SA 3.0
2014-06-15T04:37:11.187Z
Good luck with 3-coloring :) You wrote GI is poly for $(K_s,K_{1,t})\text{-free}$. If you take $s,t$ large enough the graph certainly will be free. The answer in the other question shows the paper means "poly in $s,t$".
joro
CC BY-SA 3.0
2014-06-15T11:45:34.793Z
I think for GI simpler is to subdivide every edge $r$ times where $r$ is the largest cycle in $H_i$ (not necessarily induced). This forbids induced cycles of length $ < r + 1$.
joro
CC BY-SA 3.0
2014-06-15T12:03:56.937Z
I think edge gadgets won't work for HC since they will involve Eulerian cycle.
joro
CC BY-SA 3.0
2014-06-15T12:09:40.387Z
btw, is there non-trivial class of digraphs where digraph isomorphism is in P? What about directed $P_4$ free?
joro
CC BY-SA 3.0
2014-06-15T12:13:51.613Z
@joro: you're right, subdividing edges is simpler :-) ... and because the shortest cycle is a 3-nodes clique, you can replace each edge with a path of length $\lceil r/3 \rceil$
Marzio De Biasi
CC BY-SA 3.0
2014-06-15T20:08:35.970Z
Just a nitpick, each of cycle should be sth like $(m+1)d_i$ where $d_i$ is a degree of vertex $i$, otherwise your iff part is not nesscesarry correct, may be $G_1,G_2$ are isomorphic but not $G'_1,G'_2$.
Saeed
CC BY-SA 3.0
2014-06-15T21:43:07.067Z
@Saeed: you're right; however the reduction suggested by joro is even simpler (replace every edge with a path of $\lceil r/3 \rceil$). I'll soon, update the answer and add the gadget for the negative result for Hamiltonian cycle.
Marzio De Biasi
CC BY-SA 3.0
2014-06-16T07:05:30.583Z
Don't think your conversion from directed to undirected preserves hamiltonicity, since you add vertices on edges. By adding a vertex on edge don't you force the directed edge to be on the HC of the digraph? (Don't think the GI construction is original, check forbidden subgraph here: https://cs.uwaterloo.ca/research/tr/1977/CS-77-04.pdf
joro
CC BY-SA 3.0
2014-06-16T07:17:01.293Z
@joro: yes it is correct (I just copied it from papadimitriou's paper). They key point is that the node is added on an edge that in a directed Hamiltonian path MUST be traversed.
Marzio De Biasi
CC BY-SA 3.0
2014-06-16T07:18:50.597Z
So all vertices you add are on edge that must be on the HC? You know a lot of edges of the HC of the digraph.
joro
CC BY-SA 3.0
2014-06-16T07:21:46.777Z
@joro: we are talking about DIRECTED hamiltonian cycle on a graph in which every node has $outdeg(v)+indeg(v) \leq 3$ (see paper), and in a node $v$ that has only one incoming edge (top left figure), that edge MUST be traversed;  in a node $v$ that has only one outgoing edge (top right figure), that edge MUST be traversed. Let me know if it is not clear.
Marzio De Biasi
CC BY-SA 3.0
2014-06-16T07:48:48.257Z
OK, let me first see the paper. Well might be wrong. If correct this a broad result :-)))
joro
CC BY-SA 3.0
2014-06-16T08:02:23.167Z
Browsing the paper you have $\Delta=3$?
joro
CC BY-SA 3.0
2014-06-16T08:12:30.017Z
What is $\Delta$? (yes, if you mean the max degree of the undirected equivalent graph $G'$). To summarize: in the theorem above, I give a reduction from Hamiltonian cycle on planar directed graphs in which indeg(v)+outdeg(v)<=3 to the Hamiltonian cycle problem on (planar undirected) graphs that don't have a cycle of length $\leq k$ (for any arbitrary fixed $k \geq 3$). An immediate corollary is that Hamiltonian cycle is still NPC on $(H_1,...,H_n)\text{-free}$ graphs in which every $H_i$ contains a cycle. But, the theorem is not so difficult, so I don't think it is a new result... let me know.
Marzio De Biasi
CC BY-SA 3.0
2014-06-16T13:42:19.390Z
I am not expert in graph theory, but your hamilitonian result appears very interesting to me because it gives broad results and many specific classes. Consider informing graphclasses.org about (C_4,triangle)-free:  http://graphclasses.org/classes/gc_911.html
joro
CC BY-SA 3.0
2014-06-16T15:24:16.690Z
Is $C_4$ a clique of four vertices? If yes, it seems that there are a lot of "unknown"s that are settled by the theorem. Perhaps I can ask on cstheory if the result is new or not.
Marzio De Biasi
CC BY-SA 3.0
2014-06-17T07:14:21.940Z
C_4 is cycle on 4 vertices (check the small graphs in graphclasses). If you ask me, ask if this is new or not :-) Did you gave up for 3-coloring gadgets?
joro
CC BY-SA 3.0
2014-06-17T11:01:01.930Z
Is this question worth asking:  The Overfull conjecture asserts that if a graph with large \Delta(G) has a certain subgraph then it is Class 2. This is a short certificate for Class 2 and a short certificate for Class 1 is \Delta coloring. So for these graphs coNP = NP, which means there are no hard coNP problems for these graphs (assuming the conjecture).
joro
CC BY-SA 3.0
2014-06-17T11:17:31.927Z
I'm not too familiar with graph coloring / Overfull conjecture :-( ... so I can't say if it can be relevant. I'll read more about it (and think about the k-coloring problem on $(H_1,..,H_n)\text{-free}$ graphs ...)
Marzio De Biasi
CC BY-SA 3.0
2014-06-17T13:29:23.387Z
If edge coloring large degree graphs is NP-complete, the overfull conjecture implies NP=coNP IMHO.
joro
CC BY-SA 3.0
2014-06-18T11:28:49.573Z
Asked about the overfull conjecture. Do you happen to have an edge coloring gadget that shows EC is NP-hard for graphs with $\Delta(G) \ge n/3$?
joro
CC BY-SA 3.0
2014-06-19T14:03:34.303Z
Can you parse this MO answer? Is it relevant at all:  https://mathoverflow.net/questions/172032/conjecture-for-perfect-graphs-the-fractional-chromatic-index-rounded-up-equals
joro
CC BY-SA 3.0
2014-07-12T10:48:31.700Z
GI relate graph transformation on MO:  https://mathoverflow.net/questions/175926/graph-transformation-related-to-graph-isomorphism
joro
CC BY-SA 3.0
2014-07-12T11:24:15.313Z
@joro: I'll take a closer look at it tomorrow. Perhaps Q1 can be proved by using the fact that G1,G2 are isomorphic if and only if their complements are isomorphic, and that "complementing" the edges between the two nodes of bipartite graphs preserves isomorphism. However, why didn't you post the question on cstheory?
Marzio De Biasi
CC BY-SA 3.0
2014-07-12T11:28:53.577Z
@MarzioDeBiasi Thanks. Not sure why I chose MO, would it be a great sin to crosspost after sometime unless it is not answered on MO?
joro
CC BY-SA 3.0
2014-06-13T20:14:53.363Z
2014-06-15T23:51:26.493Z
2014-06-15T23:51:26.493Z
Marzio De Biasi
<p>MAX-CUT remains NP-complete.</p>

<p><strong>Lemma 3.2</strong> simple max-cut is NP-complete in the following two classes of graphs:</p>

<p>graphs not containing cycles of length at most $k$, for every $k \ge 3$.</p>

<p>They are subdividing an edge twice.</p>

<p>From "MAX-CUT and containment relations in graphs, Marcin Kaminski"</p>

CC BY-SA 3.0
2014-06-24T14:26:44.580Z
But you asked for problems solved in polynomial time, right?
Peng O
CC BY-SA 3.0
2014-06-24T15:11:38.480Z
@PengO indeed, but this is negative result, so it is impossible to be polynomial. Another answer also shows negative results.
joro
CC BY-SA 3.0
2014-06-24T13:03:13.043Z
2014-06-24T13:03:13.043Z
joro
<p>Crossposted from <a href="https://mathoverflow.net/questions/171493/polynomial-problems-in-graph-classes-defined-by-forbidden-induced-cyclic-subgrap">MO</a>.</p>

<p>Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).</p>

<blockquote>
  <p>Are there NP-hard graph problems that can be solved in
  polynomial time for $C$ other than Clique and Clique
  cover?</p>
</blockquote>

<p>If I remember correctly, this is impossible for
independent set (unless $P=NP$).</p>

<p>Search in graphclasses.org didn't find any.</p>

<p>A class for which Clique and Clique cover are
polynomial is <a href="http://graphclasses.org/classes/gc_1022.html">C5,C6,X164,X165,sunlet4,triangle-free</a></p>

<p><strong>Edit</strong></p>

<p>Negative for IS and Domination is in <a href="http://www.sciencedirect.com/science/article/pii/S0304397505008327">this paper</a>. Page 2, the graphs $S_{i,j,k}$.</p>

CC BY-SA 3.0
2014-06-13T15:09:17.180Z
In [Stefan Kratsch, Pascal Schweitzer, Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs](http://arxiv.org/abs/1208.0142): GI is polynomial time (trivially) solvable for $(K_s, I_t)\text{-free}$ graphs, but also (less trivially) for $(K_s, K_{1,t})\text{-free}$ graphs.
Marzio De Biasi
CC BY-SA 3.0
2014-06-13T16:26:24.290Z
Perhaps it's best to note on the question on MO the cross posting as well, if anyone there is interested, they might like to see the answers/comments here.
R B
CC BY-SA 3.0
2014-06-13T20:06:56.997Z
@MarzioDeBiasi, why not turning your comment to answer?
Saeed
<cc.complexity-theory><graph-theory><graph-algorithms><co.combinatorics>
Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs
joro
# Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

(Asked by: username_0 on 2014-06-13)

Crossposted from [MO](https://mathoverflow.net/questions/171493/polynomial-problems-in-graph-classes-defined-by-forbidden-induced-cyclic-subgrap).

Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).

> Are there NP-hard graph problems that can be solved in
> polynomial time for $C$ other than Clique and Clique
> cover?

If I remember correctly, this is impossible for
independent set (unless $P=NP$).

Search in graphclasses.org didn't find any.

A class for which Clique and Clique cover are
polynomial is [C5,C6,X164,X165,sunlet4,triangle-free](http://graphclasses.org/classes/gc_1022.html)

**Edit**

Negative for IS and Domination is in [this paper](http://www.sciencedirect.com/science/article/pii/S0304397505008327). Page 2, the graphs $S\_{i,j,k}$.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, co.combinatorics
> **Comments:**
> **username_1**: In [Stefan Kratsch, Pascal Schweitzer, Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs](http://arxiv.org/abs/1208.0142): GI is polynomial time (trivially) solvable for $(K_s, I_t)\text{-free}$ graphs, but also (less trivially) for $(K_s, K_{1,t})\text{-free}$ graphs.  
> **username_2**: Perhaps it's best to note on the question on MO the cross posting as well, if anyone there is interested, they might like to see the answers/comments here.  
> **username_3**: @MarzioDeBiasi, why not turning your comment to answer?  

---

## 4 answers

### Answer by username_4 on 2014-06-14. Score: 14

I think there is a number of hard problems that become easy for triangle-free graphs; especially those deal directly with triangles such as Partition Into Triangles (Does G have a partition into triangles?). Other less trivial examples include:

* Stable Cutset Problem (Does G have an independent set S such that G-S is disconnected?). See:  *On stable sutsets in graphs,* Discrete Applied Math. 105 (2000) 39-50.
* Intersection Graph Basis (Is G the intersection graph of subsets of a k-element ground set?). See: Problem [GT59] in: Garey & Johnson, *Computers and Intractability: A Guide to the Theory of NP-Completeness.*


---

### Answer by username_5 on 2014-06-17. Score: 11

Here are some additional examples to Mon Tag's answer :

* The Disconnected Cutset problem (Does $G$ admit a set of vertices $S$ such that $G-S$ and the subgraph of $G$ induced by $S$ are disconnected) is NP-complete (see [here](http://dx.doi.org/10.1007/978-3-642-23786-7_43)). It is easy to see that this problem is polynomially solvable for triangle-free graphs (hence also the Stable Cutset problem as mentioned by Mon Tag).
* Recognizing triangular line graphs is NP-complete (see [here](http://www.sciencedirect.com/science/article/pii/S0012365X11005449)), It is also
  easy to see that this problem becomes polynomially for triangle-free input graphs.
* Computing the maximum connected matching is hard (see [here](http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1206).
  A matching is connected if, for any pair of the matching edges, there is another edge of the graph incident to both of them).
  It can be proved that this problem is polynomially solvable for $(C\_3, C\_4, C\_5)$-free graphs.

> **Comments:**
> **username_0**: Thank you. So some problems remain hard and others don't.  

---

### Answer by username_1 on 2014-06-13. Score: 10

From the comment above: in [Stefan Kratsch, Pascal Schweitzer, Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs](http://arxiv.org/abs/1208.0142): GI is polynomial time (trivially) solvable for $(K\_s,I\_t)\text{-free}$ graphs, but also (less trivially) for $(K\_s,K\_{1,t})\text{-free}$ graphs.

**EDIT**: as noted in the comment, $K\_{1,t}$ doesn't contain a cycle (I read the introduction of the paper too quickly).

After thinking a little bit about it, it seems easy to prove the following (original?):

**NEGATIVE RESULT:** *for every finite set $\{H\_1,...H\_k\}$ in which every $H\_i$ contains a cycle, the problem of graph isomorphism (GI) restricted to the class $\mathcal{C}$ of $(H\_1,...,H\_k)\text{-free}$ graphs is GI-complete.*

*Proof:* Fixed a class of $(H\_1,...,H\_k)\text{-free}$ graphs in which each $H\_i$ contains a cycle, and given $G\_1,G\_2$, let $r$ be the length of the longest cycle of the $H\_i$s. Replace each edge $(u,v)$ of $G\_1,G\_2$ with a path of length $l = \lceil r/3 \rceil$ adding $l$ new nodes $(u,p\_1,p\_2,...,p\_l,v)$ (see figure below). By construction the new graphs $G'\_1, G'\_2$ are $(H\_1,...,H\_k)\text{-free}$ indeed the possible shortest cycles are those formed by a triangle that must have length $3\lceil r/3 \rceil + 3 > r$; and it is easy to prove that they are isomorphic if and only if the original $G\_1,G\_2$ are isomorphic.

![enter image description here](https://i.sstatic.net/IoPq3.png)
  
**Figure**: a graph $G\_1$ on the left, and the equivalent $(H\_1,...,H\_k)\text{-free}$ graph $G'\_1$ on the right (suppose that the longest cycle of the $H\_i$ has length $r=15$, so every edge of $G\_1$ is replaced with a path of length $l = 5$.

We can also extend the negative result to Hamiltonian cycle NPC problem, indeed it is an immediate corollary to the following (original?):

**Theorem**: for any $k \geq 3$, the Hamiltonian cycle problem remains NP-complete even if we the graph $G$ does not contain cycles of length $\leq k$.

*Proof* We know that the Hamiltonian cycle problem is NPC even on a planar directed graph $G$ with each node $v$ satisfying: $outdeg(v) + indeg(v) \leq 3$ (Papdimitriou and Vazirani, On Two Geometric Problems Related to the Travelling Salesman Problem).
We can transform the graph $G$ to an undirectde graph $G'$ simply adding a node on the incoming edge of nodes $v$ that have $indeg(v )=1$, and to the outgoing edge of nodes $v$ that have $indeg(v)=2$.
Then we can replace the nodes of $G'$ with the gadget in the figure below. It is easy to see that there are only two valid traversals (*zigzags*) that visit each node of the gadget exactly once (red and green paths in the figure): the gadgets cannot be traversed from top-to-bottom, otherwise the horizontal (incoming or outgoing) path would be cut out.
Furthermore we can place enough nodes on the vertical/horizontal segments of the gadgets, and extend the number of its zigzags, to ensure that no cycle of length $\geq k$ is possible in the gadget or in a triangle of 3 gadgets linked together. This assures that if the resulting graph $G''$ has an Hamiltonian cycle, then the original graph $G$ has also an Hamiltonian cycle (the converse is immediate by construction of the gadget).

![enter image description here](https://i.sstatic.net/uw6oT.png)

**Corollary:** Hamiltonian cycle and path problems remain NP-complete even if restricted to $(H\_1,...,H\_k)\text{-free}$ graphs, where every $H\_i$ contains a cycle.

> **Comments:**
> **username_0**: Thank you. $K_{1,t}$ is tree, so it is not cyclic or am I missing something?  
> **username_1**: You're right! I came up with a negative result ... see if it can work, or if it is completely wrong :-S :-S  
> **username_0**: Thanks. So you got alleged negative result for GI AND Hamiltonian cycle?  
> **username_0**: Hope this is correct, this will solve a lot unknown to graphclasses.org problems.  
> **username_1**: Yes, the negative result extends to Hamiltonian cycle/path and probably to other related classes of NPC problems (e.g. TSP). ... mmm ... but if it solves *a lot of unknown problems* then (by experience) there are high chances that it is wrong :-) :-)  
> **username_0**: If I find the paper it will give negative result for IS and Dominating set.  
> **username_1**: Let me know if it can be interesting/new: I already used similar gadgets (similar to the one in the bottom figure) for planar graphs, and I can try to sketch a formal proof.  
> **username_0**: I though about replacing edges with gadgets too. To my knowledge this is original and interesting (and graphclasses.org suggests this is original). What about 3-COLOR gadget?  
> **username_0**: I asked a question about your GI paper. If you exclude sufficiently large graphs it becomes poly :)))  
> **username_1**: @joro: I'll think about 3-coloring, too!!! What do you mean with "if you exclude sufficiently large graphs it becomes poly"?  
> **username_0**: Good luck with 3-coloring :) You wrote GI is poly for $(K_s,K_{1,t})\text{-free}$. If you take $s,t$ large enough the graph certainly will be free. The answer in the other question shows the paper means "poly in $s,t$".  
> **username_0**: I think for GI simpler is to subdivide every edge $r$ times where $r$ is the largest cycle in $H_i$ (not necessarily induced). This forbids induced cycles of length $ < r + 1$.  
> **username_0**: I think edge gadgets won't work for HC since they will involve Eulerian cycle.  
> **username_0**: btw, is there non-trivial class of digraphs where digraph isomorphism is in P? What about directed $P_4$ free?  
> **username_1**: @joro: you're right, subdividing edges is simpler :-) ... and because the shortest cycle is a 3-nodes clique, you can replace each edge with a path of length $\lceil r/3 \rceil$  
> **username_3**: Just a nitpick, each of cycle should be sth like $(m+1)d_i$ where $d_i$ is a degree of vertex $i$, otherwise your iff part is not nesscesarry correct, may be $G_1,G_2$ are isomorphic but not $G'_1,G'_2$.  
> **username_1**: @Saeed: you're right; however the reduction suggested by joro is even simpler (replace every edge with a path of $\lceil r/3 \rceil$). I'll soon, update the answer and add the gadget for the negative result for Hamiltonian cycle.  
> **username_0**: Don't think your conversion from directed to undirected preserves hamiltonicity, since you add vertices on edges. By adding a vertex on edge don't you force the directed edge to be on the HC of the digraph? (Don't think the GI construction is original, check forbidden subgraph here: https://cs.uwaterloo.ca/research/tr/1977/CS-77-04.pdf  
> **username_1**: @joro: yes it is correct (I just copied it from papadimitriou's paper). They key point is that the node is added on an edge that in a directed Hamiltonian path MUST be traversed.  
> **username_0**: So all vertices you add are on edge that must be on the HC? You know a lot of edges of the HC of the digraph.  
> **username_1**: @joro: we are talking about DIRECTED hamiltonian cycle on a graph in which every node has $outdeg(v)+indeg(v) \leq 3$ (see paper), and in a node $v$ that has only one incoming edge (top left figure), that edge MUST be traversed;  in a node $v$ that has only one outgoing edge (top right figure), that edge MUST be traversed. Let me know if it is not clear.  
> **username_0**: OK, let me first see the paper. Well might be wrong. If correct this a broad result :-)))  
> **username_0**: Browsing the paper you have $\Delta=3$?  
> **username_1**: What is $\Delta$? (yes, if you mean the max degree of the undirected equivalent graph $G'$). To summarize: in the theorem above, I give a reduction from Hamiltonian cycle on planar directed graphs in which indeg(v)+outdeg(v)<=3 to the Hamiltonian cycle problem on (planar undirected) graphs that don't have a cycle of length $\leq k$ (for any arbitrary fixed $k \geq 3$). An immediate corollary is that Hamiltonian cycle is still NPC on $(H_1,...,H_n)\text{-free}$ graphs in which every $H_i$ contains a cycle. But, the theorem is not so difficult, so I don't think it is a new result... let me know.  
> **username_0**: I am not expert in graph theory, but your hamilitonian result appears very interesting to me because it gives broad results and many specific classes. Consider informing graphclasses.org about (C_4,triangle)-free:  http://graphclasses.org/classes/gc_911.html  
> **username_1**: Is $C_4$ a clique of four vertices? If yes, it seems that there are a lot of "unknown"s that are settled by the theorem. Perhaps I can ask on cstheory if the result is new or not.  
> **username_0**: C_4 is cycle on 4 vertices (check the small graphs in graphclasses). If you ask me, ask if this is new or not :-) Did you gave up for 3-coloring gadgets?  
> **username_0**: Is this question worth asking:  The Overfull conjecture asserts that if a graph with large \Delta(G) has a certain subgraph then it is Class 2. This is a short certificate for Class 2 and a short certificate for Class 1 is \Delta coloring. So for these graphs coNP = NP, which means there are no hard coNP problems for these graphs (assuming the conjecture).  
> **username_1**: I'm not too familiar with graph coloring / Overfull conjecture :-( ... so I can't say if it can be relevant. I'll read more about it (and think about the k-coloring problem on $(H_1,..,H_n)\text{-free}$ graphs ...)  
> **username_0**: If edge coloring large degree graphs is NP-complete, the overfull conjecture implies NP=coNP IMHO.  
> **username_0**: Asked about the overfull conjecture. Do you happen to have an edge coloring gadget that shows EC is NP-hard for graphs with $\Delta(G) \ge n/3$?  
> **username_0**: Can you parse this MO answer? Is it relevant at all:  https://mathoverflow.net/questions/172032/conjecture-for-perfect-graphs-the-fractional-chromatic-index-rounded-up-equals  
> **username_0**: GI relate graph transformation on MO:  https://mathoverflow.net/questions/175926/graph-transformation-related-to-graph-isomorphism  
> **username_1**: @joro: I'll take a closer look at it tomorrow. Perhaps Q1 can be proved by using the fact that G1,G2 are isomorphic if and only if their complements are isomorphic, and that "complementing" the edges between the two nodes of bipartite graphs preserves isomorphism. However, why didn't you post the question on cstheory?  
> **username_0**: @MarzioDeBiasi Thanks. Not sure why I chose MO, would it be a great sin to crosspost after sometime unless it is not answered on MO?  

---

### Answer by username_0 on 2014-06-24. Score: 1

MAX-CUT remains NP-complete.

**Lemma 3.2** simple max-cut is NP-complete in the following two classes of graphs:

graphs not containing cycles of length at most $k$, for every $k \ge 3$.

They are subdividing an edge twice.

From "MAX-CUT and containment relations in graphs, Marcin Kaminski"

> **Comments:**
> **username_6**: But you asked for problems solved in polynomial time, right?  
> **username_0**: @PengO indeed, but this is negative result, so it is impossible to be polynomial. Another answer also shows negative results.  

---

