<p>The answer by @Hugo is really nice, and here I want to add some personal opinions.</p>

<p>There are related families similar to the graphs in the family F and F'. The graphs in family B1 in the article are usually called pyramids. And graphs in family B2 are usually called prisms. See <a href="https://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity/2752#2752">the answer here</a> for an illustration.
In the literature of induced subgraph detection problems, they were used for detecting even/odd holes, which are chordless cycles with even/odd length. By the celebrated strong perfect graph theorem, a graph G is perfect if both G and the complement of G do not contain odd holes.</p>

<p>For the families of pyramids and prisms, in fact there are differences between them - one has an induced subtree of three leaves, and the other one does not. This is called the <a href="http://www.columbia.edu/~mc2775/threeinatree.pdf" rel="nofollow noreferrer">"three-in-a-tree" problem</a>, which has been studied by Chudnovsky and Seymour. It is surprising that determining if there is an induced tree which contains three given nodes is tractable, while the "four-in-a-centered-tree" problem <a href="http://perso.ens-lyon.fr/nicolas.trotignon/articles/ftree.pdf" rel="nofollow noreferrer">is NP-hard</a>. (A centered tree is a tree with at most one node with degree greater than 2.)  The differences between F and F' seems to be caused by the same reason.</p>

<p>But it seems that a complete characterization is still hard, because we do not even know the complexity of detecting graphs in some of the families that looks simple enough, like odd-hole-free graphs(!). 
And for the families that we do know a polynomial-time algorithm exists, like perfect graphs and even-hole-free graphs, although there are general strategies (based on decompositions) to design an algorithm, one has to provide a specific structural theorem for them. This is usually a family-dependent process, and most of the time the proofs are really long. (<a href="http://www.dainf.ct.utfpr.edu.br/~murilo/star.pdf" rel="nofollow noreferrer">Here's an example</a> for the even-hole-free graph, where the paper are over 90 pages.)</p>

<p>Still it would be interesting to have some classifications for induced subgraph detection problems, in the sense like the three-in-a-tree problem.</p>

CC BY-SA 4.0
2020-09-16T10:23:12.030Z
It seems that the complexity of finding odd holes has been resolved: they can be found in polynomial time: https://doi.org/10.1145/3375720
Christian Komusiewicz
CC BY-SA 3.0
2011-07-13T07:17:20.877Z
2011-07-14T01:18:12.947Z
2017-04-13T12:32:28.080Z
Hsien-Chih Chang 張顯之
<p>Although it seems intuitive that the list of forbidden (induced) subgraphs for a class $\mathscr{C}$ of graphs which has NP-hard recognition <em>should</em> possess some "intrinsic" complexity, I have recently found some striking negative evidence to this intuition in the literature.</p>

<p>Perhaps the simplest to describe is the following, taken from <a href="http://dx.doi.org/10.1016/j.dam.2009.02.015">an article by B. Lévêque, D. Lin, F. Maffray and N. Trotignon</a>.</p>

<p>Let $F$ be the family of graphs which are composed of a cycle of length at least four, plus three vertices: two adjacent to the same vertex $u$ of the cycle, and one adjacent to a vertex $v$ of the cycle, where $u$ and $v$ are not consecutive in the cycle (and no other edges).</p>

<p>Now let $F&#39;$ be the family of graphs which are composed exactly the same way, except that you add <em>four</em> vertices: two adjacent to the same vertex $u$ of the cycle (as before), but now <em>two</em> adjacent to the same vertex $v$ of the cycle, where again $u$ and $v$ are not consecutive.</p>

<p>Then the class of graphs which has $F$ as the forbidden induced subgraphs has polynomial-time recognition, whereas the recognition of the class which has $F&#39;$ as the forbidden induced subgraphs is NP-hard.</p>

<p>Therefore, I find it hard to conceive of any <em>general</em> condition that a list of forbidden induced subgraphs has to satisfy when it results in a class with (NP-) hard recognition, considering that such a condition will have to separate the "very similar" $F$ and $F&#39;$ above.</p>

CC BY-SA 3.0
2011-07-05T20:57:35.440Z
Nice answer - that's quite delicate.
Suresh Venkat
CC BY-SA 3.0
2011-07-06T00:04:36.040Z
Interesting. Is there any chance that this would have something to do with the expressivity of the logic required to describe the pattern? I'm thinking of something like for formal languages where the complexity of a language can be equivalently characterized by the way it is defined (regexp, formal grammar...) or the machine required to recognize it (automaton, pushdown...) or the expressivity of the logic required to write a formula characterizing the words of the language (MSO for regular languages, for instance).
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2011-07-06T02:38:23.400Z
That's an interesting idea, but again I can't help but think that $F$ and $F'$ are *so* close that it's hard to imagine a way of "separating" them like that (say by $F$ being describable in a language that $F'$ is not).

I could just be overly negative though..! I am admittedly going on "intuition" here so I'd be glad to be proved wrong.
Hugo Nobrega
CC BY-SA 3.0
2011-07-13T22:00:52.527Z
@Hugo: one tangible difference between them is the symmetry in the characterization of $F'$ - there's inherently no means of distinguishing between the vertices $u$ and $v$.  What happens if you consider the family $F_0$ of cycles of length at least four, plus _two_ additional vertices, adjacent to non-consecutive verts in the cycle?  Does restoring symmetry the 'other' direction (removing a vert from $F$ rather than adding one) make it hard again?
Steven Stadnicki
CC BY-SA 3.0
2011-07-14T01:27:46.370Z
@Steven: I guess not, one can detect graphs in $F_0$ by randomly guessing 8 nodes, forming both sides of the graph, and perform three-in-a-tree algorithm on three nodes, like the one in Theorem 3.1. This gives a polynomial-time algorithm for detecting $F_0$.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-08-10T17:11:40.667Z
This answer is [featured](http://is.gd/CImtKT) on the CSTheory Community Blog.
Aaron Sterling
CC BY-SA 3.0
2011-07-04T17:27:50.200Z
2011-07-04T17:27:50.200Z
Hugo Nobrega
<p>I'm considering graph classes that can be characterized by forbidden subgraphs.</p>

<p>If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm (one can just use brute force). But an infinite family of forbidden subgraphs does not imply hardness: there are some classes with infinite list of forbidden subgraphs such that the recognition can also be tested in polynomial time. Chordal and Perfect graphs are examples but, in those cases, there is a "nice" structure on the forbidden family.</p>

<p>Is there any know relation between the hardness of the recognition of a class and the "bad behavior" of the forbidden family? Such a relation should exist? This "bad behavior" has been formalized somewhere?</p>

<cc.complexity-theory><graph-theory><np-hardness>
Relation between hardness of recognition of a graph class and forbidden subgraph characterization
Vinicius dos Santos
# Relation between hardness of recognition of a graph class and forbidden subgraph characterization

(Asked by: username_0 on 2011-07-02)

I'm considering graph classes that can be characterized by forbidden subgraphs.

If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm (one can just use brute force). But an infinite family of forbidden subgraphs does not imply hardness: there are some classes with infinite list of forbidden subgraphs such that the recognition can also be tested in polynomial time. Chordal and Perfect graphs are examples but, in those cases, there is a "nice" structure on the forbidden family.

Is there any know relation between the hardness of the recognition of a class and the "bad behavior" of the forbidden family? Such a relation should exist? This "bad behavior" has been formalized somewhere?

**Tags:** cc.complexity-theory, graph-theory, np-hardness

---

## 2 answers

### Answer by username_3 on 2011-07-04. Score: 33 | Accepted answer

Although it seems intuitive that the list of forbidden (induced) subgraphs for a class $\mathscr{C}$ of graphs which has NP-hard recognition *should* possess some "intrinsic" complexity, I have recently found some striking negative evidence to this intuition in the literature.

Perhaps the simplest to describe is the following, taken from [an article by B. Lévêque, D. Lin, F. Maffray and N. Trotignon](http://dx.doi.org/10.1016/j.dam.2009.02.015).

Let $F$ be the family of graphs which are composed of a cycle of length at least four, plus three vertices: two adjacent to the same vertex $u$ of the cycle, and one adjacent to a vertex $v$ of the cycle, where $u$ and $v$ are not consecutive in the cycle (and no other edges).

Now let $F'$ be the family of graphs which are composed exactly the same way, except that you add *four* vertices: two adjacent to the same vertex $u$ of the cycle (as before), but now *two* adjacent to the same vertex $v$ of the cycle, where again $u$ and $v$ are not consecutive.

Then the class of graphs which has $F$ as the forbidden induced subgraphs has polynomial-time recognition, whereas the recognition of the class which has $F'$ as the forbidden induced subgraphs is NP-hard.

Therefore, I find it hard to conceive of any *general* condition that a list of forbidden induced subgraphs has to satisfy when it results in a class with (NP-) hard recognition, considering that such a condition will have to separate the "very similar" $F$ and $F'$ above.

> **Comments:**
> **username_4**: Nice answer - that's quite delicate.  
> **username_5**: Interesting. Is there any chance that this would have something to do with the expressivity of the logic required to describe the pattern? I'm thinking of something like for formal languages where the complexity of a language can be equivalently characterized by the way it is defined (regexp, formal grammar...) or the machine required to recognize it (automaton, pushdown...) or the expressivity of the logic required to write a formula characterizing the words of the language (MSO for regular languages, for instance).  
> **username_3**: That's an interesting idea, but again I can't help but think that $F$ and $F'$ are *so* close that it's hard to imagine a way of "separating" them like that (say by $F$ being describable in a language that $F'$ is not).  I could just be overly negative though..! I am admittedly going on "intuition" here so I'd be glad to be proved wrong.  
> **username_6**: @Hugo: one tangible difference between them is the symmetry in the characterization of $F'$ - there's inherently no means of distinguishing between the vertices $u$ and $v$.  What happens if you consider the family $F_0$ of cycles of length at least four, plus _two_ additional vertices, adjacent to non-consecutive verts in the cycle?  Does restoring symmetry the 'other' direction (removing a vert from $F$ rather than adding one) make it hard again?  
> **username_1**: @Steven: I guess not, one can detect graphs in $F_0$ by randomly guessing 8 nodes, forming both sides of the graph, and perform three-in-a-tree algorithm on three nodes, like the one in Theorem 3.1. This gives a polynomial-time algorithm for detecting $F_0$.  
> **username_7**: This answer is [featured](http://is.gd/CImtKT) on the CSTheory Community Blog.  

---

### Answer by username_1 on 2011-07-13. Score: 8

The answer by @Hugo is really nice, and here I want to add some personal opinions.

There are related families similar to the graphs in the family F and F'. The graphs in family B1 in the article are usually called pyramids. And graphs in family B2 are usually called prisms. See [the answer here](https://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity/2752#2752) for an illustration.
In the literature of induced subgraph detection problems, they were used for detecting even/odd holes, which are chordless cycles with even/odd length. By the celebrated strong perfect graph theorem, a graph G is perfect if both G and the complement of G do not contain odd holes.

For the families of pyramids and prisms, in fact there are differences between them - one has an induced subtree of three leaves, and the other one does not. This is called the ["three-in-a-tree" problem](http://www.columbia.edu/~mc2775/threeinatree.pdf), which has been studied by Chudnovsky and Seymour. It is surprising that determining if there is an induced tree which contains three given nodes is tractable, while the "four-in-a-centered-tree" problem [is NP-hard](http://perso.ens-lyon.fr/nicolas.trotignon/articles/ftree.pdf). (A centered tree is a tree with at most one node with degree greater than 2.) The differences between F and F' seems to be caused by the same reason.

But it seems that a complete characterization is still hard, because we do not even know the complexity of detecting graphs in some of the families that looks simple enough, like odd-hole-free graphs(!).
And for the families that we do know a polynomial-time algorithm exists, like perfect graphs and even-hole-free graphs, although there are general strategies (based on decompositions) to design an algorithm, one has to provide a specific structural theorem for them. This is usually a family-dependent process, and most of the time the proofs are really long. ([Here's an example](http://www.dainf.ct.utfpr.edu.br/~murilo/star.pdf) for the even-hole-free graph, where the paper are over 90 pages.)

Still it would be interesting to have some classifications for induced subgraph detection problems, in the sense like the three-in-a-tree problem.

> **Comments:**
> **username_2**: It seems that the complexity of finding odd holes has been resolved: they can be found in polynomial time: https://doi.org/10.1145/3375720  

---

