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

DOI10.1016/j.jctb.2011.12.001zbMath1245.05103MaRDI 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 minor; feedback vertex set; FPT algorithm; cycle packing

Mathematics Subject Classification ID

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C83: Graph minors

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

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