Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem

DOI10.1016/J.JCTB.2011.12.001zbMath1245.05103OpenAlexW1997576329MaRDI QIDQ444386

Ken-ichi Kawarabayashi, Yusuke Kobayashi

Publication date: 14 August 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2011.12.001

zbMATH Keywords

graph minorfeedback vertex setFPT algorithmcycle packing

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Backdoors to Satisfaction ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Hitting Selected (Odd) Cycles ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Unnamed Item ⋮ Packing cycles through prescribed vertices under modularity constraints ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ Half-integral packing of odd cycles through prescribed vertices ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Disjoint cycles intersecting a set of vertices ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Unnamed Item ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ Backdoors to tractable answer set programming ⋮ Unnamed Item ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Graph minors. XXII. Irrelevant vertices in linkage problems
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Disjoint paths in graphs
• 2-linked graphs
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Graph minors. XIII: The disjoint paths problem
• Packing cycles through prescribed vertices
• Parameterized complexity of Vertex Cover variants
• On the odd-minor variant of Hadwiger's conjecture
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• A polyhedral approach to the feedback vertex set problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Approximation algorithms and hardness results for cycle packing problems
• A Min-Max Theorem on Feedback Vertex Sets

This page was built for publication: Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem