research-article

A shorter proof of the graph minor algorithm: the unique linkage theorem

Authors:

Ken-ichi Kawarabayashi,

Paul WollanAuthors Info & Claims

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Pages 687 - 694

https://doi.org/10.1145/1806689.1806784

Published: 05 June 2010 Publication History

Abstract

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.

References

[1]

S. Arnborg and A. Proskurowski,Linear time algorithms for NP-hard problems restricted to partial -trees, Discrete Appl. Math. 23 (1989), 11--24.

Digital Library

[2]

H. L. Bodlaender,A linear-time algorithm for finding tree-decomposition of smalltreewidth, SIAM J. Comput. 25 (1996), 1305--1317.

Digital Library

[3]

H. L. Bodlaender, F. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh and D. Thilikos,(Meta) kernelization, to appear in 50th Annual Symposium on Foundations of Computer Science (FOCS 2009).

Digital Library

[4]

E. D. Demaine, F. Fomin, M. Hajiaghayi, and D. Thilikos,Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, J. ACM 52 (2005), 1--29.

Digital Library

[5]

E. D. Demaine, M. Hajiaghayi, and K. Kawarabayashi,Algorithmic graph minor theory: Decomposition, approximation and coloring, Proc. 46th Annual Symposium on Foundations of Computer Science (FOCS'05),637--646, (2005).

Digital Library

[6]

E. D. Demaine, M. Hajiaghayi, and B. Mohar,Approximation algorithms via contraction decomposition, Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07),278--287, (2007).

Digital Library

[7]

R. Diestel,Graph Theory, 3rd Edition, Springer, 2005.

[8]

R. G. Downey and M.R. Fellows,Parameterized complexity, Springer-Verlag, 1999.

Digital Library

[9]

Z. Dvorak, D. Kral and R. Thomas,Coloring triangle-free graphs on surfaces, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, 120--129.

Digital Library

[10]

M.R. Fellows and M. A. Langston,Nonconstructive tools for proving polynomial-time decidability, J. ACM 35, (1988), 727--739.

Digital Library

[11]

A. Frank,Packing paths, cuts and circuits -- a survey,in Paths, Flows and VLSI-Layout,B. Korte, L. Lovász, H. J. Promel and A. Schrijver (Eds.),Springer-Verlag, Berlin, 1990, 49--100.

[12]

M. Grohe,Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23, (2003), 613--632.

Digital Library

[13]

R. M. Karp,On the computational complexity of combinatorial problems, Networks 5 (1975), 45--68.

Digital Library

[14]

K. Kawarabayashi,Planarity allowing few error vertices in linear time, 50th Annual Symposium on Foundations of Computer Science (FOCS 2009),639--648, (2009).

Digital Library

[15]

