On cycle transversals and their connected variants in the absence of a small linear forest

DOI10.1007/s00453-020-00706-6zbMath1459.05332OpenAlexW2965619982MaRDI QIDQ5918178

Paweł Rzążewski, Konrad K. Dabrowski, Daniël Paulusma, Matthew Johnson, Carl Feghali, Giacomo Paesani

Publication date: 12 October 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00706-6

zbMATH Keywords

feedback vertex set\(H\)-free graphodd cycle transversalconnected transversal

Mathematics Subject Classification ID

Paths and cycles (05C38) Transversal (matching) theory (05D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

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 ⋮ Classifying subset feedback vertex set for \(H\)-free graphs ⋮ Connected feedback vertex set on AT-free graphs ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ 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
• 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
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Some simplified NP-complete graph problems
• Which problems have strongly exponential complexity?
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
• Independent feedback vertex set for \(P_5\)-free graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Boundary classes for graph problems involving non-local properties
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Graph Classes: A Survey
• Stable sets for (P_{6}, K_{2,3})-free graphs
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• The Price of Connectivity for Vertex Cover
• Parameterized Algorithms
• Connected Feedback Vertex Set in Planar 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
• On the complexity of \(k\)-SAT

This page was built for publication: On cycle transversals and their connected variants in the absence of a small linear forest