A randomized polynomial kernel for subset feedback vertex set

DOI10.1007/S00224-017-9805-6MaRDI QIDQ1702849zbMATH OpenOpenAlexFDO

Authors Eva-Maria C. Hols, Stefan Kratsch

Publication date 1 March 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.02510, https://drops.dagstuhl.de/opus/volltexte/2016/5744/

zbMATH Keywords

parameterized complexitykernelizationsubset feedback vertex set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Abstract: The Subset Feedback Vertex Set problem generalizes the classical Feedback Vertex Set problem and asks, for a given undirected graph $G=(V,E)$, a set $SsubseteqV$, and an integer $k$, whether there exists a set $X$ of at most $k$ vertices such that no cycle in $G-X$ contains a vertex of $S$. It was independently shown by Cygan et al. (ICALP '11, SIDMA '13) and Kawarabayashi and Kobayashi (JCTB '12) that Subset Feedback Vertex Set is fixed-parameter tractable for parameter $k$. Cygan et al. asked whether the problem also admits a polynomial kernelization. We answer the question of Cygan et al. positively by giving a randomized polynomial kernelization for the equivalent version where $S$ is a set of edges. In a first step we show that Edge Subset Feedback Vertex Set has a randomized polynomial kernel parameterized by $|S|+k$ with $O(|S{|}^{2}k)$ vertices. For this we use the matroid-based tools of Kratsch and Wahlstr"om (FOCS '12) that for example were used to obtain a polynomial kernel for $s$-Multiway Cut. Next we present a preprocessing that reduces the given instance $(G,S,k)$ to an equivalent instance $(G^{\prime },S^{\prime },k^{\prime })$ where the size of $S^{\prime }$ is bounded by $O(k^4)$. These two results lead to a polynomial kernel for Subset Feedback Vertex Set with $O(k^9)$ vertices.

Recommendations

• A randomized polynomial kernel for subset feedback vertex set
• Towards a polynomial kernel for directed feedback vertex set
• Towards a polynomial kernel for directed feedback vertex set
• A randomized polynomial kernelization for vertex cover with a smaller parameter
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Linear-time kernelization for feedback vertex set
• An approximate kernel for connected feedback vertex set
• A quadratic kernel for feedback vertex set
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• A Cubic Kernel for Feedback Vertex Set

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3902670 (Why is no real title available?)
• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• A parameterized view on matroid optimization problems
• A short proof of Mader's \(\mathcal S\)-paths theorem
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Applications of Menger's graph theorem
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Faster deterministic \textsc{Feedback Vertex Set}
• Finding odd cycle transversals.
• Finding small separators in linear time via treewidth reduction
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Half-integrality, LP-branching and FPT algorithms
• Linear time parameterized algorithms for subset feedback vertex set
• Matroid matching and some applications
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• Representative sets and irrelevant vertices: new tools for kernelization
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

Cited in

(11)

• A parameterized algorithm for subset feedback vertex set in tournaments
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Subset feedback vertex set on graphs of bounded independent set size
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Computing subset transversals in \(H\)-free graphs
• A randomized polynomial kernel for subset feedback vertex set

This page was built for publication: A randomized polynomial kernel for subset feedback vertex set

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