Lossy kernelization

DOI10.1145/3055399.3055456MaRDI QIDQ4977974zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.04111, http://wrap.warwick.ac.uk/113741/1/WRAP-Lossy-Kernelization-Ramanujan-2019.pdf

zbMATH Keywords

inapproximabilitykernelizationparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions combine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size $alpha$-approximate kernel. Loosely speaking, a polynomial size $alpha$-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance $(I,k)$ to a parameterized problem, and outputs another instance $(I^{\prime },k^{\prime })$ to the same problem, such that $|I^{\prime }|+k^{\prime }leq{k}^{O(1)}$. Additionally, for every $cgeq1$, a $c$-approximate solution $s^{\prime }$ to the pre-processed instance $(I^{\prime },k^{\prime })$ can be turned in polynomial time into a $(ccdotalpha)$-approximate solution $s$ to the original instance $(I,k)$. Our main technical contribution are $alpha$-approximate kernels of polynomial size for three problems, namely Connected Vertex Cover, Disjoint Cycle Packing and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless $NPsubseteqcoNP/poly$. Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size, and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an $alpha$-approximate kernel of polynomial size, for any $alphageq1$, unless $NPsubseteqcoNP/poly$. In order to prove this lower bound we need to combine in a non-trivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation

Recommendations

• Kernelization -- preprocessing with a guarantee
• On the approximate compressibility of connected vertex cover
• Lower bounds on kernelization
• Kernelization lower bounds through colors and IDs
• Lossy Kernels for Hitting Subgraphs

Cited in

(67)

• Time-approximation trade-offs for inapproximable problems
• Parameterized approximation via fidelity preserving transformations
• On the kernelization complexity of string problems
• On the parameterized complexity of contraction to generalization of trees
• On the approximate compressibility of connected vertex cover
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• Dynamic kernels for hitting sets and set packing
• Lossy kernelization of same-size clustering
• Partial vertex cover on graphs of bounded degeneracy
• To close is easier than to open: dual parameterization to \(k\)-median
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
• Revisiting connected vertex cover: FPT algorithms and lossy kernels
• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• Fixed-parameter algorithms for unsplittable flow cover
• Parameterized approximation via fidelity preserving transformations
• Safe approximation and its relation to kernelization
• Streaming kernelization
• Approximation algorithms inspired by kernelization methods
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Lossy kernels for connected dominating set on sparse graphs
• Fractals for kernelization lower bounds
• Lossy kernels for graph contraction problems
• Parameterized approximation algorithms for bidirected Steiner network problems
• Hans Bodlaender and the Theory of Kernelization Lower Bounds
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• An approximate kernel for connected feedback vertex set
• Lossy Kernels for Hitting Subgraphs
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Packing cycles faster than Erdős-Pósa
• Lossy kernels for connected dominating set on sparse graphs
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• Parameterized complexity of geometric covering problems having conflicts
• The parameterized complexity of cycle packing: indifference is not an issue
• On the lossy kernelization for connected treedepth deletion set
• On data reduction for dynamic vector bin packing
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• On approximate data reduction for the Rural Postman Problem: Theory and experiments
• Packing arc-disjoint cycles in oriented graphs
• Matroid-constrained vertex cover
• Lossy kernelization of same-size clustering
• On MAX-SAT with cardinality constraint
• Search-space reduction via essential vertices
• On MAX-SAT with cardinality constraint
• Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• On the parameterized complexity of connected cluster vertex deletion
• Baby PIH: Parameterized inapproximability of min CSP
• Satisfiability to coverage in presence of fairness, matroid, and global constraints
• Approximate Turing kernelization for problems parameterized by treewidth
• Kernelization of counting problems
• Approximate Turing kernelization and lower bounds for domination problems
• Budgeted matroid maximization: a parameterized viewpoint
• Approximately interpolating between uniformly and non-uniformly polynomial kernels
• Parameterized complexity of biclique contraction and balanced biclique contraction
• Scheduling kernels via configuration LP
• Approximate min-sum subset convolution
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• Tight approximation and kernelization bounds for vertex-disjoint shortest paths
• Tight approximation and kernelization bounds for vertex-disjoint shortest paths
• Polynomial-size enumeration kernelizations for long path enumeration
• On kernelization with access to NP-oracles
• On the parameterized complexity of maximum degree contraction problem
• Data reductions and combinatorial bounds for improved approximation algorithms

This page was built for publication: Lossy kernelization

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