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

MaRDI QIDQ5743382zbMATH OpenFDO

Authors Stefan Kratsch

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1107.3704, https://dl.acm.org/citation.cfm?id=2095126

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)

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

Cites work

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

Cited in

(8)

• Co-Nondeterminism in Compositions
• 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

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)