Finding approximate separators and computing tree width quickly

ABSTRACT

We show that for any fixed k, there is a linear-time algorithm which given a graph G either: (i) finds a cutset X of G with |X| ≤ k such that no component of G–X contains more than 3/4|G–X| vertices, or (ii) determines that for any set X of vertices of G with |X| ≤ k, there is a component of G–X which contains more than 2/3|G–X| vertices. This approximate separator algorithm can be used to develop and O(n log n algorithm for determining if G has a tree decomposition of width at most k (for fixed k) and finding such a tree decomposition if it exists.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: N. Alon , P. Seymour , R. Thomas, A separator theorem for graphs with an excluded minor and its applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.293-299, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100254]
• 3: Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
• 4: Jens Lagergren , Stefan Arnborg, Finding minimal forbidden minors using a finite congruence, Proceedings of the 18th international colloquium on Automata, languages and programming, p.532-543, June 1991, Madrid, Spain
• 5: Stefan Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded, decomposability—a survey, BIT, v.25 n.1, p.2-23, 1985
• 6: Stefan Arnborg , Derek G. Corneil , Andrzej Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.277-284, April 1, 1987 [doi>10.1137/0608024]
• 7: Stefan Arnborg , Andrzej Proskurowski, Characterization and recognition of partial 3-trees, SIAM Journal on Algebraic and Discrete Methods, v.7 n.2, p.305-314, April 1986 [doi>10.1137/0607033]
• 8: Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
• 9: D. Bienstock , Paul Seymour, Monotonicity in graph searching, Journal of Algorithms, v.12 n.2, p.239-245, June 1991 [doi>10.1016/0196-6774(91)90003-H]
• 10: Dan Bienstock , Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a forest, Journal of Combinatorial Theory Series B, v.52 n.2, p.274-283, July 1991 [doi>10.1016/0095-8956(91)90068-U]
• 11: H. L. Bodlaender, DYNAMIC PROGRAMMING ON GRAPHS WITH BOUNDED TREEWIDTH, Massachusetts Institute of Technology, Cambridge, MA, 1987
• 12: H.L. Bodlaender: NC-Algorithms for Graphs with Bounded Tree-width, RUU-CS-88-4, University of Utrecht, 1988.
• 13: H.L. Bodlaender: Improved Self-reduction Algorithms from Graphs with Bounded Tree-width, RUU-CS-88-29, University of Utrecht, 1988.
• 14: Hans L. Boblaender, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, Journal of Algorithms, v.11 n.4, p.631-643, Dec. 1990 [doi>10.1016/0196-6774(90)90013-5]
• 15: Hans L. Bodlaender , Ton Kloks, Better algorithms for the pathwidth and treewidth of graphs, Proceedings of the 18th international colloquium on Automata, languages and programming, p.544-555, June 1991, Madrid, Spain
• 16: R.L. Breiseh: An intuitive approach to speleotopology, SoutheJegfern Carets (published by the Southwestern Region of the National Speleological Society) 6, No.5 (1967), 72-78.
• 17: Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H]
• 18: B. Courcelle: The Monadic Second Order Logic of Graphs. III. Tree-width, Forbidden Minors, and Complexity Issues, Universit6 de Bordeaux, Report 1-8852, 1988.
• 19: John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
• 20: M. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
• 21: S.T. Hedetniemi: Open problems concerning the theory of algorithms on partial k-trees, working paper, 1987.
• 22: M Kirousis , C H Papadimitriou, Searching and pebbling, Theoretical Computer Science, v.47 n.2, p.205-218, Nov. 1986
• 23: L.M. Kirousis and C.H. Papadimitriou: Interval graphs and searching, Discrete Math 55 (1985), 181-184.
• 24: A. Lapaugh: Recontamination does not help to search a graph, Tech. Report 335, Dept. of Elec. Eng. and Comput. Sci., Princeton University, 1982.
• 25: R.J. Lipton and R.E. Tarjan: A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), 177-189.
• 26: R.J. Lipton and R.E. Tarjan: Applications of a planar separator theorem, Proc. 18th. FOC5 (1977), 162-170.
• 27: R.J. Lipton and R.E. Tarjan: Applications of a planar separator theorem, SIAM J. Comput. 9 (1980), 615-627.
• 28: J. Matous#k and R. Thomas: On the complexity of finding iso-and other morphisms for partial /e-trees, unpublished paper, 1988.
• 29: T.D. Parsons: Pursuit-evasion in a graph, in: Theory and Application of 9raphs (Y. Alavi and D.R. Lick, Eds.), New York/Berlin, pp. 426-441, Springer Verlag, 1976.
• 30: N. Robertson and P.D. Seymour: Graph minors. II. Algorithmic aspects of tree-width, j. Algo- #th#,a 7 (1986), 309-322.
• 31: Neil Robertson , P. D. Seymour, Graph minors: X. obstructions to tree-decomposition, Journal of Combinatorial Theory Series B, v.52 n.2, p.153-190, July 1991 [doi>10.1016/0095-8956(91)90061-N]
• 32: N. Robertson and P.D. Seymour: Graph minors XIII, The disjoint path problem, preprint, Sept. 1986.
• 33: P.D. Seymour and 1%. Thomas: Graph searching, and a minimax theorem for tree-width, submitted (manuscript 1988).
• 34: P. Scheffier: Linear-time algorithms for NP-complete problems restricted to partial k-trees, preprint AdW, R-Math-03/87, Karl- Weierstrafl inst. Ktr Math., Berlin, 1987.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Performance, Theory