Thursday, 30 October 2008

computational complexity - How unhelpful is graph minors theorem?

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.

No comments:

Post a Comment