research-article

Free access

A simpler algorithm and shorter proof for the graph minor decomposition

Authors:

Ken-ichi Kawarabayashi,

Paul WollanAuthors Info & Claims

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

Pages 451 - 458

https://doi.org/10.1145/1993636.1993697

Published: 06 June 2011 Publication History

Abstract

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 result to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation, as well as give a polynomial time algorithm for the disjoint paths problem when the number of the terminals is fixed. The theorem has since found numerous applications, both in graph theory and theoretical computer science. The original proof runs more than 400 pages and the techniques used are highly non-trivial.

In this paper, we give a simplified algorithm for finding the decomposition based on a new constructive proof of the decomposition theorem for graphs excluding a fixed minor H. The new proof is both dramatically simpler and shorter, making these results and techniques more accessible. The algorithm runs in time O(n³), as does the original algorithm of Robertson and Seymour. Moreover, our proof gives an explicit bound on the constants in the O notation, whereas the original proof of Robertson and Seymour does not.

Supplementary Material

JPG File (stoc_8a_2.jpg)

Download
20.25 KB

MP4 File (stoc_8a_2.mp4)

Download
106.87 MB

References

[1]

N. Alon, P. D. Seymour, and R. Thomas. A separator theorem for non-planar graphs. J. Amer. Math. Soc., 3:801--809, 1990.

[2]

B. S. Baker. Approximation algorithms for np-complete problems on planar graphs. J. Assoc. Comput. Mach., 41:153--180, 1994.

Digital Library

[3]

M. Charikar and A. Sahai. Dimension reduction in the $l_1$ norm. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), pages 551--560. IEEE, 2002.

Digital Library

[4]

C. Chekuri, A. Gupta, I. Newman, Y. Rabinovich, and S. Alistair. Embedding k-outerplanar graphs into l₁. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pages 527--536. ACM-SIAM, 2003.

Digital Library

[5]

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:1--29, 2005.

Digital Library

[6]

E. D. Demaine and M. Hajiaghayi. Fast algorithms for hard graph problems: Bidimensionality, minors and local treewidth. Lect. Note Comput. Sci., 3383:517--533, 2004.

Digital Library

[7]

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

Digital Library

[8]

M. DeVos, G. Ding, B. Oporowski, D. Sanders, B. Reed, P. D. Seymour, and D. Vertigan. Excluding any graph as a minor allows a low tree-width 2-coloring. J. Combin. Theory Ser. B, 91:25--41, 2004.

Digital Library

[9]

R. Diestel. Graph Theory. Springer-Verlag, Berlin, 2005.

[10]

D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27:275--291, 2000.

[11]

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

Digital Library

[12]

A. Gupta, I. Newman, Y. Rabinovich, and S. Alistair. Cuts, trees and $\ell_1$-embeddings of graphs. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS'99), pages 399--409. IEEE, 1999.

Digital Library

[13]

T. Ibaraki and H. Nagamochi. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7:583--596, 1992.

[14]

R. Kapadia, Z. Li, and B. Reed. A linear time algorithm to test the 2-path problem. manuscript.

[15]

K. Kawarabayashi and B. Reed. A separator theorem in minor-closed classes. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS'10), pages 153--162. IEEE, 2010.

Digital Library

[16]

K. Kawarabayashi and P. Wollan. A shorter proof of the graph minors algorithm- the unique linkage theorem. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing(STOC'10), pages 687--694. ACM, 2010.

Digital Library

[17]

P. N. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC'93), pages 682--690. ACM, 1993.

Digital Library

[18]

R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9:615--627, 1980.

Digital Library

[19]

L. Lovasz. Graph minor theory. B. Amer. Math. Soc., 43:75--86, 2005.

[20]

S. A. Plotkin, S. Rao, and W. D. Smith. Shallow excluded minors and improved graph decompositions. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94), pages 462--470. ACM-SIAM, 1994.

Digital Library

[21]

