Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity

DOI10.1016/j.tcs.2017.09.033zbMath1380.68219arXiv1706.08050OpenAlexW2963603765MaRDI QIDQ1680547

Martin Milanič, Nina Chiarelli, Matthew Johnson, Daniël Paulusma, Tatiana Romina Hartinger

Publication date: 16 November 2017

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

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

zbMATH Keywords

vertex coverfeedback vertex setprice of connectivityodd cycle transversal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ Computing weighted subset transversals in \(H\)-free graphs ⋮ Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Connected feedback vertex set on AT-free graphs ⋮ Unnamed Item ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Computing subset transversals in \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The price of connectivity for dominating set: upper bounds and complexity
• The price of connectivity for feedback vertex set
• On parameterized independent feedback vertex set
• FPT algorithms for connected feedback vertex set
• The price of connectivity for cycle transversals
• Connected vertex covers in dense graphs
• Vertex and edge covers with clustering properties: Complexity and algorithms
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• The node-deletion problem for hereditary properties is NP-complete
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• On enumerating all minimal solutions of feedback problems
• Independent feedback vertex sets for graphs of bounded diameter
• Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
• Connecting face hitting sets in planar graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Boundary classes for graph problems involving non-local properties
• Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• On Hadwiger's Number and the Stability Number
• On graphs with polynomially solvable maximum-weight clique problem
• On Restricted Two-Factors
• A New Algorithm for Generating All the Maximal Independent Sets
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Perfect connected-dominant graphs
• The Price of Connectivity for Vertex Cover
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Connected Feedback Vertex Set in Planar Graphs