Faster Algorithms Parameterized by Clique-width.
Sang‐il Oum, Sigve Hortemo Sæther, Martin Vatshelle · 2013
Many NP-hard problems, such as Dominating Set, are FPT parameterized by clique-width. For graphs of clique-width k given with a kexpression, Dominating Set can be solved in 4knO(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 (23k − 1)expression via rank-width and then solving Dominating Set using the (23k − 1)-expression, the above algorithm will only give a runtime of 42 3k nO(1). There have been results which overcome this exponential jump; the best known algorithm can solve Dominating Set in time 2O(k 2)nO(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 2O(k log k)nO(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 2O(k log k)nO(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.