Minor Insights Are Useful

June 8, 2015

tags: Chandra Chekuri, graph minors, graphs, Julia Chuzhoy, treewidth

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.

The Result(s)

Here is the main theorem that was improved between the STOC papers:

Theorem 1 There is a universal constant ${\delta>0}$ such that for every ${k \ge 1}$ , every graph ${G}$ of treewidth ${k}$ has a graph grid-minor of size ${\Omega(k^{\delta}) \times \Omega(k^{\delta})}$ . 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 ${G}$ 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 ${\delta}$ in the 2014 paper’s proof is asymptotic to ${1/98}$ . The 2015 paper improves it to ${1/36}$ . 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 ${G}$ . In the case of treewidth we have a tree ${T}$ and a mapping ${f}$ from nodes ${i}$ of ${T}$ to subsets ${B_i}$ of the vertices of ${G}$ . The two conditions for ${f}$ to be a tree decomposition of ${G}$ are:

For every edge ${(u,v)}$ of ${G}$ , there is an ${i}$ such that ${u,v \in B_i}$ .
For every vertex ${v}$ of ${G}$ , the set of ${i}$ such that ${v \in B_i}$ forms a subtree of ${T}$ —in particular it is connected.

The treewidth is the minimum ${k}$ such that ${G}$ has a tree decomposition by sets ${B_i}$ of size at most ${k+1}$ . This number makes trees have treewidth 1. If ${G}$ has a cycle ${C}$ , the conditions combine to force ${k \geq 2}$ . The ${m \times m}$ square grid has treewidth ${m}$ , while ${n}$ -vertex expanders have treewidth ${\Omega(n)}$ .

A graph ${H}$ is a minor of ${G}$ if there is a mapping ${g}$ from nodes ${i}$ of ${H}$ to disjoint subsets ${A_i}$ of ${V(G)}$ such that:

For every edge ${(i,j)}$ in ${H}$ , there is an edge ${(u,v)}$ in ${G}$ such that ${u \in A_i}$ and ${v \in A_j}$ .
For every ${i}$ , the subgraph of ${G}$ induced by ${A_i}$ is connected.

Together these conditions mean one can obtain ${H}$ from ${G}$ by contracting each ${A_i}$ to a single vertex, then deleting edges until only those in ${H}$ remain. In Theorem 1, ${H}$ is a square grid. We’ve arranged the definitions to echo as much as possible. The correspondence is rough, but the tension between treewidth ${k}$ and grid minor-size ${k^{\delta}}$ 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.

Small Insights

One observation comes from the 1994 paper:

Lemma 2 There is a universal constant ${c}$ such that every ${n}$ -vertex planar graph is a minor of the ${cn \times cn}$ 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 ${d}$ such that for any planar ${n}$ -vertex graph ${H}$ , all graphs ${G}$ that do not have ${H}$ as a minor (i.e., for which ${H}$ is an “excluded minor”) have treewidth ${O(n^d)}$ .

Note that the treewidth bound is independent of the size of ${G}$ .

Two of the important little observations from the 2014 Chekuri-Chuzhoy paper are:

Claim 4 Let ${\{ x_{1},\dots,x_{n}\}}$ be any set of non-negative integers, with ${\sum_{i} x_{i} = N}$ and ${x_{i} \le 2N/3}$ for all ${i}$ . Then we can efficiently compute a partition ${(A,B)}$ of ${\{1,\dots,N\}}$ such that ${\sum_{i \in A}x_{i} \ge N/3}$ and ${\sum_{i \in B}x_{i} \ge N/3}$ .

Claim 5 Let ${T}$ be a rooted tree such that ${V(T) \ge \ell p}$ for some positive integers ${\ell}$ and ${p}$ . Then ${T}$ has at least ${\ell}$ leaves or ${T}$ has a root-to-leaf path of length at least ${p}$ .

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 ${k/\mathsf{polylog}(k)}$ . 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 ${\delta = 1/42}$ . Here is one slide that conveys the strategy; we’ve edited it to add a vertical bracket- ${h}$ 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 ${U \subset V(G)}$ is well-linked if for all ${A,B \subset U}$ with ${|A| = |B| = t}$ , ${1 \leq t \leq |U|}$ , there are ${t}$ -many node-disjoint paths connecting ${A}$ and ${B}$ . This allows paths of length ${0}$ when ${A}$ and ${B}$ share vertices.

The maximum size ${h = |U|}$ of a well-linked set ${U}$ is another graph invariant. Bruce Reed proved:

