Complexity of finding embeddings in a k-tree. (English) Zbl 0611.05022

A k-tree is an undirected graph that can be reduced to the k-complete graph by a sequence of removals of k-degree vertices with completely connected neighbors. A partial k-tree is a subgraph of a k-tree; \(k_ t(G)\) is the smallest k for which G is a partial k-tree.
The problem PARTIAL K-TREE is: given a graph G and an integer k, is \(k_ t(G)\leq k?\) The authors prove that PARTIAL K-TREE problem is NP-complete. For a fixed k, they present a polynomial time algorithm for that problem which, unfortunately, is of degree k.
Reviewer: G.Slutzki


05C10 Planar graphs; geometric and topological aspects of graph theory
68Q25 Analysis of algorithms and problem complexity
90C39 Dynamic programming
Full Text: DOI


[1] Arnborg, S., Reduced state enumeration—another algorithm for reliability evaluation, IEEE Trans. Reliability, R-27, 101, (1978) · Zbl 0436.60062
[2] Arnborg, Stefan, Efficient algorithms for combinatorial problems on graphs with bounded decomposability—a survey, BIT, 25, 2, (1985) · Zbl 0573.68018
[3] Arnborg, Stefan; Proskurowski, Andrzej, Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 305, (1986) · Zbl 0597.05027
[4] Linear time algorithms for NP-hard problems on graphs embedded in k-treesTRITA-NA-8404The Royal Institute of Technology1984
[5] Bondy, J. A.; Murty, U. S. R., Graph theory with applications, (1976) · Zbl 1226.05083
[6] Colbourn, CharlesJ.; Proskurowski, Andrzej, Concurrent transmissions in broadcast networks, Automata, languages and programming (Antwerp, 1984), 172, 128, (1984), Springer, Berlin · Zbl 0554.94021
[7] Corneil, D. G.; Keil, J. M., A dynamic programming approach to the dominating set problem on k-trees, SIAM J. Algebraic Discrete Methods, 8, 535, (1987) · Zbl 0635.05040
[8] Farley, ArthurM., Networks immune to isolated failures, Networks, 11, 255, (1981) · Zbl 0459.94036
[9] Farley, ArthurM.; Proskurowski, Andrzej, Networks immune to isolated line failures, Networks, 12, 393, (1982) · Zbl 0493.94020
[10] Garey, MichaelR.; Johnson, DavidS., Computers and intractability, (1979) · Zbl 0411.68039
[11] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539, (1964) · Zbl 0121.26003
[12] The most reliable series parallel networksTR 83-7Dept. of Computing Science, University of Saskatchewan1983
[13] Proskurowski, Andrzej, Separating subgraphs in k-trees: cables and caterpillars, Discrete Math., 49, 275, (1984) · Zbl 0543.05041
[14] Rose, DonaldJ., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597, (1970) · Zbl 0216.02602
[15] Rose, DonaldJ., On simple characterizations of k-trees, Discrete Math., 7, 317, (1974) · Zbl 0285.05128
[16] Wald, A.; Colbourn, C. J., Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 159, (1983) · Zbl 0529.68036
[17] Yannakakis, Mihalis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 77, (1981) · Zbl 0496.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.