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(x²)-cos(x³-4x+7)-x⁴+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?

1. Possibility 1: just construct the maximum point
2. Possibility 2: reduce the problem to the finding of maximum of another function for which we already know its maximums.
3. Possibilty 3: Prove that f(x) is continious and apply Weiestrass theorem.

We know that neither Weierstrass theorem nor its proof imply anything about how one can construct this maximum. It just states that this maximum exists! Now suppose that we have a property P and we would like to show that testing P can be done in a polynomial time. How can we do that?

1. Possibility 1: just design a polynomial algorithm for testing P
2. Possibility 2: polynomially reduce the problem to testing another property P' for which we already have a polynomial algorithm

These two possibilities cover almost all the ways that reasearchers working on designing algorithms use while trying to prove the existence of efficient algorithms.

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

1. Graph Minor Theorem: If S is any family of finite graphs, none of which is a minor of another then S is finite!
2. 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?

Incidentally the following problem is NP-complete: Minor testing Given two graphs G and H. Is it true that H is a minor of G? One might wonder whether there are properties for which we can prove the pure existence of a polynomial testing algorithm? As Reinhard Diestel states in his book Graph Theory, an example of such property is the knotlessness, that is deciding whether a graph can be embadded in 3-dimensional space such that none of its cycles form a trivial knot (see the book for details). Though we do know that the algorithm exists, at this moment we do not have an explicit algorithm (we cannot write a program), even if we have got enough enthusiasm to read Graph Minors I, Graph Minors II, Graph Minors III,..... - a series of papers devoted to the mentioned results of Robertson and Seymour.

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":

1. 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.
2. 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.