Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

DOI10.1145/2629620zbMath1321.68274OpenAlexW2034437384MaRDI QIDQ5501928

Publication date: 14 August 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2504/

zbMATH Keywords

satisfiability probabilistically checkable proofs vertex cover feedback vertex set parameterized complexity sparsification kernelization vertex deletion problems hereditary graph properties arithmetic progression free sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Formal languages and automata (68Q45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On polynomial kernels for sparse integer linear programs, Hans Bodlaender and the Theory of Kernelization Lower Bounds, Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds, A Retrospective on (Meta) Kernelization, Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems, An improved deterministic parameterized algorithm for cactus vertex deletion, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Kernelization of Cycle Packing with Relaxed Disjointness Constraints, A $13k$-kernel for planar feedback vertex set via region decomposition, A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity, Polynomial kernels and user reductions for the workflow satisfiability problem, AND-compression of NP-complete problems: streamlined proof and minor observations, A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter, Vertex Cover Structural Parameterization Revisited, Known Algorithms for Edge Clique Cover are Probably Optimal, On a generalization of Nemhauser and Trotter's local optimization theorem, A Turing kernelization dichotomy for structural parameterizations of $\mathcal{F} $-minor-free deletion, Sparsification upper and lower bounds for graph problems and not-all-equal SAT, Kernels for deletion to classes of acyclic digraphs, Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints, Preprocessing to reduce the search space: antler structures for feedback vertex set, On fair covering and hitting problems, Approximation and Kernelization for Chordal Vertex Deletion, Elimination Distances, Blocking Sets, and Kernels for Vertex Cover, Kernelization for feedback vertex set via elimination distance to a forest, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, Data Reduction for Maximum Matching on Real-World Graphs, Polynomial Kernel for Interval Vertex Deletion, Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU, Kernelization for feedback vertex set via elimination distance to a forest, What Is Known About Vertex Cover Kernelization?, Polynomial kernels for hitting forbidden minors under structural parameterizations, A multistage view on 2-satisfiability, A randomized polynomial kernel for subset feedback vertex set, Finding Points in General Position, Optimal-size problem kernels for $d$-Hitting Set in linear time and space, Unnamed Item, Graph Motif Problems Parameterized by Dual, Fractals for Kernelization Lower Bounds, Unnamed Item, Why Is Maximum Clique Often Easy in Practice?, The minimum feasible tileset problem, Exploiting c-Closure in Kernelization Algorithms for Graph Problems, Quadratic vertex kernel for split vertex deletion, On the kernelization complexity of string problems, A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, On the approximate compressibility of connected vertex cover, Kernels for packing and covering problems, Optimal data reduction for graph coloring using low-degree polynomials, Unnamed Item, Unnamed Item, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Approximability of clique transversal in perfect graphs, Turing kernelization for finding long paths and cycles in restricted graph classes, On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT, On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT, Lower bounds for the happy coloring problems, Subset feedback vertex set in chordal and split graphs, Sparsification lower bound for linear spanners in directed graphs, A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs, Rank Vertex Cover as a Natural Problem for Algebraic Compression, On some FPT problems without polynomial Turing compressions, Polynomial kernels for vertex cover parameterized by small degree modulators, Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials, Best-case and worst-case sparsifiability of Boolean CSPs, Colored cut games, A polynomial kernel for bipartite permutation vertex deletion, Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds, Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size, Dynamic kernels for hitting sets and set packing

Cites Work