Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

DOI10.1145/1806689.1806725zbMath1293.68132OpenAlexW2058258808MaRDI QIDQ2875151

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (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

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 (52)

Safe Approximation and Its Relation to Kernelization ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Kernelization – Preprocessing with a Guarantee ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Strong partial clones and the time complexity of SAT problems ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Clique Cover and Graph Separation ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Kernel bounds for path and cycle problems ⋮ Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing ⋮ Data reduction for graph coloring problems ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ A kernel of order \(2k-c\log k\) for vertex cover ⋮ Kernelization for cycle transversal problems ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Lower bounds on kernelization ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ Confronting intractability via parameters ⋮ Exploiting a hypergraph model for finding Golomb rulers ⋮ Kernels for feedback arc set in tournaments ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ A linear kernel for the complementary maximal strip recovery problem ⋮ Depth Reduction for Composites ⋮ Towards optimal and expressive kernelization for \(d\)-hitting set ⋮ The minimum feasible tileset problem ⋮ An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion ⋮ Improved deterministic algorithms for weighted matching and packing problems ⋮ Unnamed Item ⋮ On the small cycle transversal of planar graphs ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Unnamed Item ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion ⋮ Fréchet distance between a line and avatar point set ⋮ Unnamed Item ⋮ Data Reduction for Graph Coloring Problems ⋮ FPT is characterized by useful obstruction sets ⋮ Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs ⋮ An improved kernelization algorithm for \(r\)-set packing ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ On sparsification for computing treewidth ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties

This page was built for publication: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses