Subset Feedback Vertex Set Is Fixed-Parameter Tractable

DOI10.1007/978-3-642-22006-7_38zbMath1334.68096arXiv1004.2972OpenAlexW1776142702MaRDI QIDQ3012825

Marcin Pilipczuk, Jakub Onufry Wojtaszczyk, Michał Pilipczuk, Marek Cygan

Publication date: 6 July 2011

Published in: SIAM Journal on Discrete Mathematics, Automata, Languages and Programming (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilityiterative compressionsubset feeback vertex set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Backdoors to Satisfaction ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ A polynomial kernel for block graph deletion ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Clique Cover and Graph Separation ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Hitting Selected (Odd) Cycles ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Unnamed Item ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Packing cycles through prescribed vertices under modularity constraints ⋮ Subset feedback vertex sets in chordal graphs ⋮ Enumerating minimal subset feedback vertex sets ⋮ Finding temporal paths under waiting time constraints ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Half-integral packing of odd cycles through prescribed vertices ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Disjoint cycles intersecting a set of vertices ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ An FPT algorithm for edge subset feedback edge set ⋮ Unnamed Item ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ Graphs without two vertex-disjoint \(S\)-cycles ⋮ 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 ⋮ FPT algorithms for generalized feedback vertex set problems ⋮ On group feedback vertex set parameterized by the size of the cutset

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Finding odd cycle transversals.
• Parameterized graph separation problems
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• A cubic kernel for feedback vertex set and loop cutset
• Approximating minimum feedback sets and multicuts in directed graphs
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• On Feedback Vertex Set New Measure and New Structures
• ON DISJOINT CYCLES
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Parameterized and Exact Computation
• Multicut is FPT
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Computing and Combinatorics