Classifying subset feedback vertex set for \(H\)-free graphs

DOI10.1007/978-3-031-15914-5_30arXiv2201.00430OpenAlexW4312793153MaRDI QIDQ6039438

Paweł Rzążewski, Giacomo Paesani, Daniël Paulusma

Publication date: 5 May 2023

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

feedback vertex setcomplexity dichotomy\(H\)-free graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs

Cites Work

• Unnamed Item
• Graph classes with structured neighborhoods and algorithmic applications
• Enumerating minimal subset feedback vertex sets
• Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
• Subset feedback vertex set on graphs of bounded independent set size
• On line graphs of subcubic triangle-free graphs
• Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs
• Hitting Selected (Odd) Cycles
• 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
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time

This page was built for publication: Classifying subset feedback vertex set for \(H\)-free graphs