All reports by Author Xi Wu:

__
TR11-072
| 1st May 2011
__

Danny Hermelin, Xi Wu#### Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization

Revisions: 1

Danny Hermelin, Xi Wu

We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let $d \ge 2$ be some constant and let $L_1, L_2 \subseteq \{0,1\}^* \times \N$ be two parameterized problems where the unparameterized version of $L_1$ is \NP-hard. ... more >>>