Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
DOI10.1145/1806689.1806725zbMATH Open1293.68132OpenAlexW2058258808WikidataQ130968380 ScholiaQ130968380MaRDI QIDQ2875151FDOQ2875151
Dieter Van Melkebeek, Holger Dell
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/
Recommendations
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Sparsification upper and lower bounds for graphs problems and not-all-equal SAT
- Optimal sparsification for some binary CSPs using low-degree polynomials
parameterized complexitysatisfiabilitysparsificationvertex coverkernelizationfeedback vertex setvertex deletion problemsprobabilistically checkable proofshereditary graph propertiesarithmetic progression free sets
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (53)
- Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
- On kernels for \(d\)-path vertex cover
- New Limits to Classical and Quantum Instance Compression
- Kernel bounds for path and cycle problems
- Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
- What’s Next? Future Directions in Parameterized Complexity
- On sparsification for computing treewidth
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Data Reduction for Graph Coloring Problems
- Title not available (Why is that?)
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- A generalization of Nemhauser and Trotter's local optimization theorem
- A kernel of order \(2k-c\log k\) for vertex cover
- Title not available (Why is that?)
- Kernelization for cycle transversal problems
- Depth Reduction for Composites
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- On the small cycle transversal of planar graphs
- Kernelization – Preprocessing with a Guarantee
- Title not available (Why is that?)
- Kernelization using structural parameters on sparse graph classes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Kernel bounds for disjoint cycles and disjoint paths
- Improved deterministic algorithms for weighted matching and packing problems
- Fréchet distance between a line and avatar point set
- Kernelization: New Upper and Lower Bound Techniques
- Towards optimal kernel for edge-disjoint triangle packing
- Lower bounds on kernelization
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- Data reduction for graph coloring problems
- Title not available (Why is that?)
- An improved kernelization algorithm for \(r\)-set packing
- Confronting intractability via parameters
- Exploiting a hypergraph model for finding Golomb rulers
- Kernels for feedback arc set in tournaments
- An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
- A linear kernel for the complementary maximal strip recovery problem
- Strong partial clones and the time complexity of SAT problems
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Towards optimal and expressive kernelization for \(d\)-hitting set
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- A completeness theory for polynomial (Turing) kernelization
- Safe Approximation and Its Relation to Kernelization
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Title not available (Why is that?)
- Clique Cover and Graph Separation
- The minimum feasible tileset problem
- Hitting forbidden minors: approximation and kernelization
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
This page was built for publication: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875151)
