Computing subset transversals in \(H\)-free graphs

DOI10.1016/j.tcs.2021.12.010OpenAlexW4205776219MaRDI QIDQ5918462

Daniël Paulusma, Nick Brettell, Matthew Johnson, Giacomo Paesani

Publication date: 18 January 2022

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

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

zbMATH Keywords

complexity dichotomyhereditary graph class\(H\)-freeodd cycle transversalfeedback vertex

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Classifying subset feedback vertex set for \(H\)-free graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Enumerating minimal subset feedback vertex sets
• Computing weighted subset transversals in \(H\)-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Complement reducible graphs
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• A randomized polynomial kernel for subset feedback vertex set
• Independent feedback vertex set for \(P_5\)-free graphs
• Mim-width. II. The feedback vertex set problem
• Subset feedback vertex set on graphs of bounded independent set size
• Faster exact algorithms for some terminal set problems
• On line graphs of subcubic triangle-free graphs
• Subset feedback vertex sets in chordal graphs
• Half-integrality, LP-branching, and FPT Algorithms
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey
• The Pathwidth and Treewidth of Cographs
• Representative Sets and Irrelevant Vertices
• Parameterized Algorithms for Even Cycle Transversal
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Hitting Selected (Odd) Cycles
• Independent Set in P₅-Free Graphs in Polynomial Time
• Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
• On cycle transversals and their connected variants in the absence of a small linear forest
• Computing subset transversals in \(H\)-free graphs
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Bounding the mim‐width of hereditary graph classes

This page was built for publication: Computing subset transversals in \(H\)-free graphs