Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
From MaRDI portal
Publication:5501928
DOI10.1145/2629620zbMATH Open1321.68274OpenAlexW2034437384WikidataQ130962558 ScholiaQ130962558MaRDI QIDQ5501928FDOQ5501928
Authors: Holger Dell, Dieter Van Melkebeek 
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/
Recommendations
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Sparsification upper and lower bounds for graphs problems and not-all-equal SAT
parameterized complexitysatisfiabilitysparsificationvertex coverkernelizationfeedback vertex setvertex deletion problemsprobabilistically checkable proofshereditary graph propertiesarithmetic progression free sets
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) 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)
Cites Work
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- Computational Complexity
- Testing subgraphs in directed graphs
- On problems without polynomial kernels
- The node-deletion problem for hereditary properties is NP-complete
- Which problems have strongly exponential complexity?
- Improved bound for complexity of matrix multiplication
- Property testing and its connection to learning and approximation
- Incompressibility through Colors and IDs
- Title not available (Why is that?)
- Node-Deletion NP-Complete Problems
- Multiplying matrices faster than coppersmith-winograd
- Title not available (Why is that?)
- Efficient testing of large graphs
- A generalization of Nemhauser and Trotter's local optimization theorem
- Matrix multiplication via arithmetic progressions
- Intersection Theorems for Systems of Sets
- Computational Complexity
- Infeasibility of instance compression and succinct PCPs for NP
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Nondeterminism within $P^ * $
- Some consequences of non-uniform conditions on uniform classes
- On self-reducibility and weak P-selectivity
- Sharp thresholds of graph properties, and the $k$-sat problem
- Simple analysis of graph tests for linearity and PCP
- The threshold for random đ-SAT is 2^{đ}log2-đ(đ)
- Kernel(s) for problems with no kernel
- A note on Elkin's improvement of Behrend's construction
- Testing subgraphs in large graphs
- Title not available (Why is that?)
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Two edge modification problems without polynomial kernels
- Lower bounds for kernelizations and other preprocessing procedures
- The PCP theorem by gap amplification
- Random kâSAT: Two Moments Suffice to Cross a Sharp Threshold
- NONDETERMINISTICALLY SELECTIVE SETS
- Point line cover: the easy kernel is essentially tight
- Testing Triangle-Freeness in General Graphs
- Linear equations, arithmetic progressions and hypergraph property testing
Cited In (70)
- A multistage view on 2-satisfiability
- Dynamic kernels for hitting sets and set packing
- A Retrospective on (Meta) Kernelization
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- Optimal data reduction for graph coloring using low-degree polynomials
- Data Reduction for Maximum Matching on Real-World Graphs
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- On polynomial kernels for sparse integer linear programs
- Parameterized algorithms and kernels for 3-hitting set with parity constraints
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- On the kernelization complexity of string problems
- Optimal data reduction for graph coloring using low-degree polynomials
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- On the approximate compressibility of connected vertex cover
- Approximation and kernelization for chordal vertex deletion
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- A structural approach to kernels for ILPs: treewidth and total unimodularity
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Approximability of clique transversal in perfect graphs
- On kernelization for edge dominating set under structural parameters
- Sparsification lower bounds for list \(H\)-coloring
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Finding points in general position
- A \(13k\)-kernel for planar feedback vertex set via region decomposition
- Polynomial kernels and user reductions for the workflow satisfiability problem
- Kernelization of cycle packing with relaxed disjointness constraints
- What Is Known About Vertex Cover Kernelization?
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- Vertex cover structural parameterization revisited
- Exploiting \(c\)-closure in kernelization algorithms for graph problems
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- Sparsification lower bound for linear spanners in directed graphs
- Kernels for deletion to classes of acyclic digraphs
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- On fair covering and hitting problems
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Colored cut games
- Polynomial Kernel for Interval Vertex Deletion
- Best-case and worst-case sparsifiability of Boolean CSPs
- Fractals for kernelization lower bounds
- On some FPT problems without polynomial Turing compressions
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Faster FPT algorithm for 5-path vertex cover
- A randomized polynomial kernel for subset feedback vertex set
- Why is maximum clique often easy in practice?
- Kernels for packing and covering problems
- Best-case and worst-case sparsifiability of Boolean CSPs
- A polynomial kernel for bipartite permutation vertex deletion
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- An improved deterministic parameterized algorithm for cactus vertex deletion
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Kernelization for feedback vertex set via elimination distance to a forest
- Kernelization for feedback vertex set via elimination distance to a forest
- Search-space reduction via essential vertices
- Rank vertex cover as a natural problem for algebraic compression
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Parameterized complexity of streaming diameter and connectivity problems
- Minimum separator reconfiguration
- Quadratic vertex kernel for split vertex deletion
- On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
- Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Graph motif problems parameterized by dual
- On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
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 Q5501928)
