Friday, January 04, 2008

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.
  1. 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).
  2. 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.
  3. 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.
  4. The proof is not only nonconstructive, but it is provably nonconstructive using Harvey Frideman's Reverse Mathematics framework.
  5. The following two facts, one a corollary of the GMT, is what yields polytime algorithms:
    1. For a fixed graph H, there is an O(n3) algorithm for the problem: Given G, is H a minor of G.
    2. If X is a set of graphs closed under minor then there exists a FINITE set of graphs H1,...,Ha such that G \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.
  6. One easily obtains poly time algorithms (indeed O(n3)) for many problems. Here are two such.
    1. Fix k. Test if a graph has Vertex Cover of size &le k. (VCk)
    2. Fix g. Test if a graph has genus &le g.
  7. 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.)
  8. 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.
  9. 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.
  10. Are there other nonconstructive algorithms? A cheap example are things like
    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.
  11. 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.
  12. Are there more legit examples? Commentators- please comment.
  13. I will have a later post on nonconstructive things in math.
Posted by at

10 comments:

  1. JeffE6:09 PM, January 04, 2008

    Bojan Mohar describes an algorithm to determine whether a graph as genus at most g in f(g)*O(n) time [STOC 1996, SIAM Discrete Math 1999]. The algorithm either constructs an embedding or finds a forbidden subgraph. I believe the dependence on g is doubly-exponential. (The graph-genus problem is NP-hard [Thomassen 1989], so exponential in g is the best one can hope for.) A side effect of Mohar's algorithm is a constructive proof of Robertson and Seymour's theorem that genus-g graphs have a finite number of forbidden minors.

    See also Kawarabayashi and Reed's STOC 2007 paper. They describe an algorithm to determine in f(k)*O(n) time whether a graph can be drawn in the plane with at most k crossings.

    ReplyDelete
  2. Anonymous3:18 AM, January 05, 2008

    A side effect of Mohar's algorithm is a constructive proof of Robertson and Seymour's theorem that genus-g graphs have a finite number of forbidden minors.

    Presumably this doesn't actually give an effective way of generating the list of forbidden minors, since such a list is unknown even for g=1.

    ReplyDelete
  3. Anonymous5:06 AM, January 05, 2008

    Does the following problems also follows from GMT:

    For a fixed graph H, give a polytime algorithm which given an edge-weighted graph G returns the minimum weight minor of H.

    ReplyDelete
  4. Anonymous5:09 AM, January 05, 2008

    Corrections in previous post,

    For a fixed graph H, give a polytime algorithm which given an edge-weighted graph G returns the minimum weight subgraph that contains a minor of H.

    ReplyDelete
  5. Anonymous7:23 PM, January 05, 2008

    The oxymoronic phrase "nonconstructive algorithm" sounds like a Yogi-ism. Is that expression actually used in the literature, or is it just blogging shorthand for something longer which, while more technically correct, doesn't exactly roll off the tongue (in which case maybe we should call "nonconstructive algorithm" a Gasarch-ism)?

    ReplyDelete
  6. Anonymous9:35 AM, January 06, 2008

    I think the term 'nonconstructive algorithm' makes a lot of sense.

    Consider primality testing algorithms.

    Any currently known fast primality testing algorithm could be considered 'nonconstructive' because in certain cases when they return that a number is composite it proves that there is a factor of the input, but it doesn't tell you what it is.

    ReplyDelete
  7. Anonymous5:16 PM, January 06, 2008

    I don't think "non-constructive algorithm" is an instantly recognizable, universal technical term, but I've heard it before.

    Primality testing is not an example in the sense of this posting. What Gasarch is talking about is cases in which you can prove that an algorithm exists but the proof does not actually tell you an algorithm.

    This is what happens with the graph minor theorem. Given any minor-closed family of graphs, there is always an algorithm for testing membership. Specifically, the family is characterized by a finite set of excluded minors, and you just need to check for them. However, the proof of the theorem gives no method for actually writing down the excluded minors, and without that this method doesn't lead to an actual algorithm, even though it proves that an algorithm definitely exists.

    ReplyDelete
  8. Anonymous5:44 PM, January 06, 2008

    This comment has been removed by a blog administrator.

    ReplyDelete
  9. Anonymous9:28 AM, January 07, 2008

    What Gasarch is talking about is cases in which you can prove that an algorithm exists but the proof does not actually tell you an algorithm.

    Then, from my understanding, an unambiguous way to describe this would be 'nonconstructive proof of existence of an algorithm' since it is the proof which does not supply a construction.

    The word 'nonconstructive' is an adjective that, in my usage, means what it modifies does not construct something.

    Therefore 'nonconstructive algorithm' would be an algorithm that does not construct something. Further 'nonconstructive proof' would be a proof which does not construct something.

    In this case the proof does not construct, but proves the existence of, an algorithm. Hence it is a 'nonconstructive proof', but I do not think the algorithm proven to exist should be called 'nonconstructive' (unless it is also a 'nonconstructive proof' as in the primality testing example).

    The example I gave is in fact a 'nonconstructive proof', but since the proof is an algorithm I think the term 'nonconstructive' could be applied. Should it? I think this discussion indicates that it is probably safer to stick with the term 'nonconstructive proof' in which case BG's query (as I currently understand it) becomes "Do there exist more nonconstructive proofs which prove the existence of an algorithm?"

    ReplyDelete
  10. GASARCH10:51 AM, January 07, 2008

    Commenter 9 is correct,
    so the question should be

    Are there OTHER (poly time)
    algorithms for problems of
    interest where the proof
    that the algorithm works,
    OR the proof that it terminates
    in poly time, is nonconstructive.

    bill g.

    ReplyDelete

Subscribe to: Post Comments (Atom)