zbMATH — the first resource for mathematics

Improved tree decomposition based algorithms for domination-like problems. (English) Zbl 1059.68598
Rajsbaum, Sergio (ed.), LATIN 2002: Theoretical informatics. 5th Latin American symposium, Cancun, Mexico, April 3–6, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43400-3). Lect. Notes Comput. Sci. 2286, 613-627 (2002).
Summary: We present an improved dynamic programming strategy for DOMINATING SET and related problems on graphs that are given together with a tree decomposition of width \(k\). We obtain an \(O(4^k n)\) algorithm for DOMINATING SET, where \(n\) is the number of nodes of the tree decomposition. This result improves the previously best known algorithm of Telle and Proskurowski running in time \(O(9^k n)\). The key to our result is an argument on a certain “monotonicity” in the table updating process during dynamic programming. Moreover, various other domination-like problems as discussed by Telle and Proskurowski are treated with our technique. We gain improvements on the base of the exponential term in the running time ranging between 55% and 68% in most of these cases. These results mean significant breakthroughs concerning practical implementations.
For the entire collection see [Zbl 0989.00058].

68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: Link