Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem

zbMATH Open1423.68216arXiv1107.3704MaRDI QIDQ5743382FDOQ5743382

Authors: Stefan Kratsch 

Publication date: 10 May 2019

Full work available at URL: https://arxiv.org/abs/1107.3704

Recommendations

• Co-Nondeterminism in Compositions
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• Kernelization Lower Bounds by Cross-Composition
• scientific article; zbMATH DE number 7053262

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Generalized Ramsey theory (05C55)

Cites Work

• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• On problems without polynomial kernels
• Title not available (Why is that?)
• Incompressibility through Colors and IDs
• (Meta) Kernelization
• Bidimensionality and kernels
• Infeasibility of instance compression and succinct PCPs for NP
• Ramsey's theorem - a new lower bound
• A new upper bound for diagonal Ramsey numbers
• Some consequences of non-uniform conditions on uniform classes
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Title not available (Why is that?)
• Cross-composition: a new technique for kernelization lower bounds
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Parameterized complexity of finding subgraphs with hereditary properties.
• Preprocessing of min ones problems: a dichotomy
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

Cited In (8)

• A fixed-depth size-hierarchy theorem for AC ⁰ [⊕] via the coin problem
• On the combination of the Bernays-Schönfinkel-Ramsey fragment with simple linear integer arithmetic
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• New limits to classical and quantum instance compression
• A completeness theory for polynomial (Turing) kernelization
• Co-Nondeterminism in Compositions

This page was built for publication: Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743382)