The Graph Minor Theorem

The Graph Minor
Neil Robertson, Paul Seymour published a series of papers in the Journal of Combinatorial
Theory Series B.
Beginning with Graph Minors.I.Excluding a Forest, appearing and 1983 and currently up to Graph
Minors.XXIII.Nash-Williams’ Immersion Conjecture. The most recent appearing in 2012.
One of the main intended results culminated in Graph Minors.XX.Wagner’s Conjecture, in a
proof of what is now known as The Graph Minor Theorem.
A binary relation ≤ on a set  is a quasi-order if it is both reflexive and transitive.
For all , ,  ∈ ,
 ≤  (reflexive)
If  ≤  and  ≤ , then  ≤  (transitive)
A partial-order is a quasi-order that also requires anti-symmetry, that is:
If  ≤  and  ≤ , then  = .
A set is well-quasi-ordered (wqo) under a relation ≤ if:
1) It is well-founded. Every non-empty subset has a minimal element.
2) It does not contain any infinite antichains. For all infinite sequences of elements 0 , 1 , 2 , …
from  there is 1 ≤  <  such that  ≤  .
Well-quasi-orders have also been described in terms of ideals (see for example Higman or J.
A subset  of  is called an upper ideal if  ∈  and  ≤  implies  ∈ .
  = {| ≥    }
If   =  , then  is said to generate  or  is the ideal generated by .
In this context, a space  is well-quasi-ordered if it is quasi-ordered and every ideal has a finite
generating set.
Orders on Sets of Graphs
Some potential orders on the set of finite undirected graphs:
Subgraph Containment
Topological Order
Immersion Order
Minor Order
Subgraph Containment
Under subgraph containment,  ≤  if  is isomorphic to a subgraph of .
Subgraph Containment
Subgraph Containment
4 ≤ 5
Topological Order
A graph  is a subdivision of a graph  if  can be obtained by subdividing edges of . In the
topological order,  ≤   if  contains a subgraph isomorphic to a subdivision of .
6 ≤  8
4 ≤  6
Immersion Order
In the immersion order,  ≤  if there is a map : () → () and a map  that takes each
edge  of  to a path from () and () in  such that paths given by  are edge disjoint.
Equivalently, H is isomorphic to a subgraph obtainable from  by a series of liftings.
Immersion Order
4 ≤ 3
Minor Order
Allowable operations are taking subgraphs and contracting edges.  ≤  if  is (isomorphic
to) a minor of .
Minor Order
4 ≤ 3
The Graph Minor Theorem
The class of all finite undirected graphs is a wqo under the minor relation.
Consequences and Applications
If a family of graphs is closed under taking minors, then membership in that
family can be characterized by a finite list of minor obstructions.
Consequences and Applications
Vertex Disjoint Paths: Given a graph  and a set of  pairs of vertices 1 , 1 , 2 , 2 , … , ( ,  ) of ,
does there exist paths 1 , 2 , … ,  in , mutually vertex-disjoint, such that  joins  and  for 1 ≤
 ≤ ?
If k is in the input of the problem, it is NP-complete. (Karp)
In Graph Minors.XIII.The Disjoint Paths Problem, Robertson and Seymour give a (3 ) algorithm for
fixed k.
As a consequence, they obtain a (3 ) algorithm for checking minor containment.
Consequences and Applications
If a family of graphs is closed under taking minors,
then membership in that family can be tested in
polynomial time.
1) The algorithm is non-constructive. (requires knowledge of obstruction set)
2) It hides huuuuuuuuge constants of proportionality.
Consequences and Applications
Dr. Langston and Mike Fellows pioneering work in applications included proofs that:
For every fixed k, gate matrix layout is solvable in polynomial time.
As well as analogs for:
Disk dimension
Minimum cut linear arrangement
Topological bandwidth
Crossing number
Maximum leaf spanning tree
Search number
Two dimensional grid load factor
Consequences and Applications
Their work would lay the foundation for what would be formalized as a new field
of study – fixed parameter tractability.
R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag 1999.
Current Research
Improving minor containment checking.
Currently for branchwidth k: 2() ℎ2 2(ℎ)  algorithm by Adler, Dorn, Fomin,
San, and Thilikos.
Current Research
Improving the cost of the hidden constant.
Best vertex cover time is (1.2738 + ) due to Chen, Kanj, and Xia.
Current Research
Identification of obstruction sets.
Obstruction set for 2-track GML consists of 3 and  1,3 .
Obstruction set for 3-track GML contains 110 elements. (Kinnersley and
Current Research
Extension of results to directed graphs.
Difficult to determine what a minor of a directed graph should be.
Work has been done on immersions of directed graphs.
The class of directed graphs is not a wqo under (weak) immersion.
The class of all tournaments is a wqo under strong immersion. (Chudnovsky and Seymour)
Adler, Isolde, et al. "Faster parameterized algorithms for minor containment." Theoretical Computer Science 412.50 (2011): 7018-7028.
Chen, Jianer, Iyad A. Kanj, and Ge Xia. "Improved parameterized upper bounds for vertex cover." Mathematical Foundations of Computer
Science 2006. Springer Berlin Heidelberg, 2006. 238-249.
Chudnovsky, Maria, and Paul Seymour. "A well-quasi-order for tournaments." Journal of Combinatorial Theory, Series B 101.1 (2011): 4753.
Fellows, Michael R., and Michael A. Langston. "Nonconstructive tools for proving polynomial-time decidability." Journal of the ACM
(JACM) 35.3 (1988): 727-739.
Kinnersley, Nancy G., and Michael A. Langston. "Obstruction set isolation for the gate matrix layout problem." Discrete Applied
Mathematics 54.2 (1994): 169-213.
Langston, Michael A. “Fixed-Parameter Tractability, A Prehistory,” in The Multivariate Complexity Revolution and Beyond: Essays
Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday (H. L. Bodlaender, R. Downey, F. V. Fomin and D. Marx, editors),
Springer, 2012, 3–16.
Robertson, Neil, and Paul D. Seymour. "Graph minors. XIII. The disjoint paths problem." Journal of Combinatorial Theory, Series B 63.1
(1995): 65-110.
Robertson, Neil, and Paul D. Seymour. "Graph minors. XX. Wagner's conjecture." Journal of Combinatorial Theory, Series B 92.2 (2004):
1. Show that finite nondirected graphs are not wqo under subgraph containment.
2. Show that finite nondirected graphs are not wqo under the topological order.

similar documents