Fast exact algorithms for some connectivity problems parameterized by clique-width

DOI10.1016/J.TCS.2019.02.030MaRDI QIDQ2420640zbMATH OpenOpenAlexWikidataFDO

Authors Benjamin Bergougnoux, Mamadou Moustapha Kanté

Publication date 6 June 2019

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

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

zbMATH Keywords

connected \(\sigma, \rho\)-domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Abstract: Given a clique-width $k$-expression of a graph $G$, we provide $2^{O(k)}cdotn$ time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We also propose a $2^{O(k)}cdotn$ time algorithm for Feedback Vertex Set. The best running times for all the considered cases were either $2^{O(kcdotlog(k))}cdot{n}^{O(1)}$ or worse.

Recommendations

• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Algorithmic lower bounds for problems parameterized by clique-width
• Exact algorithms for a loading problem with bounded clique width
• A fast algorithm for the maximum clique problem
• Exact algorithms for dominating clique problems (extended abstract)
• Exact algorithms for maximum clique: a computational study
• Fast algorithms for the maximum clique problem on massive sparse graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• scientific article; zbMATH DE number 4072403

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Approximating clique-width and branch-width
• Approximating rank-width and clique-width quickly
• Clique-width: when hard does not mean impossible
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Feedback vertex set on graphs of low clique-width
• Fundamentals of parameterized complexity
• Graph minors. II. Algorithmic aspects of tree-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Handle-rewriting hypergraph grammars
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• On the complexity of \(k\)-SAT
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Upper bounds to the clique width of graphs

Cited in

(13)

• On the terminal connection problem
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• On the computational difficulty of the terminal connection problem
• Polynomial Turing compressions for some graph problems parameterized by modular-width
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
• Feedback vertex set on graphs of low cliquewidth
• Feedback vertex set on graphs of low clique-width
• MIP formulations for induced graph optimization problems: a tutorial
• More applications of the \(d\)-neighbor equivalence: connectivity and acyclicity constraints
• Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
• Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space

This page was built for publication: Fast exact algorithms for some connectivity problems parameterized by clique-width

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