Vertex Cover Reconfiguration and Beyond

DOI10.1007/978-3-319-13075-0_36MaRDI QIDQ2942651zbMATH OpenOpenAlexFDO

Authors Amer E. Mouawad, N. Nishimura, Venkatesh Raman

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In the Vertex Cover Reconfiguration (VCR) problem, given a graph $G$, positive integers $k$ and $ell$ and two vertex covers $S$ and $T$ of $G$ of size at most $k$, we determine whether $S$ can be transformed into $T$ by a sequence of at most $ell$ vertex additions or removals such that every operation results in a vertex cover of size at most $k$. Motivated by results establishing the W[1]-hardness of VCR when parameterized by $ell$, we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains W[1]-hard on bipartite graphs, is NP-hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs.

Recommendations

• Reconfiguration of vertex covers in a graph
• Reconfiguring k-path vertex covers
• Vertex cover structural parameterization revisited
• scientific article; zbMATH DE number 1420918
• Vertex cover: Further observations and further improvements
• Extended formulations for vertex cover
• On the approximability of the vertex cover and related problems
• Experimental and Efficient Algorithms
• The generalized vertex cover problem and some variations
• scientific article; zbMATH DE number 2119748

Cites work

• Complexity of independent set reconfigurability problems
• Connectedness of the graph of vertex-colourings
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Local search: is brute-force avoidable?
• On the complexity of reconfiguration problems
• On the parameterized complexity of multiple-interval graph problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Some simplified NP-complete graph problems
• The complexity of rerouting shortest paths
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Cited in

(24)

• Reconfiguration on nowhere dense graph classes
• Editorial: Special issue on reconfiguration problems
• On girth and the parameterized complexity of token sliding and token jumping
• Invitation to combinatorial reconfiguration
• Introduction to reconfiguration
• Computing the flip distance between triangulations
• Reconfiguration of maximum-weight b-matchings in a graph
• Vertex cover meets scheduling
• Vertex cover: Further observations and further improvements
• Reconfiguration of Steiner trees in an unweighted graph
• Finding shortest paths between graph colourings
• Reconfiguration of vertex covers in a graph
• Replica Placement via Capacitated Vertex Cover
• Finding shortest paths between graph colourings
• Core influence mechanism on vertex-cover problem through leaf-removal-core breaking
• Shortest reconfiguration paths in the solution space of Boolean formulas
• The complexity of dominating set reconfiguration
• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• The complexity of dominating set reconfiguration
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Exploring the gap between treedepth and vertex cover through vertex integrity
• scientific article; zbMATH DE number 7765402 (Why is no real title available?)
• TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$
• Reconfiguring k-path vertex covers

This page was built for publication: Vertex Cover Reconfiguration and Beyond

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