If a family of forbidden subgraphs is hard, does that imply that the graph class is hard? « Stack Exchange Theoretical Computer Science Blog

If a family of forbidden subgraphs is hard, does that imply that the graph class is hard?

2011-08-10 by . 0 comments

Post to Twitter

The previous graph theory post mentioned the concept of forbidden minors — a class of graphs that contains no minors of a particular type.  We can also, of course, consider the notion of forbidden subgraphs, in which a graph class $latex \mathcal{C}$ is defined by avoidance of another graph class $latex \mathcal{H}$: graph $latex G$ is a member of $latex \mathcal{C}$ iff $latex G$ contains no subgraph that is a member of $latex \mathcal{H}$.  A partial list of graph classes defined in this way can be found here.

Suppose the forbidden subgraph family $latex \mathcal{H}$ is finite.  If we want to check whether $latex G \in \mathcal{C}$ “all we have to do” is to confirm that $latex G$ does not contain finitely many subgraphs of a particular type, which can be done in time polynomial in the size of $latex G$.  While this has tremendous real-world applications, it also lands us in the world of “nonconstructive polynomial time”: there are graph classes that are provably characterized by finite forbidden families, and yet, we don’t know what the families are.  Moreover, there may be no reasonable way to find out, as shown by the following theorem of Fellows and Langston:

Theorem: There is no algorithm to compute, from a finite description of a minor-closed family represented by a Turing machine that accepts precisely the graphs in the family, the set of obstructions for that family.

I will turn now to a question about what happens when the forbidden family is infinite but easy (or hard) to recognize.  Nonconstructive polynomial time, and the use of finite forbidden family characterization in graph algorithms, is dealt with in more detail in many places, including Algorithmic Implications of the Graph Minor Theorem, by Bienstock and Langston.

Consider chordal graphs, which are graphs where every cycle of length four or more contains a chord, that is to say, an edge between two vertices that are part of the cycle.  So chordal graphs have a simple forbidden graph characterization: no subgraphs that are cycles of size four or more with no chords.  This is an infinite forbidden family, but one that is computationally simple to recognize.  Of course, not all graph classes are simple to recognize, which motivated Vincius Santos to ask the question on CSTheory: is there a relationship between the computational complexity of recognizing a forbidden family of subgraphs, and the computational complexity of the graph class defined by the forbidden family?

Hugo Nobrega gave a remarkable answer to this question, but I wanted to blog about this question both to publicize the answer, and also because the original question remains open.  Nobrega’s answer boils down to “probably not,” though it provides a beautiful example that shows any straightforward “intuitions” will not work.  Perhaps someone reading this blog knows the answer, or has further insight.  If you know any work in this direction, please do leave a comment on the post, or on the original question.  Nobrega’s answer is brief enough that I will reproduce it in full (lightly edited).

Although it seems intuitive that the list of forbidden (induced) subgraphs for a class $latex \mathcal{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 $latex \mathcal{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 $latex u$ of the cycle, and one adjacent to a vertex $latex v$ of the cycle, where $latex u$ and $latex v$ are not consecutive in the cycle (and no other edges).

Now let $latex \mathcal{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 $latex u$ of the cycle (as before), but now two adjacent to the same vertex $latex v$ of the cycle, where again $latex u$ and $latex v$ are not consecutive.

Then the class of graphs which has $latex \mathcal{F}$ as the forbidden induced subgraphs has polynomial-time recognition, whereas the recognition of the class which has $latex \mathcal{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” $latex \mathcal{F}$ and $latex \mathcal{F}^*$ above.

That’s a remarkable example, but of course not a conclusive proof.  There is more discussion in the comments on the answer (and in other, less upvoted answers) about possible approaches for a full resolution of Santos’s question.  I must say, I would love to know the answer myself!

Filed under Answer of the Week

Subscribe to comments with RSS.

Comments have been closed for this post