Many NP-hard problems, such as DOMINATING SET, are FPT parameterized by clique-width. For graphs of clique-width k given with a k-expression, DOMINATING SET can be solved in 4(k)n(O(1)) time. However, no FPT algorithm is known for computing an optimal k-expression. For a graph of clique-width k, if we rely on known algorithms to compute a (2(3k)-1)-expression via rank-width and then solving DOMINATING SET using the (2(3k)-1)-expression, the above algorithm will only give a runtime of 4(23k)n(O(1)). There have been results which overcome this exponential jump; the best known algorithm can solve DOMINATING SET in time 2(O(k2))n(O(1)) by avoiding constructing a k-expression Bui-Xuan et al. (2013) [7]. We improve this to 2O((k logk))n(O(1)). Indeed, we show that for a graph of clique-width k, a large class of domination and partitioning problems (LC-VSP), including DOMINATING SET, can be solved in 2(O(k log k))n(O(1)).
Our main tool is a variant of rank-width using the rank of a 0-1 matrix over the rational field instead of the binary field.

- Publisher
- ELSEVIER SCIENCE BV

- Issue Date
- 2014-05

- Language
- English

- Article Type
- Article

- Keywords
BRANCH-WIDTH; DOMINATING SETS; RANK-WIDTH; GRAPHS; DECOMPOSITION; OBSTRUCTIONS

- Citation
THEORETICAL COMPUTER SCIENCE, v.535, pp.16 - 24

- ISSN
- 0304-3975

- Appears in Collection
- MA-Journal Papers(저널논문)

- Files in This Item

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.