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(n^{3}) 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 H_{1},...,H_{a} such thatG \in X iff NONE of H_{1},...,H_{a} are minors of G.
(This is the corollary to GMT.)
EXAMPLE: a graph is planar iff it does not have K_{3,3} or K_{5}
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(n^{3})) for
many problems. Here are two such.

Fix k. Test if a graph has Vertex Cover of size &le k. (VC_{k})

Fix g. Test if a graph has genus &le g.

There are constructive linear time algorithms
for the VC_{k}. 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(n^{3}) (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
things like
f(k) = 1 if SAT is in TIME(n^{k}), 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.
Commentatorsplease comment. 
There are many problems in NP where if you fix one parameter
they are in O(f(k)p(n)) and not O(n^{f(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