Pages that link to "Item:Q5501928"
From MaRDI portal
The following pages link to Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses (Q5501928):
Displayed 50 items.
- On polynomial kernels for sparse integer linear programs (Q269481) (← links)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- A \(13k\)-kernel for planar feedback vertex set via region decomposition (Q306250) (← links)
- Polynomial kernels and user reductions for the workflow satisfiability problem (Q309799) (← links)
- AND-compression of NP-complete problems: streamlined proof and minor observations (Q309801) (← links)
- On a generalization of Nemhauser and Trotter's local optimization theorem (Q340561) (← links)
- The minimum feasible tileset problem (Q666670) (← links)
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization (Q722549) (← links)
- Approximability of clique transversal in perfect graphs (Q724231) (← links)
- Turing kernelization for finding long paths and cycles in restricted graph classes (Q730497) (← links)
- Best-case and worst-case sparsifiability of Boolean CSPs (Q786033) (← links)
- Kernels for deletion to classes of acyclic digraphs (Q1678165) (← links)
- A randomized polynomial kernel for subset feedback vertex set (Q1702849) (← links)
- On the kernelization complexity of string problems (Q1749539) (← links)
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs (Q1755775) (← links)
- On the approximate compressibility of connected vertex cover (Q2006945) (← links)
- Sparsification lower bound for linear spanners in directed graphs (Q2055974) (← links)
- On some FPT problems without polynomial Turing compressions (Q2072079) (← links)
- Colored cut games (Q2087453) (← links)
- A polynomial kernel for bipartite permutation vertex deletion (Q2093571) (← links)
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds (Q2093577) (← links)
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size (Q2093579) (← links)
- Dynamic kernels for hitting sets and set packing (Q2093581) (← links)
- An improved deterministic parameterized algorithm for cactus vertex deletion (Q2135634) (← links)
- Polynomial kernels for hitting forbidden minors under structural parameterizations (Q2202024) (← links)
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space (Q2203595) (← links)
- Kernels for packing and covering problems (Q2272393) (← links)
- Optimal data reduction for graph coloring using low-degree polynomials (Q2272594) (← links)
- Polynomial kernels for vertex cover parameterized by small degree modulators (Q2322700) (← links)
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT (Q2408194) (← links)
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion (Q2662677) (← links)
- Preprocessing to reduce the search space: antler structures for feedback vertex set (Q2672419) (← links)
- On fair covering and hitting problems (Q2672421) (← links)
- A multistage view on 2-satisfiability (Q2692727) (← links)
- Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints (Q2947024) (← links)
- Kernelization of Cycle Packing with Relaxed Disjointness Constraints (Q3174716) (← links)
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter (Q3177162) (← links)
- Vertex Cover Structural Parameterization Revisited (Q3181056) (← links)
- A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity (Q3452840) (← links)
- Known Algorithms for Edge Clique Cover are Probably Optimal (Q3464061) (← links)
- Approximation and Kernelization for Chordal Vertex Deletion (Q4586151) (← links)
- Finding Points in General Position (Q4605338) (← links)
- Fractals for Kernelization Lower Bounds (Q4609787) (← links)
- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel (Q4637327) (← links)
- (Q5009477) (← links)
- Hans Bodlaender and the Theory of Kernelization Lower Bounds (Q5042447) (← links)
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds (Q5042452) (← links)
- A Retrospective on (Meta) Kernelization (Q5042460) (← links)
- Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel (Q5048303) (← links)
- Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems (Q5048305) (← links)