Pages that link to "Item:Q2875151"
From MaRDI portal
The following pages link to Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (Q2875151):
Displaying 50 items.
- Strong partial clones and the time complexity of SAT problems (Q340559) (← links)
- Kernelization using structural parameters on sparse graph classes (Q340583) (← links)
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter (Q372970) (← links)
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments (Q385516) (← links)
- Preprocessing subgraph and minor problems: when does a small vertex cover help? (Q386050) (← links)
- Kernel bounds for path and cycle problems (Q392032) (← links)
- Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing (Q392033) (← links)
- Data reduction for graph coloring problems (Q393081) (← links)
- Kernelization for cycle transversal problems (Q423937) (← links)
- Lower bounds on kernelization (Q456702) (← links)
- Confronting intractability via parameters (Q465686) (← links)
- Exploiting a hypergraph model for finding Golomb rulers (Q471187) (← links)
- Towards optimal and expressive kernelization for \(d\)-hitting set (Q486984) (← links)
- Improved deterministic algorithms for weighted matching and packing problems (Q534565) (← links)
- On the small cycle transversal of planar graphs (Q551170) (← links)
- Kernel bounds for disjoint cycles and disjoint paths (Q638521) (← links)
- Kernels for feedback arc set in tournaments (Q657916) (← links)
- A generalization of Nemhauser and Trotter's local optimization theorem (Q657921) (← links)
- The minimum feasible tileset problem (Q666670) (← links)
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs (Q713308) (← links)
- Fréchet distance between a line and avatar point set (Q722543) (← links)
- An improved kernelization algorithm for \(r\)-set packing (Q765496) (← links)
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion (Q1759683) (← links)
- A kernel of order \(2k-c\log k\) for vertex cover (Q1944208) (← links)
- A completeness theory for polynomial (Turing) kernelization (Q2343083) (← links)
- On sparsification for computing treewidth (Q2343087) (← links)
- Constructing NP-intermediate problems by blowing holes with parameters of various properties (Q2345449) (← links)
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT (Q2408194) (← links)
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP (Q2429346) (← links)
- Towards optimal kernel for edge-disjoint triangle packing (Q2446590) (← links)
- A linear kernel for the complementary maximal strip recovery problem (Q2453554) (← links)
- Hitting forbidden minors: approximation and kernelization (Q2790404) (← links)
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders (Q2828222) (← links)
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs (Q2828227) (← links)
- Safe Approximation and Its Relation to Kernelization (Q2891346) (← links)
- Kernelization – Preprocessing with a Guarantee (Q2908537) (← links)
- What’s Next? Future Directions in Parameterized Complexity (Q2908548) (← links)
- Clique Cover and Graph Separation (Q2943572) (← links)
- An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion (Q3058695) (← links)
- Data Reduction for Graph Coloring Problems (Q3088272) (← links)
- New Limits to Classical and Quantum Instance Compression (Q3449566) (← links)
- Kernelization: New Upper and Lower Bound Techniques (Q3656848) (← links)
- Depth Reduction for Composites (Q4634033) (← links)
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds (Q5042452) (← links)
- (Q5075825) (← links)
- (Q5090371) (← links)
- (Q5111239) (← links)
- Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT (Q5363770) (← links)
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses (Q5501928) (← links)
- (Q5743378) (← links)
