Algorithmic Implicationsof the Graph Minor Theorem∗Daniel Bienstock Michael A. LangstonDept. of Civil Engineering Dept. of Computer ScienceColumbia University University of TennesseeNew York, NY 10027 Knoxville, TN 37996A chapter prepared for theHandbook of Operations Research and Management Science:Volume on Networks and Distribution∗Page proofs and related correspondence should be sent to M. A. Langston.Algorithmic Implicationsof the Graph Minor TheoremDaniel Bienstock and Michael A. Langston1 IntroductionIn the course of roughly the last ten years, Neil Robertson and Paul Seymour have ledthe way in developing a vast body of work in graph theory. One of their most celebratedresults is a proof of an old and intractable conjecture in graph theory, previously known asWagner’s Conjecture, and now known as the Graph Minor Theorem. The purpose of thischapter is to describe some of the algorithmic ramifications of this powerful theorem and itsconsequences.Significantly, many of the tools used in the proof of the Graph Minor Theorem can beapplied to a very broad class of algorithmic problems. For example, Robertson and Seymourhave obtained a relatively simple polynomial-time algorithm for the disjoint paths problem(described in detail later), a task that had eluded researchers for many years. Other ap-plications include combinatorial problems from several domains, including network routing,utilization and design. Indeed, it is a critical measure of the value of the Graph Minor The-orem that so many applications are already known for it. Only the tip of the iceberg seemsto have surfaced thus far. Many more important applications are being reported even as wewrite this.The entire graph minors project is immense, containing almost 20 papers whose totallength may exceed 600 pages. Thus we focus here primarily on some of the main algorithmicideas, although a brief sketch of related issues is necessary. We assume the reader is familiarwith basic concepts in graph theory [BM]. Except where noted otherwise, all graphs we2consider are finite, simple and undirected.2 A Brief Outline of the Graph Minors ProjectThree of the key notions employed are minors, obstructions and well-quasi-orders, andwe examine them in that order.Minors. Given graphs H and G, we say that H is a minor of G (or that G contains Has a minor) if a graph isomorphic to H can be obtained by removing from G some verticesand edges and then contracting some edges in the resulting subgraph. Thus every graph isa minor of itself, and the single vertex graph is a minor of every nonempty graph. For aslightly less trivial example, see Figure 1, which illustrates that the wheel with four spokes(W4) is a minor of the binary three-cube (Q3)............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................G = Q3H = W4– – – contract⊇−→ −→ −→..........................................................................................................................................................................................................................................................................................................•• •••••••• ••••••••• •••••••••• •• •••............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ............. ............. ............. ............. .......................... ............. ............. ............. ............. .......................................Figure 1A concept related to minor containment is topological containment. We say that a graphG is a subdivision of a graph H if G may be obtained by subdividing edges of H (an edge{u, v} is subdivided by replacing {u, v} with a path with ends u and v and whose internalvertices are new). We say that G topologically contains H if G contains a subgraph that is asubdivision of H. Thus topological containment is a special case of minor containment (we3can only contract edges at least one of whose endpoints have degree two). Observe that W4is not topologically contained in Q3.Topological containment has been heavily studied by graph theorists. Perhaps the mostfamous theorem in this regard is Kuratowski’s [Ku]: a graph is planar if and only if it doesnot topologically contain K5or K3,3. We note here that these two graphs are minimallynonplanar, that is, every graph topologically (and properly) contained in either of them isplanar.For the sake of exposition, let us view this theorem in terms of minors. Clearly, everyminor of a planar graph is also planar. That is, the class of planar graphs is closed in theminor order. Consequently, no planar graph contains a K5or K3,3minor. Moreover, everyproper minor of either of these two graphs is planar, and neither one contains the other asa minor. But can there be other minimal
View Full Document
Unlocking...