Abstract
Many NP-hard problems on graphs have polynomial, in fact usually linear, dynamic programming algorithms when restricted to partial k-trees (graphs of treewidth bounded by k), for fixed values of k. We investigate the practicality of such algorithms, both in terms of their complexity and their derivation, and account for the dependency on the treewidth k. We define a general procedure to derive the details of table updates in the dynamic programming solution algorithms. This procedure is based on a binary parse tree of the input graph. We give a formal description of vertex subset optimization problems in a class that includes several variants of domination, independence, efficiency and packing. We give algorithms for any problem in this class, which take a graph G, integer k and a width k tree-decomposition of G as input, and solve the problem on G in O(n24k) steps.
This research was supported in part by NSF grant CCR9213439
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
K.Abrahamson and M.Fellows, Finite automata, bounded treewidth and wellquasiordering, to appear in Contemporary Mathematics (1992).
S.Arnborg, S.Hedetniemi and A.Proskurowski (editors) Algorithms on graphs with bounded treewidth, Special issue of Discrete Applied Mathematics.
S.Arnborg, J.Lagergren and D.Seese, Easy problems for tree-decomposable graphs, J. of Algorithms 12(1991) 308–340.
S. Arnborg and A. Proskurowski, Characterization and recognition of partial 3-trees, SIAM J. Alg. and Discr. Methods 7 (1986) 305–314.
S.Arnborg and A.Proskurowski, Linear time algorithms for NP-hard problems on graphs embedded in k-trees, Discr. Appl. Math. 23 (1989) 11–24.
M.W.Bern, E.L.Lawler and A.L.Wong, Linear-time computation of optimal subgraphs of decomposable graphs, J. of Algorithms 8(1987) 216–235.
H.L.Bodlaender, Dynamic programming on graphs with bounded treewidth, Proceedings ICALP 88, LNCS vol.317 (1988) 105–119.
H.L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, to appear in Proceedings STOC'93.
J.A.Bondy and U.S.R.Murty, Graph theory with applications, 1976.
R.B.Borie, R.G.Parker and C.A.Tovey, Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursive constructed graph families, Algorithmica, 7:555–582, 1992.
E.J.Cockayne, B.L.Hartnell, S.T.Hedetniemi and R.Laskar, Perfect domination in graphs, manuscript (1992), to appear in Special issue of JCISS.
B.Courcelle, The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation, 85, (1990) 12–75.
M.Garey and D.Johnson, Computers and Intractability, Freeman, San Fransisco, 1979.
D.Grinstead and P.Slater, A recurrence template for several parameters in seriesparallel graphs, manuscript (1992).
J. van Leeuwen, Graph Algorithms, in Handbook of Theoretical Computer Science vol. A, Elsevier, Amsterdam, (1990) pg. 550.
J.Matoušek and R.Thomas, Algorithms finding tree-decompositions of graphs, J. of Algorithms, 12 (1991) 1–22.
A.Proskurowski and M.Syslo, Efficient computations in tree-like graphs, in Computing Suppl 7, (1990) 1–15.
N. Robertson and P.D. Seymour, Graph minors II: algorithmic aspects of tree-width, J. of Algorithms 7 (1986) 309–322.
D.Sanders, On linear recognition of tree-width at most four, manuscript (1992).
K.Takamizawa, T.Nishizeki and N.Saito, Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM 29(1982) 623–641.
J.A.Teile, Characterization of domination-type parameters in graphs, to appear in Proceedings of 24th SouthEastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium.
J.A.Telle, Complexity of domination-type problems in graphs, submitted BIT.
J.A.Telle and A.Proskurowski, Efficient sets in partial k-trees, to appear in Domination in graphs, Special volume of Discrete Applied Mathematics.
T.Wimer, Linear time algorithms on k-terminal graphs. Ph.D. thesis, Clemson University, South Carolina, (1988).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Telle, J.A., Proskurowski, A. (1993). Practical algorithms on partial k-trees with an application to domination-like problems. In: Dehne, F., Sack, JR., Santoro, N., Whitesides, S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57155-8_284
Download citation
DOI: https://doi.org/10.1007/3-540-57155-8_284
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57155-1
Online ISBN: 978-3-540-47918-5
eBook Packages: Springer Book Archive