Lemma 7 For graphs of treewidth ${k}$ , ${h \leq k \leq 4h}$ .

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 ${h}$ enables one to find a grid minor of size ${\Omega(\sqrt{h})}$ on the side. To gain their tighter connections, the new papers relax the concept:

Definition 8 ${U}$ is ${\alpha}$ -well-linked if for all ${T,T' \subset U}$ with ${|T| = |T'| = t}$ , ${1 \leq t \leq |U|}$ , there is a flow from ${T}$ to ${T'}$ of congestion at most ${1/\alpha}$ .

The following result connects the bound ${\alpha}$ to the flow-building task. It meets one definition of ‘observation’ insofar as it is used as the definition of “ ${\alpha}$ -well-linked” in some other works by the authors.

Observation 9 If ${U}$ is ${\alpha}$ -well-linked in ${G}$ then for any partition of all of ${V(G)}$ into sides ${A}$ and ${B}$ , the number of edges crossing the partition is at least the minimum of ${\alpha|A\cap U|}$ and ${\alpha|B \cap U|}$ .

The newest paper also uses versions where ${t}$ is constrained to be at most some number ${k'}$ for which ${\alpha k'}$ then becomes another upper bound on edges across the ${A,B}$ 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?

11 Comments leave one →

Frank Vega permalink

June 9, 2015 3:00 pm

Dear Professor,

I have found a new complexity class that I called “equivalent-P” and I have showed it has a close relation with the P versus NP Problem. I have been making a paper that explain my ideas, and in the meantime, I decided to share them as a preprint in the web.

Here, I show you the abstract of the paper (so you can capture the idea):

“The P versus NP problem is one of the most important and unsolved problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by Kurt Gödel to John von Neumann in 1956. However, the precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in a seminal paper. We consider a new complexity class, called equivalent-P, which has a close relation with this problem. The class equivalent-P has those languages that contain ordered pairs of instances, where each one belongs to a specific problem in P, such that the two instances share a same solution, that is, the same certificate. We demonstrate that equivalent-P = NP and equivalent-P = P. In this way, we find the solution of P versus NP problem, that is, P = NP.”

In this preprint, I shall show that there is an NP-complete problem in equivalent-P and a P-complete problem in equivalent-P. Moreover, I shall show the complexity class equivalent-P is closed under reductions. Since P and NP are also closed under reductions, then we can conclude that P = NP.

You can read more on:

https://hal.archives-ouvertes.fr/hal-01161668/document

Kind regards,
Frank.

Loading...

Reply
- Cristóbal Camarero permalink
  
  June 11, 2015 1:49 am
  
  Frank, HORNSAT is a P-complete, so it is in P. As P is a subset of NP, HORNSAT is also in NP. If the “proof” of your “theorem 6.2” where correct you could get directly P=NP:
  “Proof. If a P-complete is in NP, then NP = P, because NP is closed under reductions (see Theorem X) and P too [9]. Therefore, this is a direct consequence of the above.”
  Which is obviously wrong.
  
  Loading...
  
  Reply
  - vegafrank permalink
    
    June 15, 2015 2:30 pm
    
    You are certainly right. However, this can be fix if we find a problem that is P-complete and equivalent-P-complete at the same time. I was wondering if this exists, that is a P-complete problem that can be reduced any two problem in P and that reduction guarantees if the two instances can share a same solution, then they will keep this property after the reduction. Unfortunately, I don’t know if such P-complete problem exists and I suppose that will be too difficult to find.
    
    Loading...
- Serge permalink
  
  June 11, 2015 6:05 pm
  
  The P versus NP problem is a logical fractal. It seems to be the proof-theoretic equivalent – in the sense of the Curry-Howard isomorphism – of a geometric fractal figure that’s actually the strange attractor of a chaotic process. Thus the two opposite opinions that P=NP and P!=NP both correspond respectively to the two lobes of a fractal Lorentz attractor. Therefore, any long-term attempt to solve the P versus NP problem is bound to exhibit the following characteristics:
  
  1) The mental process is endless – that is, you can prove neither P=NP nor P!=NP. This parallels the fact that a chaotic process never comes to an end.
  
  2) The more resources you put into trying to solve the problem, the harder it proves to be. This parallels the fact that a fractal figure exhibits new landscapes on whichever scale you try to explore it. By the way, it’s the only explanation I’ve found for why professionals and beginners feel equally competent on the P versus NP problem.
  
  You and I, just like virtually every complexity theorist – whether professional or amateur – have been trapped into a mental chaotic fractal process. It’s a very interesting phenomenon, one that forces you to always imagine new theories, although approximate ones. Likewise, exploring a Mandelbrot set will force you to discover forever renewed and approximate fractal landscapes.
  
  Loading...
  
  Reply
