Minor Insights Are Useful
Some examples of small insights that help
Cropped from src1, src2
Julia Chuzhoy and Chandra Chekuri are experts on approximation algorithms: both upper and lower bounds. Each is also interested in graph theory as it applies to algorithms.
Today Ken and I wish to talk about their recent papers on structural theorems for graphs.
The latest paper, by Chuzhoy, was just presented at STOC 2015 and is titled, “Excluded Grid Theorem: Improved and Simplified.” It builds on their joint papers, “Polynomial Bounds for the Grid-Minor Theorem” from STOC 2014 and “Degree-3 Treewidth Sparsifiers” from SODA 2015.
We note with amusement that the filename of the STOC 2014 paper on Chuzhoy’s website is improved-GMT.pdf while the new one is improved-improved-GMT-STOC.pdf. The versions of the GMT, for “Grid-Minor Theorem,” that they were improving had exponential bounds, notably one obtained in 1994 by Neil Robertson, Paul Seymour, and Robin Thomas. We concur with the authors that there must be an improved-improved-improved GMT out there. Perhaps we’ll see it at STOC 2016, but if the 3-2-1 progression keeps up, it will have zero authors.
Here is the main theorem that was improved between the STOC papers:
Theorem 1 There is a universal constant such that for every , every graph of treewidth has a graph grid-minor of size . Moreover the grid minor can be found by a randomized algorithm in time polynomial in the size of the graph.
This is a classic structural type graph theorem. It says that if a graph is sufficiently complex, then it must have a certain regular substructure. Here complexity is measured by the treewidth of the graph, and the substructure is that it contains a certain type of subgraph.
The in the 2014 paper’s proof is asymptotic to . The 2015 paper improves it to . There is however a ‘disimprovement’: the sharper theorem has a nonconstructive element and no longer provides a polynomial-time algorithm for finding the minor with high probability. It does simplify the proof and fosters a framework for further progress.
The Main Concepts
Both treewidth and minors involve kinds of embeddings of other graphs into subgraphs or set systems based on . In the case of treewidth we have a tree and a mapping from nodes of to subsets of the vertices of . The two conditions for to be a tree decomposition of are:
- For every edge of , there is an such that .
- For every vertex of , the set of such that forms a subtree of —in particular it is connected.
The treewidth is the minimum such that has a tree decomposition by sets of size at most . This number makes trees have treewidth 1. If has a cycle , the conditions combine to force . The square grid has treewidth , while -vertex expanders have treewidth .
A graph is a minor of if there is a mapping from nodes of to disjoint subsets of such that:
- For every edge in , there is an edge in such that and .
- For every , the subgraph of induced by is connected.
Together these conditions mean one can obtain from by contracting each to a single vertex, then deleting edges until only those in remain. In Theorem 1, is a square grid. We’ve arranged the definitions to echo as much as possible. The correspondence is rough, but the tension between treewidth and grid minor-size comes out precisely in the proof.
In Praise Of Minor Results
Theorems of the above type often have quite complex proofs. As usual these proofs are broken down into pieces. The hierarchy is observation, claim, and lemma. Perhaps “claim” comes before “observation.” In any event the point is that we not only break long proofs into smaller chunks, we break down the conceptualization of their strategies. The sage Doron Zeilberger argues:
So blessed be the lemmas, for they shall inherit mathematics. Even more important than lemmas are observations, but that is another story.
I thought I would follow Doron’s suggestion and talk just about observations. They are used in their proofs and seem like they could be of independent interest.
One observation comes from the 1994 paper:
Lemma 2 There is a universal constant such that every -vertex planar graph is a minor of the square grid.
This amounts to observing that all planar networks can be compactly implemented on grids. The significance for Chuzhoy and Chekuri is that Theorem 1 extends to all planar graphs. In contraposed form:
Theorem 3 There is a universal constant such that for any planar -vertex graph , all graphs that do not have as a minor (i.e., for which is an “excluded minor”) have treewidth .
Note that the treewidth bound is independent of the size of .
Two of the important little observations from the 2014 Chekuri-Chuzhoy paper are:
Claim 4 Let be any set of non-negative integers, with and for all . Then we can efficiently compute a partition of such that and .
Claim 5 Let be a rooted tree such that for some positive integers and . Then has at least leaves or has a root-to-leaf path of length at least .
The new paper takes its jumping-off point from this little observation: Treewidth can be approximately conserved while minorizing down to a bounded-degree graph. This may sound surprising but isn’t—think of the fact that expander graphs can have degree 3. Building on advances in a paper by Ken-ichi Kawarabayashi and Yusuke Kobayashi and an independent paper by Seymour with Alexander Leaf (both of which also improved the exponent from the 1994 result), the SODA paper shows how to keep the treewidth of the degree-3 graph above . The motivation for going down all the way to degree 3 is another simple observation:
In graphs of degree 3, edge-disjoint path systems and node-disjoint path systems are the same on non-terminal nodes.
The plan and gadgets built for the proof come off well in slides for both Chekuri and Chuzhoy at a time when they had . Here is one slide that conveys the strategy; we’ve edited it to add a vertical bracket- as on the previous slide:
The disjoint path systems connect clusters of nodes that facilitate multiple switching and routing by obeying definitions like the following:
Definition 6 A node set is well-linked if for all with , , there are -many node-disjoint paths connecting and . This allows paths of length when and share vertices.
The maximum size of a well-linked set is another graph invariant. Bruce Reed proved:
Lemma 7 For graphs of treewidth , .
This concept and observation bridge between treewidth and problems of routing paths that build grid structures. Leaf and Seymour proved that having a path-of-clusters system of width enables one to find a grid minor of size on the side. To gain their tighter connections, the new papers relax the concept:
Definition 8 is -well-linked if for all with , , there is a flow from to of congestion at most .
The following result connects the bound to the flow-building task. It meets one definition of ‘observation’ insofar as it is used as the definition of “-well-linked” in some other works by the authors.
Observation 9 If is -well-linked in then for any partition of all of into sides and , the number of edges crossing the partition is at least the minimum of and .
The newest paper also uses versions where is constrained to be at most some number for which then becomes another upper bound on edges across the cut. This is the gateway to the rough-and-tumble combinatorial details, for which the latest paper and the talk slides are best to see. But we hope that sharing these observations conveys the flavor well.
What are your favorite observations?