How unhelpful is graph minors theorem? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T10:47:16Z http://mathoverflow.net/feeds/question/10279 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10279/how-unhelpful-is-graph-minors-theorem How unhelpful is graph minors theorem? Ilya Nikokoshev 2009-12-31T15:10:48Z 2010-01-02T03:18:24Z <p>A very interesting <a href="http://en.wikipedia.org/wiki/Robertson-Seymour%5Ftheorem" rel="nofollow">Robertson-Seymour (graphs minors) theorem</a> says:</p> <blockquote> <p>Any infinite collection of graphs $C$ with the property that if $G\in C$ then its minors also are has the form <code>$\{$</code>graphs $G$ that don't contain any <code>$E_i\}$</code> for some <em>finite</em> collection <code>$E = \{E_i\}$</code>.</p> </blockquote> <p>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.</p> <p>I wonder whether the above difficulty is because </p> <ol> <li>it is indeed hard to test this property of a graph</li> <li>the theorem does turn easily testable properties into long lists</li> <li>it is not known how to effectively turn easily testable properties into lists</li> </ol> <p>Here's the formal question:</p> <blockquote> <p>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$?</p> </blockquote> http://mathoverflow.net/questions/10279/how-unhelpful-is-graph-minors-theorem/10302#10302 Answer by David Eppstein for How unhelpful is graph minors theorem? David Eppstein 2009-12-31T18:10:09Z 2010-01-01T08:48:13Z <p>For a reference concerning this problem, see <a href="http://dx.doi.org/10.1016/S0304-3975%2897%2900300-9" rel="nofollow">Cattell et al, "On computing graph minor obstruction sets", Theor. Comput. Sci. 2000</a>.</p> <p>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).</p> <p>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.</p> http://mathoverflow.net/questions/10279/how-unhelpful-is-graph-minors-theorem/10320#10320 Answer by Rune for How unhelpful is graph minors theorem? Rune 2009-12-31T20:31:14Z 2010-01-02T03:18:24Z <p>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.)</p> <p>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.</p> <p><strong>EDIT</strong>: I've been corrected in the comments. Please read Gil Kalai and David Eppstein's comments.</p>