{\huge Minor Insights Are Useful}
Some examples of small insights that help \vspace{.5in}
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 {\tt improved-GMT.pdf} while the new one is {\tt 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 {\tt improved-improved-improved} GMT out there. Perhaps we'll see it at STOC 2016, but if the progression keeps up, it will have zero authors.
The Result(s)
Here is the main theorem that was improved between the STOC papers:
Theorem 1 There is a universal constant $latex {\delta>0}&fg=000000$ such that for every $latex {k \ge 1}&fg=000000$, every graph $latex {G}&fg=000000$ of treewidth $latex {k}&fg=000000$ has a graph grid-minor of size $latex {\Omega(k^{\delta}) \times \Omega(k^{\delta})}&fg=000000$. 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 $latex {G}&fg=000000$ 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 $latex {\delta}&fg=000000$ in the 2014 paper's proof is asymptotic to $latex {1/98}&fg=000000$. The 2015 paper improves it to $latex {1/36}&fg=000000$. 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 $latex {G}&fg=000000$. In the case of treewidth we have a tree $latex {T}&fg=000000$ and a mapping $latex {f}&fg=000000$ from nodes $latex {i}&fg=000000$ of $latex {T}&fg=000000$ to subsets $latex {B_i}&fg=000000$ of the vertices of $latex {G}&fg=000000$. The two conditions for $latex {f}&fg=000000$ to be a tree decomposition of $latex {G}&fg=000000$ are:
The treewidth is the minimum $latex {k}&fg=000000$ such that $latex {G}&fg=000000$ has a tree decomposition by sets $latex {B_i}&fg=000000$ of size at most $latex {k+1}&fg=000000$. This number makes trees have treewidth 1. If $latex {G}&fg=000000$ has a cycle $latex {C}&fg=000000$, the conditions combine to force $latex {k \geq 2}&fg=000000$. The $latex {m \times m}&fg=000000$ square grid has treewidth $latex {m}&fg=000000$, while $latex {n}&fg=000000$-vertex expanders have treewidth $latex {\Omega(n)}&fg=000000$.
A graph $latex {H}&fg=000000$ is a minor of $latex {G}&fg=000000$ if there is a mapping $latex {g}&fg=000000$ from nodes $latex {i}&fg=000000$ of $latex {H}&fg=000000$ to disjoint subsets $latex {A_i}&fg=000000$ of $latex {V(G)}&fg=000000$ such that:
Together these conditions mean one can obtain $latex {H}&fg=000000$ from $latex {G}&fg=000000$ by contracting each $latex {A_i}&fg=000000$ to a single vertex, then deleting edges until only those in $latex {H}&fg=000000$ remain. In Theorem~1, $latex {H}&fg=000000$ is a square grid. We've arranged the definitions to echo as much as possible. The correspondence is rough, but the tension between treewidth $latex {k}&fg=000000$ and grid minor-size $latex {k^{\delta}}&fg=000000$ 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 break long proofs into smaller chucks. The famous 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.
Small Insights
One observation comes from the 1994 paper:
Lemma 2 There is a universal constant $latex {c}&fg=000000$ such that every $latex {n}&fg=000000$-vertex planar graph is a minor of the $latex {cn \times cn}&fg=000000$ 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 $latex {d}&fg=000000$ such that for any planar $latex {n}&fg=000000$-vertex graph $latex {H}&fg=000000$, all graphs $latex {G}&fg=000000$ that do not have $latex {H}&fg=000000$ as a minor (i.e., for which $latex {H}&fg=000000$ is an ``excluded minor'') have treewidth $latex {O(n^d)}&fg=000000$.
Note that the treewidth bound is independent of the size of $latex {G}&fg=000000$. They prove this with $latex {d = 1/\delta \sim 98}&fg=000000$.
Two of the important little observations from the 2014 Chekuri-Chuzhoy paper are:
Lemma 4 Let $latex {\{ x_{1},\dots,x_{n}\}}&fg=000000$ be any set of non-negative integers, with $latex {\sum_{i} x_{i} = N}&fg=000000$ and $latex {x_{i} \le 2N/3}&fg=000000$ for all $latex {i}&fg=000000$. Then we can efficiently compute a partition $latex {(A,B)}&fg=000000$ of $latex {\{1,\dots,N\}}&fg=000000$ such that $latex {\sum_{i \in A}x_{i} \ge N/3}&fg=000000$ and $latex {\sum_{i \in B}x_{i} \ge N/3}&fg=000000$.
Lemma 5 Let $latex {T}&fg=000000$ be a rooted tree such that $latex {V(T) \ge \ell p}&fg=000000$ for some positive integers $latex {\ell}&fg=000000$ and $latex {p}&fg=000000$. Then $latex {T}&fg=000000$ has at least $latex {\ell}&fg=000000$ leaves or $latex {T}&fg=000000$ has a root-to-leaf path of length at least $latex {p}&fg=000000$.
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 $latex {k/\mathsf{polylog}(k)}&fg=000000$. 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.
Well-Linked Observations
The plan and gadgets built for the proof come off well in slides for both Chekuri and Chuzhoy at a time when they had $latex {\delta = 1/42}&fg=000000$. 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 $latex {U \subset V(G)}&fg=000000$ is well-linked if for all $latex {A,B \subset U}&fg=000000$ with $latex {|A| = |B| = t}&fg=000000$, $latex {1 \leq t \leq |U|}&fg=000000$, there are $latex {t}&fg=000000$-many node-disjoint paths connecting $latex {A}&fg=000000$ and $latex {B}&fg=000000$. This allows paths of length 0 when $latex {A}&fg=000000$ and $latex {B}&fg=000000$ share vertices.
The maximum size $latex {h = |U|}&fg=000000$ of a well-linked set $latex {U}&fg=000000$ is another graph invariant. Bruce Reed proved:
Lemma 7 For graphs of treewidth $latex {k}&fg=000000$, $latex {h \leq k \leq 4h}&fg=000000$.
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 $latex {h}&fg=000000$ enables one to find a grid minor of size $latex {\Omega(\sqrt{h})}&fg=000000$ on the side. To gain their tighter connections, the new papers relax the concept:
Definition 8 $latex {U}&fg=000000$ is $latex {\alpha}&fg=000000$-well-linked if for all $latex {T,T' \subset U}&fg=000000$ with $latex {|T| = |T'| = t}&fg=000000$, $latex {1 \leq t \leq |U|}&fg=000000$, there is a flow from $latex {T}&fg=000000$ to $latex {T'}&fg=000000$ of congestion at most $latex {1/\alpha}&fg=000000$.
The following result connects the bound $latex {\alpha}&fg=000000$ to the flow-building task. It meets one definition of 'observation' in that the authors in other works sometimes use it as the definition of ``$latex {\alpha}&fg=000000$-well-linked.''
Lemma 9 If $latex {U}&fg=000000$ is not $latex {\alpha}&fg=000000$-well-linked in $latex {G}&fg=000000$ then there is a partition of all of $latex {V(G)}&fg=000000$ into sides $latex {A}&fg=000000$ and $latex {B}&fg=000000$ such that the number of edges between $latex {A}&fg=000000$ and $latex {B}&fg=000000$ is bounded above by $latex {\alpha|A\cap U|}&fg=000000$ and by $latex {\alpha|B \cap U|}&fg=000000$.
The newest paper also uses versions where $latex {t}&fg=000000$ is constrained to be at most some number $latex {k'}&fg=000000$ for which $latex {\alpha k'}&fg=000000$ then becomes another upper bound on edges across the $latex {A,B}&fg=000000$ 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.
Open Problems
What are your favorite observations?