Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs

DOI10.1137/22M1468864zbMath1498.05275arXiv2105.02736OpenAlexW3159532254MaRDI QIDQ5043646

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

Publication date: 6 October 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

blockforestfeedback vertex seteven cycle transversalodd cactus

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of block designs (05B05) Transversal (matching) theory (05D15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Classifying subset feedback vertex set for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ A parameterized algorithm for subset feedback vertex set in tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• An improved deterministic parameterized algorithm for cactus vertex deletion
• On line graphs of subcubic triangle-free graphs
• Quick but odd growth of cacti
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
• Parameterized Algorithms for Even Cycle Transversal
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• On cycle transversals and their connected variants in the absence of a small linear forest
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs

This page was built for publication: Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs