Faster algorithms for vertex partitioning problems parameterized by clique-width

DOI10.1016/J.TCS.2014.03.024MaRDI QIDQ2447760zbMATH OpenOpenAlexFDO

Authors Sang-Il Oum, Sigve Hortemo Sæther, Martin Vatshelle

Publication date 29 April 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.0224

zbMATH Keywords

clique-widthdynamic programminggeneralized dominationparameterized complexityrank-width

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Dynamic programming (90C39)

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(klogk)}{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(klogk)}{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.

Recommendations

• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Clique-width: on the price of generality

Cites work

• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Approximating clique-width and branch-width
• Boolean-width of graphs
• Dominating sets for split and bipartite graphs
• Dominating Sets in Chordal Graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Faster algorithms on branch and clique decompositions
• Graph classes with structured neighborhoods and algorithmic applications
• Graph minors. X: Obstructions to tree-decomposition
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Interval deletion is fixed-parameter tractable
• Linear time solvable optimization problems on graphs of bounded clique-width
• Lower bounds based on the exponential time hypothesis
• Obstructions to branch-decomposition of matroids
• On the clique-width of some perfect graph classes
• On the Relationship Between Clique-Width and Treewidth
• Parametrized complexity theory.
• Practical algorithms on partial k-trees with an application to domination-like problems
• Proper interval vertex deletion
• Rank‐width is less than or equal to branch‐width
• Simpler parameterized algorithm for OCT
• Testing branch-width
• The rank-width of edge-coloured graphs
• The rank-width of the square grid
• Upper bounds to the clique width of graphs

Cited in

(14)

• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Star colouring of bounded degree graphs and regular graphs
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Rank-width: algorithmic and structural results
• When an optimal dominating set with given constraints exists
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• Several notions of rank-width for countable graphs
• More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Parameterized complexity for iterated type partitions and modular-width
• On the complexity of minimizing energy consumption of partitioning DAG tasks

This page was built for publication: Faster algorithms for vertex partitioning problems parameterized by clique-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2447760)