Abstract
Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in problems can be solved in polynomial time. We show that if C is a class of graphs which is modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the treewidth and the minimum fill-in problems on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms, that use respectively O(n) and O(n 3) time for treewidth and minimum fill-in.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability-A survey. BIT, 25:2–23, 1985.
S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth., 8:277–284, 1987.
L. Babel. Triangulating graphs with few P 4’s. Disc. Appl. Math., 89:45–57, 1998.
H. L. Bodlaender, T. Kloks, and D. Kratsch. Treewidth and pathwidth of permutation graphs. SIAM J. Disc. Math., 8(4):606–616, 1995.
H. L. Bodlaender and R. H. Möhring. The pathwidth and treewidth of cographs. SIAM J. Disc. Math., 6:181–188, 1993.
H. L. Bodlaender and U. Rotics. Computing the treewidth and the minimum fill-in with the modular decomposition. Technical Report CS-UU-2001-22, Institute of Information and Computing Sciences, Utrecht University, Utrecht, the Netherlands, 2001. ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-2001/2001-22.pdf.
V. Bouchitté and I. Todinca. Listing all potential maximal cliques of a graph. In H. Reidel and S. Tison, editors, Proceedings STACS’00, pages 503–515. Springer Verlag, Lecture Notes in Computer Science, vol. 1770, 2000.
V. Bouchitté and I. Todinca. Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput., 31:212–232, 2001.
H. Broersma, E. Dahlhaus, and T. Kloks. Algorithms for the treewidth and minimum fill-in of HHD-free graphs. In Proceedings 23nd International Workshop on Graph-Theoretic Concepts in Computer Science WG’97, pages 109–117. Springer Verlag, Lecture Notes in Computer Science, vol. 1335, 1997.
H. Broersma, E. Dahlhaus, and T. Kloks. A linear time algorithm for minimum fill in and treewidth for distance hereditary graphs. Disc. Appl. Math., 99:367–400, 2000.
H. Buer and R. H. Möhring. A fast algorithm for the decomposition of graphs and posets. Mathematics of Operations Research, 8(2):170–184, 1983.
A. Cournier and M. Habib. A new linear algorithm for modular decomposition. In T. Sophie, editor, Trees in algebra and programming, CAAP’94, pages 68–84. Springer Verlag, Lecture Notes in Computer Science, vol. 787, 1994.
E. Dahlhaus. Minimum fill-in and treewidth for graphs modularly decomposable into chordal graphs. In Proceedings 24nd International Workshop on Graph-Theoretic Concepts in Computer Science WG’98, pages 351–358. Springer Verlag, Lecture Notes in Computer Science, vol. 1517, 1998.
E. Dahlhaus, J. Gustedt, and R. M. McConnell. Efficient and practical modular decomposition. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 26–35, 1997.
W. Espelage, F. Gurski, and E. Wanke. Deciding clique-width for graphs of bounded treewidth. In Proceedings WADS 2001, pages 87–98. Springer Verlag, Lecture Notes in Computer Science, vol. 2125, 2001.
T. Kloks. Treewidth of circle graphs. Int. J. Found. Computer Science, 7:111–120, 1996.
T. Kloks and D. Kratsch. Listing all minimal separators of a graph. SIAM J. Comput., 27(3):605–613, 1998.
R. M. McConnell and J. Spinrad. Modular decomposition and transitive orientation. Disc. Math., 201:189–241, 1999.
R. H. Möhring. Graph problems related to gate matrix layout and PLA folding. In E. Mayr, H. Noltemeier, and M. SysFlo, editors, Computational Graph Theory, Comuting Suppl. 7, pages 17–51. Springer Verlag, 1990.
N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7:309–322, 1986.
R. Sundaram, K. Sher Singh, and C. Pandu Rangan. Treewidth of circular-arc graphs. SIAM J. Disc. Math., 7:647–655, 1994.
M. Yannakakis. Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth., 2:77–79, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodlaender, H.L., Rotics, U. (2002). Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition. In: Penttonen, M., Schmidt, E.M. (eds) Algorithm Theory — SWAT 2002. SWAT 2002. Lecture Notes in Computer Science, vol 2368. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45471-3_40
Download citation
DOI: https://doi.org/10.1007/3-540-45471-3_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43866-3
Online ISBN: 978-3-540-45471-7
eBook Packages: Springer Book Archive