Separator theorem for graphs with an excluded minor and its applications

Noga Alon, Paul Seymour, Robin Thomas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

115 Scopus citations

Abstract

Let G be an n-vertex graph with nonnegative weights whose sum is 1 assigned to its vertices, and with no minor isomorphic to a given h-vertex graph H. We prove that there is a set X of no more than h3/2n 1/2 vertices of G whose deletion creates a graph in which the total weight of every connected component is at most 1/2 . This extends significantly a well-known theorem of R.J. Lipton and R.E. Tarjan for planar graphs. We exhibit an algorithm which finds, given an n-vertex graph G with weights as above and an h-vertex graph H, either such a set X or a minor of G isomorphic to H. The algorithm runs in time O(h 1/2 n 1/2 m), where m is the number of edges of G plus the number of its vertices. Our results supply extensions of the many known applications of the Lipton-Tarjan separator theorem from the class of planar graphs (or that of graphs with bounded genus) to any class of graphs with an excluded minor. For example, it follows that for any fixed graph H, given a graph G with n vertices and with no H-minor one can approximate the size of the maximum independent set of G up to a relative error of 1/√log n in polynomial time, find that size exactly and find the chromatic number of G in time 2O(√n) and solve any sparse system of n linear equations in n unknowns whose sparsity structure corresponds to G in time O(n3/2). We also describe a combinatorial application of our result which relates the tree-width of a graph to the maximum size of a Kh-minor in it.

Original languageEnglish (US)
Title of host publicationProc 22nd Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages293-299
Number of pages7
ISBN (Print)0897913612
StatePublished - Jan 1 1990
Externally publishedYes
EventProceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA
Duration: May 14 1990May 16 1990

Publication series

NameProc 22nd Annu ACM Symp Theory Comput

Other

OtherProceedings of the 22nd Annual ACM Symposium on Theory of Computing
CityBaltimore, MD, USA
Period5/14/905/16/90

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Separator theorem for graphs with an excluded minor and its applications'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Seymour, P., & Thomas, R. (1990). Separator theorem for graphs with an excluded minor and its applications. In Proc 22nd Annu ACM Symp Theory Comput (pp. 293-299). (Proc 22nd Annu ACM Symp Theory Comput). Publ by ACM.