Faster Algorithms For Vertex Partitioning Problems Parameterized by Clique-width

Abstract

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^{2^{3k}}{n}^{O(1)}$. There have been results which overcome this exponential jump; the best known algorithm can solve Dominating Set in time $2^{O(k^2)}{n}^{O(1)}$ by avoiding constructing a $k$-expression [Bui-Xuan, Telle, and Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoret. Comput. Sci., 2013. doi:10.1016/j.tcs.2013.01.009]. We improve this to $2^{O(k\log k)}{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.

13 pages, 5 figures

References in corpus (1)

• A comparison of two approaches for polynomial time algorithms computing basic graph parameters

Cited by in corpus (5)

• Rank-width: Algorithmic and structural results
• Linear Recognition of Almost Interval Graphs
• Star Colouring of Bounded Degree Graphs and Regular Graphs
• Fast exact algorithms for some connectivity problems parametrized by clique-width
• Solving Hamiltonian Cycle by an EPT Algorithm for a Non-sparse Parameter