11
$\begingroup$

Crossposted from MO.

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

Edit

Negative for IS and Domination is in this paper. Page 2, the graphs $S_{i,j,k}$.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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). 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), 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. 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.

$\endgroup$
  • $\begingroup$ Thank you. So some problems remain hard and others don't. $\endgroup$ – joro Jun 18 '14 at 9:11
10
$\begingroup$

From the comment above: in Stefan Kratsch, Pascal Schweitzer, Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs: 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
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

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.

$\endgroup$
  • $\begingroup$ Thank you. $K_{1,t}$ is tree, so it is not cyclic or am I missing something? $\endgroup$ – joro Jun 14 '14 at 6:49
  • $\begingroup$ You're right! I came up with a negative result ... see if it can work, or if it is completely wrong :-S :-S $\endgroup$ – Marzio De Biasi Jun 14 '14 at 10:02
  • $\begingroup$ Thanks. So you got alleged negative result for GI AND Hamiltonian cycle? $\endgroup$ – joro Jun 14 '14 at 10:56
  • $\begingroup$ Hope this is correct, this will solve a lot unknown to graphclasses.org problems. $\endgroup$ – joro Jun 14 '14 at 11:03
  • 1
    $\begingroup$ 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$. $\endgroup$ – Saeed Jun 15 '14 at 20:08
1
$\begingroup$

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"

$\endgroup$
  • 1
    $\begingroup$ But you asked for problems solved in polynomial time, right? $\endgroup$ – Peng O Jun 24 '14 at 14:26
  • $\begingroup$ @PengO indeed, but this is negative result, so it is impossible to be polynomial. Another answer also shows negative results. $\endgroup$ – joro Jun 24 '14 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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