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

DOI10.1016/j.tcs.2024.114624zbMATH Open1542.68163MaRDI QIDQ6549683

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

Publication date: 4 June 2024

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

zbMATH Keywords

feedback vertex setcomplexity dichotomysubset feedback vertex setH-free graphsweighted variants

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• 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
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Classifying subset feedback vertex set for \(H\)-free graphs
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Sparse induced subgraphs in \(P_6\)-free graphs

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