Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem
Stefan Kratsch · 2012
Until recently, techniques for obtaining lower bounds for kernelization were one of the most sought after tools in the field of parameterized complexity. Now, after a strong influx of techniques, we are in the fortunate situation of having tools available that are even stronger than what has been required in their applications so far. Based on a result of Fortnow and Santhanam (STOC 2008, JCSS 2011), Bodlaender et al. (ICALP 2008, JCSS 2009) showed that, unless NP ⊆ coNP/poly, the existence of a deterministic polynomial-time composition algorithm, i.e., an algorithm which outputs an instance of bounded parameter value which is yes if and only if one of t input instances is yes, rules out the existence of polynomial kernels for a problem. Dell and van Melkebeek (STOC 2010) continued this line