Linear time algorithms for NP-hard problems restricted to partial k- trees. (English) Zbl 0666.68067
We present and illustrate by a sequence of examples an algorithm paradigm for solving NP-hard problems on graphs resticted to partial graphs of k- trees and given with an embedding in a k-tree. Such algorithms, linear in the size of the graph but exponential or superexponential in k, exist for most NP-hard problems that have linear time algorithms for trees. The examples used are optimization problems involving independent sets, dominating sets, graph coloring, Hamiltonian circuits, network reliability and minimum vertex deletion forbidden subgraphs. The results generalize previous results for series-parallel graphs, bandwidth- constrained graphs, and non-serial dynamic programming.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C05 | Trees |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
NP-hard problems on graphs; linear time algorithms for trees; optimization; dynamic programmingReferences:
| [1] | Arnborg, S., Reduced state enumeration: Another algorithm for reliability evaluation, IEEE Trans. Reliability, 27, 101-105 (1978) · Zbl 0436.60062 |
| [2] | Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability: A survey, BIT, 25, 2-23 (1985) · Zbl 0573.68018 |
| [3] | Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 305-314 (1986) · Zbl 0597.05027 |
| [4] | Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebraic Discrete Methods, 8, 277-284 (1987) · Zbl 0611.05022 |
| [5] | Bern, M. W.; Lawler, E. L.; Wong, A. L., Linear time computation of optimal subgraphs of decomposable graphs, J. Algorithms, 8, 216-235 (1987) · Zbl 0618.68058 |
| [6] | Bertele, U.; Brioschi, F., Nonserial Dynamic Programming (1972), Academic Press: Academic Press New York · Zbl 0187.17801 |
| [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-543 (1987) · Zbl 0635.05040 |
| [8] | Corneil, D. G.; Lerchs, H.; Burlingham, L. Stewart, Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057 |
| [9] | Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [10] | Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., 1, 180-187 (1972) · Zbl 0227.05116 |
| [11] | Johnson, D. S., The NP-completeness column: An ongoing guide, J Algorithms, 4 (1984) · Zbl 0545.68032 |
| [12] | Lelann, G., (Distributed Systems: Towards a Formal Approach (1977), IFIP), 155-160 |
| [13] | Lingas, A., Subgraph isomorphism for easily separable graphs of bounded valence, (Proceedings Workshop on Graph-Theoretic Concepts in Computer Science (1985), Trauner) |
| [14] | Monien, B.; Sudborough, I. H., Bandwidth-constrained NP-complete problems, (Proceedings 13th ACM STOC (1981)), 207-217 · Zbl 0594.68042 |
| [15] | Robertson, N.; Seymour, P. D., Graph minors II: Algorithmic aspects of freewidth, J. Algorithms, 7, 309-322 (1986) · Zbl 0611.05017 |
| [16] | Rose, D., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597-609 (1970) · Zbl 0216.02602 |
| [17] | Rosenthal, A., Computing the reliability of a complex network, SIAM J. Appl. Math., 32, 384-393 (1977) · Zbl 0379.90048 |
| [18] | Rosenthal, A., Dynamic programming is optimal for nonserial optimization problems, SIAM J. Comput., 11, 47-59 (1982) · Zbl 0479.90081 |
| [19] | Seese, D., Tree-partite graphs and the complexity of algorithms, (P-Math 08/86 (1986), Akademie der Wissenschaften der DDR, Karl Weierstrass Institut für Mathematik), Preprint · Zbl 0574.68036 |
| [20] | Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on seriesparallel graphs, J. ACM, 29, 623-641 (1982) · Zbl 0485.68055 |
| [21] | Wimer, T. V.; Hedetniemi, S. T.; Laskar, R., A methodology for constructing linear graph algorithms (1985), DCS, Clemson University: DCS, Clemson University Clemson, SC · Zbl 0603.68040 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
