Algorithmic Implications of the Graph Minor Theorem Daniel Bienstock Dept of Civil Engineering Columbia University New York NY 10027 Michael A Langston Dept of Computer Science University of Tennessee Knoxville TN 37996 A chapter prepared for the Handbook of Operations Research and Management Science Volume on Networks and Distribution Page proofs and related correspondence should be sent to M A Langston Algorithmic Implications of the Graph Minor Theorem Daniel Bienstock and Michael A Langston 1 Introduction In the course of roughly the last ten years Neil Robertson and Paul Seymour have led the way in developing a vast body of work in graph theory One of their most celebrated results is a proof of an old and intractable conjecture in graph theory previously known as Wagner s Conjecture and now known as the Graph Minor Theorem The purpose of this chapter is to describe some of the algorithmic ramifications of this powerful theorem and its consequences Significantly many of the tools used in the proof of the Graph Minor Theorem can be applied to a very broad class of algorithmic problems For example Robertson and Seymour have 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 applications 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 Theorem that so many applications are already known for it Only the tip of the iceberg seems to have surfaced thus far Many more important applications are being reported even as we write this The entire graph minors project is immense containing almost 20 papers whose total length may exceed 600 pages Thus we focus here primarily on some of the main algorithmic ideas although a brief sketch of related issues is necessary We assume the reader is familiar with basic concepts in graph theory BM Except where noted otherwise all graphs we 2 consider are finite simple and undirected 2 A Brief Outline of the Graph Minors Project Three of the key notions employed are minors obstructions and well quasi orders and we examine them in that order Minors Given graphs H and G we say that H is a minor of G or that G contains H as a minor if a graph isomorphic to H can be obtained by removing from G some vertices and edges and then contracting some edges in the resulting subgraph Thus every graph is a minor of itself and the single vertex graph is a minor of every nonempty graph For a slightly 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 Q3 H W4 contract Figure 1 A concept related to minor containment is topological containment We say that a graph G 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 internal vertices are new We say that G topologically contains H if G contains a subgraph that is a subdivision of H Thus topological containment is a special case of minor containment we 3 can only contract edges at least one of whose endpoints have degree two Observe that W 4 is not topologically contained in Q3 Topological containment has been heavily studied by graph theorists Perhaps the most famous theorem in this regard is Kuratowski s Ku a graph is planar if and only if it does not topologically contain K5 or K3 3 We note here that these two graphs are minimally nonplanar that is every graph topologically and properly contained in either of them is planar For the sake of exposition let us view this theorem in terms of minors Clearly every minor of a planar graph is also planar That is the class of planar graphs is closed in the minor order Consequently no planar graph contains a K5 or K3 3 minor Moreover every proper minor of either of these two graphs is planar and neither one contains the other as a minor But can there be other minimal excluded minors The answer is negative for if G were such a purported graph then G would be nonplanar and thus it would contain topologically and therefore as a minor either K5 or K3 3 In summary a graph is planar if and only if it does not contain a K5 or K3 3 minor We note in passing two other points of interest concerning planarity One is that planarity can be tested in polynomial time in fact in linear time HT The other is that a problem of natural interest is to try to extend Kuratowski s theorem to higher surfaces A surface is obtained from the sphere by gluing onto it a finite number of handles and or crosscaps Ma A graph can be embedded on a given surface if it can be drawn on that surface without crossings Given a surface S can we characterize those graphs embeddable in S by a finite list of excluded graphs in the topological order In the 1930s Erdo s conjectured that the answer is yes No results were obtained on this conjecture until much later first with a proof for the case when S is the projective plane Ar and then for the case when S is non orientable GHW 4 Obstructions Kuratowski s theorem may be regarded as a characterization of planarity by means of excluded graphs henceforth termed obstructions Characterizations of this nature abound in combinatorial mathematics and optimization Some familiar examples include the max flow min cut theorem Seymour s description of the clutters with the max flow min cut property and Farkas lemma In all these the presence of a desired feature is characterized by the absence of some obstruction Besides being aesthetically pleasing theorems of this type are desirable because such characterizations provide evidence of tractability of the problem at hand giving hope for a polynomial time test for the desired feature The graph minors project contains several such theorems many of which turn out to be at the heart of both proofs and applications As expected there are algorithmic aspects to these theorems As a very introductory example one can test in polynomial time if any graph can be embedded on the torus Well quasi orders A class Q equipped with a transitive and reflexive relation is called a quasi order For example the class of all graphs is a quasi order where is the minor containment relation There has been some confusion as to the difference between quasiorders and partial orders it suffices to look at graph minors to understand this difference It is
View Full Document
Unlocking...