AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

Most kernelization lower bounds rely, directly or indirectly, on the framework of Bodlaender et al. (ICALP 2008, JCSS 2009) and Fortnow & Santhanam (STOC 2008, JCSS 2011): To show a lower bound it is necessary to show a so-called composition algorithm which, essentially, encodes the OR of a given set of instances into one instance of the target problem. Such an algorithm takes (deterministic) polynomial-time and the output instance is YES if at least one of the input instances is YES. It has been observed that a kernelization lower bound for the target problem still follows if the composition is allowed to behave co-nondeterministically, i.e., similar to coNP-Turing machines for accepting coNP-complete languages (i.e. nondeterminism without false negatives).

The talk will recall the relevant notions (e.g. kernels, composition) and show the first example of using a co-nondeterministic composition algorithm. The target problem is the task of deciding whether a given graph G contains a clique or independent set of size at least k. This closely relates to the question of efficient preprocessing for computing Ramsey numbers.

Stefan Kratsch. "Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem." In SODA, pages 114--122, 2012.

Magnus Wahlström

--email hidden

passcode not visible

logged in users only