Faster Algorithms For Vertex Partitioning Problems Parameterized by Clique-width
In: Theoret. Comput. Sci. 535(May 2014), pp. 16-24; (2013) S. 16-24
Online
report
Zugriff:
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.
Comment: 13 pages, 5 figures
Titel: |
Faster Algorithms For Vertex Partitioning Problems Parameterized by Clique-width
|
---|---|
Autor/in / Beteiligte Person: | Oum, Sang-il ; Sæther, Sigve Hortemo ; Vatshelle, Martin |
Link: | |
Quelle: | Theoret. Comput. Sci. 535(May 2014), pp. 16-24; (2013) S. 16-24 |
Veröffentlichung: | 2013 |
Medientyp: | report |
DOI: | 10.1016/j.tcs.2014.03.024 |
Schlagwort: |
|
Sonstiges: |
|