More applications of the d-neighbor equivalence: acyclicity and connectivity constraints

DOI10.1137/20M1350571MaRDI QIDQ5009336zbMATH OpenOpenAlexFDO

Authors Benjamin Bergougnoux, Mamadou Moustapha Kanté

Publication date 20 August 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(\sigma,\rho\)-domination\(d\)-neighbor equivalenceclique-widthconnectivity problemfeedback vertex setmim-widthrank-width

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}cdot{n}^{O(1)}$, $2^{O(klog(k))}cdot{n}^{O(1)}$, $2^{O(k^2)}cdot{n}^{O(1)}$ and $n^{O(k)}$ where $k$ is respectively the clique-width, $mathbfQ$-rank-width, rank-width and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013] and the rank-based approach introduced in [Bodlaender, Cygan, Kratsch and Nederlof, ICALP 2013]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for $W[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$ and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $mathbfQ$-rank-width and the rank-width of the input graph.

Recommendations

• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.

Cites work

• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• An exact algorithm for connected red-blue dominating set
• Approximating clique-width and branch-width
• Boolean-width of graphs
• Computing the largest bond of a graph
• 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
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Graph classes with structured neighborhoods and algorithmic applications
• Graph minors. X: Obstructions to tree-decomposition
• scientific article; zbMATH DE number 3779513 (Why is no real title available?)
• scientific article; zbMATH DE number 7650221 (Why is no real title available?)
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Mim-width. I. Induced path problems
• Mim-width. II. The feedback vertex set problem
• Minimum semidefinite rank of outerplanar graphs and the tree cover number
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Multiplying matrices faster than coppersmith-winograd
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• On the complexity of k-SAT
• Parameterized algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The Complexity of Coloring Circular Arcs and Chords
• Tree-coloring problems of bounded treewidth graphs
• Upper bounds to the clique width of graphs
• Which problems have strongly exponential complexity?

Cited in

(19)

• List k-colouring P_t-free graphs: a mim-width perspective
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• MIP formulations for induced graph optimization problems: a tutorial
• On \(d\)-stable locally checkable problems parameterized by mim-width
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
• Approximation hardness of domination problems on generalized convex graphs
• A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
• Finding induced subgraphs from graphs with small mim-width
• Domination and cut problems on chordal graphs with bounded leafage
• On the hardness of generalized domination problems parameterized by mim-width
• Comparing width parameters on graph classes
• Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
• Tight bounds for some classical problems parameterized by cutwidth
• On algorithmic applications of \(\mathcal{F}\)-branchwidth
• Hamiltonicity parameterized by mim-width Is (indeed) para-NP-hard
• Solving problems on generalized convex graphs via mim-width

This page was built for publication: More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints

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