24
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
33
$\begingroup$

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.

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.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Nice answer - that's quite delicate. $\endgroup$
    – Suresh Venkat
    Jul 5, 2011 at 20:57
  • $\begingroup$ 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). $\endgroup$
    – a3nm
    Jul 6, 2011 at 0:04
  • 3
    $\begingroup$ 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. $\endgroup$
    – Hugo Nobrega
    Jul 6, 2011 at 2:38
  • $\begingroup$ @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? $\endgroup$
    – Steven Stadnicki
    Jul 13, 2011 at 22:00
  • $\begingroup$ @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$. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Jul 14, 2011 at 1:27
8
$\begingroup$

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

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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