Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
From MaRDI portal
Publication:5501928
arithmetic progression free setsfeedback vertex sethereditary graph propertieskernelizationparameterized complexityprobabilistically checkable proofssatisfiabilitysparsificationvertex coververtex deletion problems
Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)
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
- 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
- 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?)
- 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
- Node-Deletion NP-Complete Problems
- Nondeterminism within $P^ * $
- NONDETERMINISTICALLY SELECTIVE SETS
- On problems without polynomial kernels
- On self-reducibility and weak P-selectivity
- 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 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 subgraphs in directed graphs
- Testing subgraphs in large graphs
- Testing Triangle-Freeness in General Graphs
- The node-deletion problem for hereditary properties is NP-complete
- The PCP theorem by gap amplification
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- Two edge modification problems without polynomial kernels
- Which problems have strongly exponential complexity?
Cited in
(91)- Kernels for deletion to classes of acyclic digraphs
- A randomized polynomial kernel for subset feedback vertex set
- On the kernelization complexity of string problems
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- On the approximate compressibility of connected vertex cover
- Sparsification lower bound for linear spanners in directed graphs
- On some FPT problems without polynomial Turing compressions
- 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
- An improved deterministic parameterized algorithm for cactus vertex deletion
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Optimal-size problem kernels for d-Hitting Set in linear time and space
- Kernels for packing and covering problems
- Optimal data reduction for graph coloring using low-degree polynomials
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- On fair covering and hitting problems
- A multistage view on 2-satisfiability
- On polynomial kernels for sparse integer linear programs
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Parameterized algorithms and kernels for 3-hitting set with parity constraints
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- 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
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Vertex cover structural parameterization revisited
- A structural approach to kernels for ILPs: treewidth and total unimodularity
- Approximation and kernelization for chordal vertex deletion
- Finding points in general position
- Fractals for kernelization lower bounds
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Best-case and worst-case sparsifiability of Boolean CSPs
- 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
- On kernelization for edge dominating set under structural parameters
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- Faster FPT algorithm for 5-path vertex cover
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- Data Reduction for Maximum Matching on Real-World Graphs
- Optimal data reduction for graph coloring using low-degree polynomials
- Graph motif problems parameterized by dual
- Why is maximum clique often easy in practice?
- 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
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
- On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
- Quadratic vertex kernel for split vertex deletion
- Kernelization for feedback vertex set via elimination distance to a forest
- Sparsification lower bounds for list \(H\)-coloring
- 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?
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Search-space reduction via essential vertices
- Parameterized complexity of streaming diameter and connectivity problems
- Minimum separator reconfiguration
- Colored cut games
- Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel
- Kernelization for orthogonality dimension
- No polynomial kernels for knapsack
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Minimum separator reconfiguration
- Difference determines the degree: structural kernelizations of component order connectivity
- Parameterized lower bounds for the weighted vertex cover problem in trees
- Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
- Parameterized complexity of streaming diameter and connectivity problems
- Search-space reduction via essential vertices
- Preprocessing complexity for some graph problems parameterized by structural parameters
- Polynomial kernels for edge modification problems towards block and strictly chordal graphs
- Optimal polynomial-time compression for Boolean Max CSP
- Sparsification lower bounds for list H-coloring
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- Approximability of clique transversal in perfect graphs
- Parameterized quantum query algorithms for graph problems
- Component order connectivity admits no polynomial kernel parameterized by the distance to subdivided comb graphs
- Kernelization of compressing two-dimensional routing tables with order
- Boundaried kernelization
- On kernelization with access to NP-oracles
- Polynomial kernels with reachability for weighted d-matroid intersection
- Best-case and worst-case sparsifiability of Boolean CSPs
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)