- Javaid permalink
  
  June 12, 2015 1:57 pm
  
  I don’t see how these comments are relevant to this post?
  
  Loading...
  
  Reply
  - Serge permalink
    
    June 12, 2015 7:26 pm
    
    “What are your favorite observations?”, asked Pip. If you think my comparison of the P=NP issue with fractal behavior is not an observation, then what is? You might not share it, but you can’t say it’s not an observation. Now if you really think it’s wrong, I’ll be delighted to read your arguments.
    
    Loading...
Javaid permalink

June 12, 2015 9:59 pm

Well, Serge, to me it appeared as if the other 2 responses were replies to Frank Vega’s comment, and which is certainly out of place.
The “location” of my comment somehow did not appear where I wanted to be- right after Frank’s..
So anyway, I was not referring to your comment in particular

Loading...

Reply
- Serge permalink
  
  June 17, 2015 8:03 am
  
  The lack of moderation also has interesting side-effects. Beginner’s insights, questions and inspirations get spelled out publicly without scholar filters. It’s a genuine art to let the professional speak to the professional, the amateur to the amateur, so that sometimes – too rarely to my taste – some interferences may occur. After all, determinism and randomness are the two teats of complexity theory…
  
  Loading...
  
  Reply
John Sidles permalink

June 13, 2015 7:57 am

Pip asks ” What are your favorite observations?”

At the risk of drifting off-topic, I’d like to remark how very often it happens that well-conducted scientific debates are immensely enjoyable beneficial … no matter who’s right!

It was Scott Aaronson’s Shtetl Optimized discussion of climate-change that brought this reflection to mind … from which the following news-and-discussion is excerpted.

————
CONGRATULATIONS AND FELICITATIONS TO GIL KALAI

To speak in praise of Scott’s remark …

Scott remarks (#181) “There’s exactly one thing that will make most CS [computer science] academics want to pay attention to you, […] it’s you producing high-quality technical work.”

Non-CS readers of Shtetl Optimized may benefit from an instance in which Scott himself (and Greg Kuperberg too) commendably “walk their talk”.

Namely, Gil Kalai’s work on the fundamental infeasibility of scalable quantum computation receives an attentive and respectful hearing from the CS community — respectful even from researchers like Scott and Greg who hold opposing views — in large measure because Gil is a sufficiently accomplished mathematician to be (deservedly) honored as one of the ten plenary speakers at the upcoming quadrennial meeting of the European Mathematical Society at the 7th European Congress of Mathematics (7ECM) (Berlin, July 18–22, 2016).

It’s worth mentioning too, that later this week the Hebrew University of Jerusalem will host a two-day MathFest in Honor of Gil Kalai’s 60th Birthday.

Conclusion The reasoned and respectful, yet lively and marvelously simulating discourse among researchers like Gil, Scott, and Greg (and many more names need to mentioned too … John Preskill, Steve Flammia, Aram Harrow, etc.) is of tremendous benefit to engineering researchers (like me) … no matter who proves to be right.

Long may this discourse continue in its full respectful vigor, with Nature and Reason as the joint arbiters. Would that climate-change arch-skeptics appreciated the virtues of this ancient and enlightened scholarly tradition.

Appreciation, congratulations, felicitations, and thanks especially are extended to Gil Kalai!

Loading...

Reply

	javaid aslam on 1968 vs 2024
	Ian Z aka nobrowser on 1968 vs 2024
	Enough is enough on 1968 vs 2024
	rjlipton on An Open Problem
	Jordan on An Open Problem
	Jon Awbrey on An Open Problem
	Blog Runner on An Open Problem
	William Gasarch on An Open Problem
	DL on An Open Problem
	Jon Awbrey on An Open Problem
	An Open Problem \| Gö… on Cargo Cult Redo
	Peter Gerdes on Women in Math Research
	Peter Gerdes on Women in Math Research
	rjlipton on Women in Math Research
	Cristóbal Camarero on Women in Math Research

a personal view of the theory of computation

Minor Insights Are Useful

The Result(s)

The Main Concepts

In Praise Of Minor Results

Small Insights

Well-Linked Observations

Open Problems

Like this:

Related

Trackbacks

Leave a ReplyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

Minor Insights Are Useful

The Result(s)

The Main Concepts

In Praise Of Minor Results

Small Insights

Well-Linked Observations

Open Problems

Share this:

Like this:

Related

Trackbacks

Leave a ReplyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

Discover more from Gödel's Lost Letter and P=NP