[Computational Complexity] More on Graph Minors
- Guest post by Vahan Mkrtchyan
(Sequel to Graph Minor Theorem Post)
When I was a student my supervisor used to explain me that one of the reasons why the P vs NP problem was not solved and why it could not be solved in near future, was the lack of techniques for proving the pure existence of polynomial algorithms for certain algorithmic problems.
In order to explain what he meant, consider a typical problem for an elementary course of calculus. Suppose we are given a function something like
f(x)=sin(exp(x2)-cos(x3-4x+7)-x4+6)and we want to prove that this functions attains a maximum in some point from the segment [0,1]. How can we do this?
- Possibility 1: just construct the maximum point
- Possibility 2: reduce the problem to the finding of maximum of another function for which we already know its maximums.
- Possibilty 3: Prove that f(x) is continious and apply Weiestrass theorem.
- Possibility 1: just design a polynomial algorithm for testing P
- Possibility 2: polynomially reduce the problem to testing another property P' for which we already have a polynomial algorithm
Fortunately, they cover almost all cases, since the Graph Minor Theorem implies that we have a
Possibilty 3: Prove that the property P is minor-closed, since Graph Minor Theory developed by Neil Robertson and Paul Seymour implies that all minor-closed properties can be tested in polynomial (even in cubic) time! Let us note a graph-theoretic property P is said to be minor-closed if whenever a graph G satisfies P then so does evey minor of G. This follows from
- Graph Minor Theorem: If S is any family of finite graphs, none of which is a minor of another then S is finite!
- The existence of a polynomial (cubic) algorithm for H-minor testing: Given a graph G. Is it true that H is a minor of G?
One might wonder what can be said about graph minor theorem for infinite case. Robin Thomas in A counter-example to Wagner's conjecture for infinite graphs (Math. Proc. Comb. Phil. Soc. 1988, 103, pp. 55-57) constructed an infinite sequence of infinite graphs none of which is a minor of the other. Unfortunately, Thomas's proof contains two "bugs":
- The proof heavily lies on the validity of the prominent Axiom of Choice from Set Theory. It would be extremely useful to understand whether the existence of such a sequence really depends on this axiom? To put it in more understanble form for the experts of Mathematical Logic, I would like to ask for the refutation of Graph Minor theorem in ZF-(minus) - Zermelo-Fraenkel set theory that does not include the axiom of choice? This question is interesting not only on its own, but also for the Countable Graph Minor Conjecture.
- Thomas's proof implies nothing about the countable Graph Minor Conjecture, a conjecture stating that there are no infinite sequences of countable graphs none of which is a minor of the other?
Recent Developments: Bruce Reed and Ken-ichi Kawarabayashi have recently reduced the complexity of H-minor testing to O(n logn). "...To cast a glance at the next advaces of our science and the secrets of its development..." (the sentence is taken from David Hilbert's epochal talk before the International Congress of Mathematicians at Paris in 1900), especially for the generalization of the Graph Minor Theorem to Matroids (=Graph Minor Project) see Jim Geelen's lecture-notes delivered by him in the recent ADONET-CIRM doctoral school on Graphs and Algorithms.
Posted By Lance to Computational Complexity at 1/25/2008 06:18:00 AM