[ACM Press the 42nd ACM symposium - Cambridge, Massachusetts, USA (2010.06.05-2010.06.08)] Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10 - A shorter proof of the graph minor algorithm

✍ Scribed by Kawarabayashi, Ken-ichi; Wollan, Paul

• Book ID: 126814429
• Publisher: ACM Press
• Year: 2010
• Tongue: English
• Weight: 481 KB
• Category: Article
• ISBN: 1450300502
• DOI: 10.1145/1806689.1806784

✦ Synopsis

At the core of the seminal Graph Minor Theory of Robertson and Seymour is a powerful theorem which describes the structure of graphs excluding a fixed minor. This result is used to prove Wagner's conjecture and provide a polynomial time algorithm for the disjoint paths problem when the number of the terminals is fixed (i.e, the Graph Minor Algorithm). However, both results require the full power of the Graph Minor Theory, i.e, the structure theorem.

In this paper, we show that this is not true in the latter case. Namely, we provide a new and much simpler proof of the correctness of the Graph Minor Algorithm. Specifically, we prove the "Unique Linkage Theorem" without using Graph Minors structure theorem. The new argument, in addition to being simpler, is much shorter, cutting the proof by at least 200 pages. We also give a new full proof of correctness of an algorithm for the well-known edge-disjoint paths problem when the number of the terminals is fixed, which is at most 25 pages long.