Faster algorithms for vertex partitioning problems parameterized by clique-width

• Dominating set for graphs of clique-width k.
• Naive approach will solve in time 4(2(3k))poly(n).
• The previous best algorithm by Bui-Xuan et al.: 2(O(k2))poly(n) by using rank-width.
• Ours: 2O(klogk)poly(n) by inventing a new trick using QQ-rank-width.
• This is the FIRST paper to use QQ-rank-width for the faster dynamic-programming algorithm.

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 4knO(1)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)(23k−1)-expression via rank-width and then solving Dominating Set using the (23k−1)(23k−1)-expression, the above algorithm will only give a runtime of 423knO(1)423knO(1). There have been results which overcome this exponential jump; the best known algorithm can solve Dominating Set in time 2O(k2)nO(1)2O(k2)nO(1) by avoiding constructing a k-expression Bui-Xuan et al. (2013) [7]. We improve this to 2O(klogk)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(klogk)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.