[Computational Complexity] Graph Minor Theorem and Non Const Algorithms
- The last comment on the last post had some questions about the graph minor theorem and (implicitly) nonconstructive algorithms in general. Here is some background and answers.
- If G is a graph then H is a minor of G if H can be obtained by removing vertices, removing edges, and constracting edges (that is, replacing edge (u,v) with just one vertex that has all the neighbors that u and v had).
- The formal statement of the Graph Minor Theorem (GMT)is: the set of graphs with the minor ordering is a well quasi order. This means that you cannot have an infinite descending sequence of graphs or an infinite set of incomparable graphs, using this ordering.
- The GMT has a hard nonconstructive proof. It was proven in a sequence of papers by Robertson and Seymour entitled `Graph Minors I' `Graph Minors II' etc. It was finally proved in Graph Minors XX. This website claims that it was proven in 1988 but was not published until 2004.
- The proof is not only nonconstructive, but it is provably nonconstructive using Harvey Frideman's Reverse Mathematics framework.
The following two facts, one a corollary of the GMT,
is what yields polytime algorithms:
- For a fixed graph H, there is an O(n3) algorithm for the problem: Given G, is H a minor of G.
- If X is a set of graphs closed under minor then there exists a FINITE set of graphs H1,...,Ha such thatG \in X iff NONE of H1,...,Ha are minors of G. (This is the corollary to GMT.) EXAMPLE: a graph is planar iff it does not have K3,3 or K5 as a minor. In this case we know the obstruction set. The proof of GMT does not yield this information.
One easily obtains poly time algorithms (indeed O(n3)) for
many problems. Here are two such.
- Fix k. Test if a graph has Vertex Cover of size &le k. (VCk)
- Fix g. Test if a graph has genus &le g.
- There are constructive linear time algorithms for the VCk. Last time I checked it was down to O(n + (1.34)k). For the Genus problem I don't know whats known. (Commentators- please comment.)
- Fellows and Langston showed how to convert most algorithms (including those for VC and Genus) from poly nonconst to poly constructive. The degree does not go up much (either by 0 or 1), but the order constant gets even worse.
- NOW for the commentators question: is the converse true: does an algorithm for (say) genus g that is in time O(n3) (the order constant may depend on g) imply GMT. I doubt this is true. It may be provably not true given that GMT has a provably nonconstructive proof.
Are there other nonconstructive algorithms? A cheap example are
f(k) = 1 if SAT is in TIME(nk), 0 otherwise
which is in P (its just a step function or the always 0 function) but do not know how to compute it. Are there examples for problems we care about being in P through nonconstructive means that are NOT from GMT? I do not know. Commentators-please comment.
- There are many problems in NP where if you fix one parameter they are in O(f(k)p(n)) and not O(nf(k)). Such problems are called FIXED PARAMETER TRACTABLE. Downey and Fellows wrote a book on it a while back, though there are more books out now.
- Are there more legit examples? Commentators- please comment.
- I will have a later post on nonconstructive things in math.
Posted By GASARCH to Computational Complexity at 1/04/2008 01:01:00 PM