Abstract
We show how the value of various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al. that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O(log n) (minimum front size and treewidth) and O(log2 n) (pathwidth and minimum elimination tree height) times the optimal values. In addition we examine the existence of bounded approximation algorithms for the parameters, and show that unless P = NP, there are no absolute approximation algorithms for them.
The research of this author is partially supported by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM).
The research of this author is supported by the Foundation for Computer Science (S.I.O.N.) of the Netherlands Organization for Scientific Research (N.W.O.) and by the ESPRIT II Basic Research Actions of the EC under Contract No. 3075 (project ALCOM).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arnborg, D. G. Corneil, A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal of Algebraic and Discrete Methods, 8:277–284, 1987.
S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs, J. of Algorithms, 12:308–340, 1991.
S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey. BIT, 25:2–23, 1985.
H. L. Bodlaender. Polynomial algorithms for Graph Isomorphism and Chromatic Index on partial k-trees. J. Algorithms, 11:631–644, 1990.
H. L. Bodlaender and T. Kloks. Better algorithms for the pathwidth and treewidth of graphs. Proc. 18th ICALP, pages 544–555. Springer Verlag, Lect. Notes in Comp. Sc. 510, 1991.
H. L. Bodlaender and R. H. Möhring. The pathwidth and treewidth of cographs. In Proc. 2nd Scandinavian Workshop on Algorithm Theory, pages 301–309. Springer Verlag Lect. Notes in Computer Science vol. 447, 1990.
N. Deo, M. S. Krishnamoorty and M. A. Langston. Exact and approximate solutions for the gate matrix layout problem. IEEE Transactions on Computer-Aided Design, 6:79–84, 1987.
J.R. Egan and C.L. Liu. Bipartite folding and partitioning of a PLA, IEEE Trans. CAD, 3:191–199, 1984.
I. S. Duff and J. K. Reid. The multifrontal solution of indefinite sparse symmetric linear equations. ACM Transactions on Mathematical Software, 9:302–325, 1983.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
J. A. George. Nested dissection of a regular finite element mesh. SIAM Journal of Numerical Analysis, 10:345–363, 1973.
J. R. Gilbert. Some nested dissection order is nearly optimal. Information Processing Letters, 6:325–328, 1987/88.
F. Harary. Graph Theory, Addison-Wesley, 1969.
P. Klein, A. Agrawal, R. Ravi, and S. Rao. Approximation through multicommodity flow. In Proceedings of the 31th Annual Symposium on Foundations of Computer Science, IEEE, pages 726–737, 1990.
D. König. Theorie der Graphen, Reprinted by Chelsea Publishing Company, New York, 1950.
J. Lagergren. Efficient parallel algorithms for tree-decomposition and related problems. In Proceedings of the 31th Annual Symposium on Foundations of Computer Science, IEEE, pages 173–182, 1990.
J. van Leeuwen. Graph Algorithms. In Handbook of Theoretical Computer Science. A: Algorithms and Complexity Theory, North Holland, Amsterdam, 1990.
F. T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximate algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, IEEE pages 422–431, 1988.
F. T. Leighton. Personal communication, 1990.
C. E. Leiserson and J. G. Lewis. Orderings for parallel sparse symmetric factorization. An unpublished manuscript, 1988.
R. J. Lipton, D. J. Rose and R. E. Tarjan. Generalized nested dissection. SIAM Journal of Numerical Analysis 16:346–358, 1979.
J. W. H. Liu. The multifrontal method for sparse matrix solution: theory and practice. Tech. Report CS-90-04, York University, North York, Ontario, Canada. To appear.
R. H. Möhring. Graph problems related to gate matrix layout and PLA folding. In Computing Supplementum 7 (G. Tinhofer et al, eds), page 17–51. Springer-Verlag, Vienna, 1990.
A. Pothen. The complexity of optimal elimination trees. Tech. Report CS-88-16, Pennsylvania State University, 1988.
N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7:309–322, 1986.
N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. Manuscript, 1986.
N. Robertson and P. D. Seymour. Graph minors. X. Obstructions to tree-decompositions. To appear in J. Combinatorial Theory, Ser. B., 1991.
D.J. Rose, R.E. Tarjan and G.S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. Vol. 5, No. 2, 266–283, 1976.
P.D. Seymour and R. Thomas. Call Routing and the Ratcatcher. Manuscript, 1991.
M. Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal of Algebraic and Discrete Methods, 2:77–79, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T. (1992). Approximating treewidth, pathwidth, and minimum elimination tree height. In: Schmidt, G., Berghammer, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 1991. Lecture Notes in Computer Science, vol 570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55121-2_1
Download citation
DOI: https://doi.org/10.1007/3-540-55121-2_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55121-8
Online ISBN: 978-3-540-46735-9
eBook Packages: Springer Book Archive