Abstract
We combine two techniques recently introduced to obtain faster dynamic programming algorithms for optimization problems on graph decompositions. The unification of generalized fast subset convolution and fast matrix multiplication yields significant improvements to the running time of previous algorithms for several optimization problems. As an example, we give an \(O^{*}(3^{\frac{\omega}{2}k})\) time algorithm for Minimum Dominating Set on graphs of branchwidth k, improving on the previous O *(4k) algorithm. Here ω is the exponent in the running time of the best matrix multiplication algorithm (currently ω< 2.376). For graphs of cliquewidth k, we improve from O *(8k) to O *(4k). We also obtain an algorithm for counting the number of perfect matchings of a graph, given a branch decomposition of width k, that runs in time \(O^{*}(2^{\frac{\omega}{2}k})\). Generalizing these approaches, we obtain faster algorithms for all so-called [ρ,σ]-domination problems on branch decompositions if ρ and σ are finite or cofinite. The algorithms presented in this paper either attain or are very close to natural lower bounds for these problems.
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
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Möbius: Fast Subset Convolution. In: STOC 2007, pp. 67–74. ACM, New York (2007)
Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Inform. Comput. 167, 86–119 (2001)
Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 61–74. Springer, Heidelberg (2009)
Coppersmith, D., Winograd, S.: Matrix Multiplication via Arithmetic Progressions. J. Symbolic Comput. 9, 251–280 (1990)
Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. System. Sci. 46(2), 218–270 (1993)
Courcelle, B., Olariu, S.: Upper bounds on the clique-width of graphs. Discrete Appl. Math. 101, 77–114 (2000)
Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 95–106. Springer, Heidelberg (2005)
Dorn, F.: Dynamic Programming and Fast Matrix Multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 280–291. Springer, Heidelberg (2006)
Fomin, F.V., Thilikos, D.M.: Dominating Sets in Planar Graphs: Branch-width and Exponential Speed-up. In: SODA 2003, pp. 386–397. ACM, New York (2003)
Fomin, F.V., Thilikos, D.M.: A simple and fast approach for solving problems on planar graphs. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 56–67. Springer, Heidelberg (2004)
Fürer, M.: Faster Integer Multiplication. In: STOC 2007, pp. 57–66. ACM, New York (2007)
Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory B 52(2), 153–190 (1991)
Telle, J.A.: Complexity of Domination-Type Problems in Graphs. Nordic J. Comput. 1, 157–171 (1994)
Telle, J.A., Proskurowski, A.: Algorithms for Vertex Partitioning Problems on Partial k-Trees. SIAM J. Discrete Math. 10, 529–550 (1997)
Valiant, L.G.: The Complexity of Computing the Permanent. Theor. Comput. Sci. 8, 189–201 (1979)
van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 566–577. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodlaender, H.L., van Leeuwen, E.J., van Rooij, J.M.M., Vatshelle, M. (2010). Faster Algorithms on Branch and Clique Decompositions. In: Hliněný, P., Kučera, A. (eds) Mathematical Foundations of Computer Science 2010. MFCS 2010. Lecture Notes in Computer Science, vol 6281. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15155-2_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-15155-2_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15154-5
Online ISBN: 978-3-642-15155-2
eBook Packages: Computer ScienceComputer Science (R0)