**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(xand we want to prove that this functions attains a maximum in some point from the segment [0,1]. How can we do this?^{2})-cos(x^{3}-4x+7)-x^{4}+6)

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

Is there an electronically available version of Kawarabayashi and Reed's O(n log n) graph minor result?

ReplyDeleteActually the first polynomial-time algorithmic result has been obtained by Demaine, Hajiaghayi,and Kawarabayashi in FOCS'05 which is available online. I'm not sure that the result of Reed and Kawarabayashi is finished and checked.

ReplyDeleteConcerning the result of Reed and Kawarabayashi, I would like to say that for the first time I heard about that from Jim during the mentioned lectures.

ReplyDeleteReplying to 2.: I thought that Robertson and Seymour had already provided a polynomial-time algorithm, in the sense that we can check for any fixed excluded minor in O(n^3), although with an astronomical constant hidden in the O.

ReplyDeleteCris

Concerning Robertson-Seymour O(n^3) algorithm for H-minor testing problem there is another fact that I encountered in Schrijver's Combinatorial Optmization. He says

ReplyDeletethat the correctness of this algorithm is based on validity of a lemma which proof is still unpublished....

Vahan