Classifying subset feedback vertex set for H-free graphs

DOI10.1016/J.TCS.2024.114624MaRDI QIDQ6549683zbMATH OpenFDO

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

Publication date 4 June 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114624

zbMATH Keywords

complexity dichotomyfeedback vertex setH-free graphssubset feedback vertex setweighted variants

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• Classifying subset feedback vertex set for H-free graphs
• Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Enumerating minimal subset feedback vertex sets
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Graph classes with structured neighborhoods and algorithmic applications
• Hitting selected (odd) cycles
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 7788454 (Why is no real title available?)
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• On cycle transversals and their connected variants in the absence of a small linear forest
• On line graphs of subcubic triangle-free graphs
• Sparse induced subgraphs in P₆-free graphs
• Subset feedback vertex set on graphs of bounded independent set size

Cited in

(2)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6549683)