Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)
From MaRDI portal
Publication:5741082
DOI10.1137/15M1038876zbMath1341.05239arXiv1309.7891OpenAlexW2489053438MaRDI QIDQ5741082
Saket Saurabh, Archontia C. Giannopoulou, Ondřej Suchý, Daniel Lokshtanov
Publication date: 22 July 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1309.7891
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- On feedback vertex set: new measure and new structures
- Improved algorithms for feedback vertex set problems
- A cubic kernel for feedback vertex set and loop cutset
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- An FPT algorithm for Tree Deletion Set
- Kernelization – Preprocessing with a Guarantee
- A 4 k 2 kernel for feedback vertex set
- Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
- Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Preprocessing of Min Ones Problems: A Dichotomy
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- Polynomial algorithms in linear programming
- A generalization of the fast LUP matrix decomposition algorithm and applications
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Compression via Matroids
- Representative Sets and Irrelevant Vertices
- Multiplying matrices faster than coppersmith-winograd
