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