How unhelpful is graph minors theorem? - MathOverflow

How unhelpful is graph minors theorem?

2009-12-31T15:10:48Z

A very interesting Robertson-Seymour (graphs minors) theorem says:

Any infinite collection of graphs $C$ with the property that if $G\in C $ then its minors also are has the form $\{$ graphs $G$ that don't contain any $E_i\}$ for some finite collection $E = \{E_i\}$ .

So, the theorem says that you could create a list of forbidden minors to find out if the graph is torically embeddable, but this doesn't help much, since the list is both not fully known and large.

I wonder whether the above difficulty is because

it is indeed hard to test this property of a graph
the theorem does turn easily testable properties into long lists
it is not known how to effectively turn easily testable properties into lists

Here's the formal question:

Consider a polynomial algorithm $P$ that returns a yes/no question given a graph as an input and which always returns yes for minors of any graph for which it returns yes. There exists $E$, the exceptional list of a collection defined by $P$. What is known about the computability of the map $P\mapsto E$?

Answer by David Eppstein for How unhelpful is graph minors theorem?

2009-12-31T18:10:09Z

For a reference concerning this problem, see Cattell et al, "On computing graph minor obstruction sets", Theor. Comput. Sci. 2000.

I think the answer to your specific question is that it's recursively enumerable (one can test all graphs using P to see whether they belong to E) but not recursive (without further information there is no way of knowing that one has found all obstructions).

Here's a specific construction that shows this: given an instance h of the halting problem, construct an algorithm A that either recognizes all graphs if h is a non-halting instance, or that recognizes the graphs with no K_s minor if h halts in s steps. It's not hard to do this in such a way that A is always a polynomial time algorithm, but one can't tell whether E is empty or non-empty without solving the halting problem.

Answer by Rune for How unhelpful is graph minors theorem?

2009-12-31T20:31:14Z

To answer some of your questions: 1. Yes, testing such properties is usually hard. For instance, before the graph minors theorem we had properties for which no algorithm was known at all! (Maybe a recursively enumerable algorithm was known, I don't remember.) After the graph-minors theorem, such properties became testable in polynomial time! Now that's a big jump from no algorithm known to polynomial time. (If I remember correctly, the polynomial is like O(n log n), which is almost linear time.)

As for 2. and 3., I don't know any property which we can easily test, for which we don't know the forbidden minors. I'd like to know such properties, if they are known. It seems to me that if we have an algorithm for easily testing a property, we really understand the property, and therefore should be able to come up with a list of forbidden minors somehow. Of course, this is just a feeling.

EDIT: I've been corrected in the comments. Please read Gil Kalai and David Eppstein's comments.