N. Robertson and P. D. Seymour. Graph minors. v: Excluding a planar graph. J. Combin. Theory Ser. B, 41:92--114, 1986.

Digital Library

[22]

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

Digital Library

[23]

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

Digital Library

[24]

N. Robertson and P. D. Seymour. Graph minors. xi: Circuits on a surface. J. Combin. Theory Ser. B, 60:72--106, 1994.

Digital Library

[25]

N. Robertson and P. D. Seymour. Graph minors. ivx: Extending an embedding. J. Combin. Theory Ser. B, 65:23--50, 1995.

Digital Library

[26]

N. Robertson and P. D. Seymour. Graph minors. xii: Distance on a surface. J. Combin. Theory Ser. B, 64:240--272, 1995.

Digital Library

[27]

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

Digital Library

[28]

N. Robertson and P. D. Seymour. Graph minors. xv: Giant steps. J. Combin. Theory Ser. B, 68:112--148, 1996.

Digital Library

[29]

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

Digital Library

[30]

N. Robertson and P. D. Seymour. Graph minors. xx: Wagner's conjecture. J. Combin. Theory Ser. B, 92:325--357, 2004.

Digital Library

[31]

R. E. Tarjan. Data structures and network algorithmsl. SIAM, Philadelphia, Pennsylvania, 1983.

Digital Library

[32]

T. Tholey. Solving the 2-disjoint paths problem in nearly linear time. Theory Comput Syst, 39:51--78, 2004.

[33]

K. Wagner. Uber eine eigenschaft der ebenen komplexe. Math. Ann., 114:570--590, 1937.

Cited By

Dujmović VEsperet LMorin PWood D(2023)Proof of the Clustered Hadwiger Conjecture2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00116(1921-1930)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00116
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
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
Show More Cited By

Index Terms

A simpler algorithm and shorter proof for the graph minor decomposition
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Paths and connectivity problems

Recommendations

A shorter proof of the graph minor algorithm: the unique linkage theorem
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

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 ...
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 '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

June 2011

840 pages

ISBN:9781450306911

DOI:10.1145/1993636

General Chair:
Lance Fortnow
Northwestern University
,
Program Chair:
Salil Vadhan
Harvard University

Copyright © 2011 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: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'11

Sponsor:

SIGACT

STOC'11: Symposium on Theory of Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

STOC '11 Paper Acceptance Rate 84 of 304 submissions, 28%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
801
Total Downloads

Downloads (Last 12 months)118
Downloads (Last 6 weeks)12

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dujmović VEsperet LMorin PWood D(2023)Proof of the Clustered Hadwiger Conjecture2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00116(1921-1930)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00116
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
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
Pilipczuk MSiebertz SChan T(2019)Polynomial bounds for centered colorings on proper minor-closed graph classesProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310526(1501-1520)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310526
Garnero VPaul CSau IThilikos D(2019)Explicit Linear Kernels for Packing ProblemsAlgorithmica10.1007/s00453-018-0495-581:4(1615-1656)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00453-018-0495-5
Haeupler BLi JZuzic GNewport CKeidar I(2018)Minor Excluded Network Families Admit Fast Distributed AlgorithmsProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212776(465-474)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3212734.3212776
Grohe M(2016)Tangles and Connectivity in GraphsLanguage and Automata Theory and Applications10.1007/978-3-319-30000-9_2(24-41)Online publication date: 26-Feb-2016
https://doi.org/10.1007/978-3-319-30000-9_2
Grohe MSchweitzer PServedio RRubinfeld R(2015)Computing with TanglesProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746587(683-692)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746587
Grohe MMarx D(2015)Structure Theorem and Isomorphism Test for Graphs with Excluded Topological SubgraphsSIAM Journal on Computing10.1137/12089223444:1(114-159)Online publication date: 18-Feb-2015
https://dl.acm.org/doi/10.1137/120892234
Kawarabayashi KKhanna S(2013)Totally odd subdivisions and parity subdivisionsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627890(1013-1029)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627890
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents