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

  1. it is indeed hard to test this property of a graph
  2. the theorem does turn easily testable properties into long lists
  3. 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$?


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.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ Yes, this is the argument one can make about 2 and 3, but I suspect there would be equally valid arguments with the contrary view. $\endgroup$ – Ilya Nikokoshev Jan 1 '10 at 3:24
  • 3
    $\begingroup$ Cant we test quickly if a graph is embeddable in a surface of genus 5 (say)? $\endgroup$ – Gil Kalai Jan 1 '10 at 11:10
  • 2
    $\begingroup$ @Gil: Yes, there exist linear time algorithms for bounded-genus embedding (e.g. Kawarabayashi, Mohar, and Reed, FOCS'08, doi:10.1109/FOCS.2008.53) but I don't think the forbidden minors are known for all bounded genus embeddings. $\endgroup$ – David Eppstein Jan 1 '10 at 18:18
  • 1
    $\begingroup$ As for "the polynomial is like O(n log n)": Reed has claimed something like this, I think, but until he actually publishes the full details I think we have to rely on the O(n^3) Robertson–Seymour algorithm from Graph Minors XIII, doi:10.1006/jctb.1995.1006. $\endgroup$ – David Eppstein Jan 1 '10 at 18:23
  • 9
    $\begingroup$ Reed has been claiming an O(n^2) algorithm for years without publishing details and has now moved up to claiming O(n log n). I think that making such claims without backing them up does serious damage to the subject since it throws into doubt anything that relies on the claims and prevents others from working on the problem and actually publishing their algorithms. $\endgroup$ – David Eppstein Jan 1 '10 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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