zbMATH — the first resource for mathematics

Faster algorithms on branch and clique decompositions. (English) Zbl 1287.05147
Hliněný, Petr (ed.) et al., Mathematical foundations of computer science 2010. 35th international symposium, MFCS 2010, Brno, Czech Republic, August 23–27, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15154-5/pbk). Lecture Notes in Computer Science 6281, 174-185 (2010).
Summary: 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 ^{*}(4^{k })\) algorithm. Here \(\omega \) is the exponent in the running time of the best matrix multiplication algorithm (currently \(\omega < 2.376\)). For graphs of cliquewidth \(k\), we improve from \(O ^{*}(8^{k })\) to \(O ^{*}(4^{k })\). 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 \([\rho ,\sigma ]\)-domination problems on branch decompositions if \(\rho \) and \(\sigma \) are finite or cofinite. The algorithms presented in this paper either attain or are very close to natural lower bounds for these problems.
For the entire collection see [Zbl 1194.68039].

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI