Pages that link to "Item:Q619903"
From MaRDI portal
The following pages link to Infeasibility of instance compression and succinct PCPs for NP (Q619903):
Displaying 50 items.
- On polynomial kernels for sparse integer linear programs (Q269481) (← links)
- Parameterized complexity dichotomy for \textsc{Steiner Multicut} (Q295637) (← links)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- AND-compression of NP-complete problems: streamlined proof and minor observations (Q309801) (← links)
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments (Q329279) (← links)
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter (Q372970) (← links)
- Preprocessing subgraph and minor problems: when does a small vertex cover help? (Q386050) (← links)
- Incremental list coloring of graphs, parameterized by conservation (Q391091) (← links)
- Kernel bounds for path and cycle problems (Q392032) (← links)
- Parameterized complexity of vertex deletion into perfect graph classes (Q392038) (← links)
- Data reduction for graph coloring problems (Q393081) (← links)
- On the parameterized complexity of the repetition free longest common subsequence problem (Q413298) (← links)
- Confronting intractability via parameters (Q465686) (← links)
- The kernelization complexity of connected domination in graphs with (no) small cycles (Q476436) (← links)
- On cutwidth parameterized by vertex cover (Q476444) (← links)
- Restricted and swap common superstring: a multivariate algorithmic perspective (Q494787) (← links)
- On the parameterized complexity of finding separators with non-hereditary properties (Q494799) (← links)
- Fixed-parameter algorithms for DAG partitioning (Q507587) (← links)
- On making a distinguished vertex of minimum degree by vertex deletion (Q528861) (← links)
- Kernel bounds for disjoint cycles and disjoint paths (Q638521) (← links)
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs (Q713308) (← links)
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization (Q722549) (← links)
- Turing kernelization for finding long paths and cycles in restricted graph classes (Q730497) (← links)
- Dual parameterization of weighted coloring (Q786042) (← links)
- Meta-kernelization with structural parameters (Q896025) (← links)
- Two edge modification problems without polynomial kernels (Q1662097) (← links)
- Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} (Q1679222) (← links)
- On the kernelization complexity of string problems (Q1749539) (← links)
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs (Q1755775) (← links)
- Parameterized computational complexity of finding small-diameter subgraphs (Q1758028) (← links)
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems (Q1949740) (← links)
- Parameterized two-player Nash equilibrium (Q1949741) (← links)
- On the parameterized complexity of contraction to generalization of trees (Q2000005) (← links)
- On the approximate compressibility of connected vertex cover (Q2006945) (← links)
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization (Q2032346) (← links)
- On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems (Q2049975) (← links)
- On some FPT problems without polynomial Turing compressions (Q2072079) (← links)
- A polynomial kernel for bipartite permutation vertex deletion (Q2093571) (← links)
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds (Q2093577) (← links)
- Polynomial kernels for hitting forbidden minors under structural parameterizations (Q2202024) (← links)
- Kernels for packing and covering problems (Q2272393) (← links)
- Two edge-disjoint paths with length constraints (Q2330117) (← links)
- Kernelization lower bound for permutation pattern matching (Q2339595) (← links)
- Backdoors to tractable answer set programming (Q2341833) (← links)
- A completeness theory for polynomial (Turing) kernelization (Q2343083) (← links)
- Incompressibility of \(H\)-free edge modification problems (Q2343091) (← links)
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT (Q2408194) (← links)
- Tractability, hardness, and kernelization lower bound for and/or graph solution (Q2410230) (← links)
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP (Q2429346) (← links)
- On the hardness of losing width (Q2441542) (← links)