K. Kawarabayashi and B. Reed,Computing crossing number in linear time, Proc. 39th ACM Symposium on Theory of Computing (STOC'07), 382--390, (2007).

Digital Library

[16]

K. Kawarabayashi and B. Mohar,Graph and Map Isomorphism and all polyhedral embeddings in linear time, Proc. 40th ACM Symposium on Theory of Computing (STOC'08), 471--480, (2008).

Digital Library

[17]

K. Kawarabayashi, B. Mohar and B. Reed,A simpler linear time algorithm for embedding graphs into an arbitrary surface and thegenus of boundedtree-width graphs, Proc. 49th Annual Symposium on Foundations of Computer Science (FOCS'08),771--780, (2008).

Digital Library

[18]

K. Kawarabayashi, Y. Kobayashi and B. Reed,The disjoint paths problem in quaratic time, submitted.

[19]

K. Kawarabayashi and Y. Kobayashi,The edge-disjoint paths problem for 4-edge-connected graphs andEulerian graphs, ACM-SIAM Symposium on Discrete Algorithms(SODA), 345--353, (2010).

Digital Library

[20]

Y. Kobayashi and K. Kawarabayashi,Algorithms for finding an induced cycle in planar graphs and boundedgenus graphs, ACM-SIAM Symposium on Discrete Algorithms(SODA), 1146--1155, (2009).

Digital Library

[21]

L. Lovász,in Combinatorics, Proc. Fifith Hungarian Combin. Colloq.,Keszthely, 1976, Vol. II, p.1208, North-Holland, Amsterdam, 1978.

[22]

J. F. Lynch,The equivalence of theorem proving and the interconnection problem, ACM SIGDA Newsletter 5 (1975), 31--65.

Digital Library

[23]

D. Marx and I. Schlotter,Obtaining a planar graph by vertex deletion, Proc. the 33rd Workshop on Graph-Theoretic Concepts in Computer Scienece,292--303, (2007).

Digital Library

[24]

M. Milgram and P. Ungar, Amer. Math. Monthly, 85, (1978), 664--668.

[25]

B. Reed,Tree width and tangles: a new connectivity measure and some applications, in "Surveys in Combinatorics, 1997 (London)",London Math. Soc. Lecture Note Ser. 241, Cambridge Univ.Press, Cambridge, 87--162, (1997).

[26]

B. Reed, N. Robertson, A. Schrijver and P. D. Seymour,Finding disjoint trees in planar graphs in linear time,Contemp. Math., 147, Amer. Math. Soc., Providence, RI, 1993, 295--301.

[27]

N. Robertson and P. D. Seymour,An outline of a disjoint paths algorithm, in Paths, Flows, and VLSI-Layout,B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver (Eds.),Springer-Verlag, Berlin, 1990, 267--292.

[28]

N. Robertson and P. D. Seymour, Graph minors. VI.Disjoint paths across a disk, J. Combin. Theory Ser. B, 41(1986), 115--138.

Digital Library

[29]

N. Robertson and P. D. Seymour, Graph minors. VII.Disjoint paths on a surface, J. Combin. Theory Ser. B, 45(1988), 212--254.

Digital Library

[30]

N. Robertson and P. D. Seymour,Graph minors IX. Disjoint crossed paths, J. Combin. Theory Ser. B, 49 (1990), 40--77.

Digital Library

[31]

N. Robertson and P. D. Seymour,Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1995), 65--110.

Digital Library

[32]

N. Robertson and P. D. Seymour,Graph minors. XV. Giant Steps, J. Combin. Theory Ser. B 68 (1996), 112--148.

Digital Library

[33]

N. Robertson and P. D. Seymour,Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B 89 (2003), 43--76.

Digital Library

[34]

N. Robertson and P. D. Seymour,Graph minors. XXI. Graphs with unique linkages, J. Combin. Theory Ser. B 99 (2009), 583--616.

Digital Library

[35]

N. Robertson and P. D. Seymour,Graph minors. XXII. Irrelevant vertices in linkage problems,to appear in J. Combin. Theory Ser. B.

Digital Library

[36]

A. Schrijver,Combinatorial Optimization: Polyhedra and Efficiency, number 24 inAlgorithm and Combinatorics, Springer Verlag, 2003.

Cited By

Thilikos DWiederrecht S(2024)Killing a VortexJournal of the ACM10.1145/366464871:4(1-56)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3664648
Włodarczyk MZehavi M(2023)Planar Disjoint Paths, Treewidth, and Kernels2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00044(649-662)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00044
Sau IStamoulis GThilikos D(2023) k-apices of minor-closed graph classes. I. Bounding the obstructionsJournal of Combinatorial Theory Series B10.1016/j.jctb.2023.02.012161:C(180-227)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.jctb.2023.02.012
Show More Cited By

Index Terms

A shorter proof of the graph minor algorithm: the unique linkage theorem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Paths and connectivity problems

Recommendations

A simpler algorithm and shorter proof for the graph minor decomposition
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

At the core of the Robertson-Seymour theory of graph minors lies a powerful decomposition theorem which captures, for any fixed graph H, the common structural features of all the graphs which do not contain H as a minor. Robertson and Seymour used this ...
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction

We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of ...
Minor obstructions for apex-pseudoforests
Abstract
A graph is called a pseudoforest if none of its connected components contains more than one cycle. A graph is an apex-pseudoforest if it can become a pseudoforest by removing one of its vertices. We identify 33 graphs that form the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

June 2010

812 pages

ISBN:9781450300506

DOI:10.1145/1806689

General Chair:
Michael Mitzenmacher
Harvard
,
Program Chair:
Leonard J. Schulman
Caltech

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'10

Sponsor:

SIGACT

STOC'10: Symposium on Theory of Computing

June 5 - 8, 2010

Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
494
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)2

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Thilikos DWiederrecht S(2024)Killing a VortexJournal of the ACM10.1145/366464871:4(1-56)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3664648
Włodarczyk MZehavi M(2023)Planar Disjoint Paths, Treewidth, and Kernels2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00044(649-662)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00044
Sau IStamoulis GThilikos D(2023) k-apices of minor-closed graph classes. I. Bounding the obstructionsJournal of Combinatorial Theory Series B10.1016/j.jctb.2023.02.012161:C(180-227)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.jctb.2023.02.012
Sau IStamoulis GThilikos D(2022)k-apices of Minor-closed Graph Classes. II. Parameterized AlgorithmsACM Transactions on Algorithms10.1145/351902818:3(1-30)Online publication date: 11-Oct-2022
https://dl.acm.org/doi/10.1145/3519028
Thilikos DWiederrecht S(2022)Killing a vortex2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00104(1069-1080)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00104
Diner ÖGiannopoulou AStamoulis GThilikos D(2022)Block Elimination DistanceGraphs and Combinatorics10.1007/s00373-022-02513-y38:5Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00373-022-02513-y
Lokshtanov DMisra PPilipczuk MSaurabh SZehavi MMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)An exponential time parameterized algorithm for planar disjoint pathsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384250(1307-1316)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384250
Dieng YGavoille C(2020)On the Treewidth of Planar Minor Free GraphsInnovations and Interdisciplinary Solutions for Underserved Areas10.1007/978-3-030-51051-0_17(238-250)Online publication date: 6-Aug-2020
https://doi.org/10.1007/978-3-030-51051-0_17
Lokshtanov DSaurabh SZehavi M(2020)Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint PathsTreewidth, Kernels, and Algorithms10.1007/978-3-030-42071-0_9(112-128)Online publication date: 20-Apr-2020
https://doi.org/10.1007/978-3-030-42071-0_9
Fleszar KMnich MSpoerhase J(2018)New algorithms for maximum disjoint paths based on tree-likenessMathematical Programming: Series A and B10.1007/s10107-017-1199-3171:1-2(433-461)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10107-017-1199-3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents