crosscomposition_journal.bbl
\begin{thebibliography}{10}

\bibitem{Abu-KhzamFLS07}
F.~N. Abu-Khzam, M.~R. Fellows, M.~A. Langston, and W.~H. Suters.
\newblock Crown structures for vertex cover kernelization.
\newblock {\em Theory Comput. Syst.}, 41(3):411--430, 2007.
\newblock \href {http://dx.doi.org/10.1007/s00224-007-1328-0}
  {\path{doi:10.1007/s00224-007-1328-0}}.

\bibitem{AlonGKSY11}
N.~Alon, G.~Gutin, E.~J. Kim, S.~Szeider, and A.~Yeo.
\newblock Solving {MAX}-$r$-{SAT} above a tight lower bound.
\newblock {\em Algorithmica}, 61(3):638--655, 2011.
\newblock \href {http://dx.doi.org/10.1007/s00453-010-9428-7}
  {\path{doi:10.1007/s00453-010-9428-7}}.

\bibitem{Bodlaender09}
H.~L. Bodlaender.
\newblock Kernelization: New upper and lower bound techniques.
\newblock In {\em Proc. 4th {IWPEC}}, pages 17--37, 2009.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-11269-0_2}
  {\path{doi:10.1007/978-3-642-11269-0_2}}.

\bibitem{BodlaenderDFH09}
H.~L. Bodlaender, R.~G. Downey, M.~R. Fellows, and D.~Hermelin.
\newblock On problems without polynomial kernels.
\newblock {\em J. Comput. Syst. Sci.}, 75(8):423--434, 2009.
\newblock \href {http://dx.doi.org/10.1016/j.jcss.2009.04.001}
  {\path{doi:10.1016/j.jcss.2009.04.001}}.

\bibitem{BodlaenderFLPST09}
H.~L. Bodlaender, F.~V. Fomin, D.~Lokshtanov, E.~Penninkx, S.~Saurabh, and
  D.~M. Thilikos.
\newblock ({M}eta) {K}ernelization.
\newblock In {\em Proc. 50th FOCS}, pages 629--638, 2009.
\newblock \href {http://dx.doi.org/10.1109/FOCS.2009.46}
  {\path{doi:10.1109/FOCS.2009.46}}.

\bibitem{BodlaenderJK11}
H.~L. Bodlaender, B.~M.~P. Jansen, and S.~Kratsch.
\newblock Cross-composition: A new technique for kernelization lower bounds.
\newblock In {\em Proc. 28th STACS}, pages 165--176, 2011.
\newblock \href {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.165}
  {\path{doi:10.4230/LIPIcs.STACS.2011.165}}.

\bibitem{BodlaenderJK12}
H.~L. Bodlaender, B.~M.~P. Jansen, and S.~Kratsch.
\newblock Kernel bounds for path and cycle problems.
\newblock In {\em Proc. 6th IPEC}, pages 145--158, 2011.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-28050-4_12}
  {\path{doi:10.1007/978-3-642-28050-4_12}}.

\bibitem{BodlaenderJK11b}
H.~L. Bodlaender, B.~M.~P. Jansen, and S.~Kratsch.
\newblock Preprocessing for treewidth: A combinatorial analysis through
  kernelization.
\newblock In {\em Proc. 38th {ICALP}}, pages 437--448, 2011.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-22006-7_37}
  {\path{doi:10.1007/978-3-642-22006-7_37}}.

\bibitem{BodlaenderK08}
H.~L. Bodlaender and A.~M. C.~A. Koster.
\newblock Combinatorial optimization on graphs of bounded treewidth.
\newblock {\em Comput. J.}, 51(3):255--269, 2008.
\newblock \href {http://dx.doi.org/10.1093/comjnl/bxm037}
  {\path{doi:10.1093/comjnl/bxm037}}.

\bibitem{BodlaenderTY11}
H.~L. Bodlaender, S.~Thomass{\'e}, and A.~Yeo.
\newblock Kernel bounds for disjoint cycles and disjoint paths.
\newblock {\em Theor. Comput. Sci.}, 412(35):4570--4578, 2011.
\newblock \href {http://dx.doi.org/10.1016/j.tcs.2011.04.039}
  {\path{doi:10.1016/j.tcs.2011.04.039}}.

\bibitem{CaiCHO05}
J.~Cai, V.~T. Chakaravarthy, L.~A. Hemaspaandra, and M.~Ogihara.
\newblock Competing provers yield improved {K}arp-{L}ipton collapse results.
\newblock {\em Inf. Comput.}, 198(1):1--23, 2005.
\newblock \href {http://dx.doi.org/10.1016/j.ic.2005.01.002}
  {\path{doi:10.1016/j.ic.2005.01.002}}.

\bibitem{ChenKJ01}
J.~Chen, I.~A. Kanj, and W.~Jia.
\newblock Vertex cover: Further observations and further improvements.
\newblock {\em J. Algorithms}, 41(2):280--301, 2001.
\newblock \href {http://dx.doi.org/10.1006/jagm.2001.1186}
  {\path{doi:10.1006/jagm.2001.1186}}.

\bibitem{ChorFJ04}
B.~Chor, M.~Fellows, and D.~W. Juedes.
\newblock Linear kernels in linear time, or how to save $k$ colors in
  {$O$}$(n^2)$ steps.
\newblock In {\em Proc. 30th WG}, pages 257--269, 2004.
\newblock \href {http://dx.doi.org/10.1007/978-3-540-30559-0_22}
  {\path{doi:10.1007/978-3-540-30559-0_22}}.

\bibitem{CrowstonFGJRTY11}
R.~Crowston, M.~R. Fellows, G.~Gutin, M.~Jones, F.~A. Rosamond,
  S.~Thomass{\'e}, and A.~Yeo.
\newblock Simultaneously satisfying linear equations over $f_2$: Maxlin2 and
  max-r-lin2 parameterized above average.
\newblock In {\em Proc. FSTTCS 2011}, pages 229--240, 2011.
\newblock \href {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.229}
  {\path{doi:10.4230/LIPIcs.FSTTCS.2011.229}}.

\bibitem{CyganFL11}
M.~Cygan, F.~V. Fomin, and E.~J. van Leeuwen.
\newblock Parameterized complexity of firefighting revisited.
\newblock In {\em Proc. 6th IPEC}, pages 13--26, 2011.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-28050-4_2}
  {\path{doi:10.1007/978-3-642-28050-4_2}}.

\bibitem{CyganKPPW11}
M.~Cygan, S.~Kratsch, M.~Pilipczuk, M.~Pilipczuk, and M.~Wahlstr{\"o}m.
\newblock Clique cover and graph separation: New incompressibility results.
\newblock In {\em Proc. 39th ICALP}, 2012.
\newblock To appear.

\bibitem{CyganLPPS11a}
M.~Cygan, D.~Lokshtanov, M.~Pilipczuk, M.~Pilipczuk, and S.~Saurabh.
\newblock On cutwidth parameterized by vertex cover.
\newblock In {\em Proc. 6th IPEC}, pages 246--258, 2011.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-28050-4_20}
  {\path{doi:10.1007/978-3-642-28050-4_20}}.

\bibitem{CyganLPPS11}
M.~Cygan, D.~Lokshtanov, M.~Pilipczuk, M.~Pilipczuk, and S.~Saurabh.
\newblock On the hardness of losing width.
\newblock In {\em Proc. 6th IPEC}, pages 159--168, 2011.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-28050-4_13}
  {\path{doi:10.1007/978-3-642-28050-4_13}}.

\bibitem{CyganMPPS11}
M.~Cygan, D.~Marx, M.~Pilipczuk, M.~Pilipczuk, and I.~Schlotter.
\newblock Parameterized complexity of {E}ulerian deletion problems.
\newblock In {\em Proc. 37th WG}, pages 131--142, 2011.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-25870-1_13}
  {\path{doi:10.1007/978-3-642-25870-1_13}}.

\bibitem{DellM12}
H.~Dell and D.~Marx.
\newblock Kernelization of packing problems.
\newblock In {\em Proc. 23rd SODA}, pages 68--81, 2012.

\bibitem{DellM10}
H.~Dell and D.~van Melkebeek.
\newblock Satisfiability allows no nontrivial sparsification unless the
  polynomial-time hierarchy collapses.
\newblock In {\em Proc. 42nd STOC}, pages 251--260, 2010.
\newblock \href {http://dx.doi.org/10.1145/1806689.1806725}
  {\path{doi:10.1145/1806689.1806725}}.

\bibitem{DomLS09}
M.~Dom, D.~Lokshtanov, and S.~Saurabh.
\newblock Incompressibility through colors and {ID}s.
\newblock In {\em Proc. 36th ICALP}, pages 378--389, 2009.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-02927-1_32}
  {\path{doi:10.1007/978-3-642-02927-1_32}}.

\bibitem{DowneyF99}
R.~Downey and M.~R. Fellows.
\newblock {\em Parameterized Complexity}.
\newblock Monographs in Computer Science. Springer, New York, 1999.

\bibitem{Drucker12_techreport}
A.~Drucker.
\newblock New limits to classical and quantum instance compression.
\newblock Technical report, MIT, 2012.
\newblock Available from:
  \url{http://people.csail.mit.edu/andyd/compression.pdf}.

\bibitem{FellowsJR12}
M.~R. Fellows, B.~M.~P. Jansen, and F.~Rosamond.
\newblock Towards fully multivariate algorithmics: Parameter ecology and the
  deconstruction of computational complexity.
\newblock {\em European J. Combin.}, 2012.
\newblock (To appear).

\bibitem{FernauFLRSV09}
H.~Fernau, F.~V. Fomin, D.~Lokshtanov, D.~Raible, S.~Saurabh, and Y.~Villanger.
\newblock Kernel(s) for problems with no kernel: On out-trees with many leaves.
\newblock In {\em Proc. 26th {STACS}}, Dagstuhl, Germany, 2009.
\newblock Available from:
  \url{http://drops.dagstuhl.de/opus/volltexte/2009/1843}.

\bibitem{FlumG06}
J.~Flum and M.~Grohe.
\newblock {\em Parameterized Complexity Theory}.
\newblock Springer-Verlag New York, Inc., 2006.

\bibitem{FominLST10}
F.~Fomin, D.~Lokshtanov, S.~Saurabh, and D.~M. Thilikos.
\newblock Bidimensionality and kernels.
\newblock In {\em Proc. 21st SODA}, pages 503--510, 2010.

\bibitem{FortnowS11}
L.~Fortnow and R.~Santhanam.
\newblock Infeasibility of instance compression and succinct {PCP}s for {NP}.
\newblock {\em J. Comput. Syst. Sci.}, 77(1):91--106, 2011.
\newblock \href {http://dx.doi.org/10.1016/j.jcss.2010.06.007}
  {\path{doi:10.1016/j.jcss.2010.06.007}}.

\bibitem{GareyJ79}
M.~R. Garey and D.~S. Johnson.
\newblock {\em Computers and Intractability, A Guide to the Theory of
  {NP}-Complete\-ness}.
\newblock W.H. Freeman and Company, New York, 1979.

\bibitem{GuillemotHPP12}
S.~Guillemot, F.~Havet, C.~Paul, and A.~Perez.
\newblock On the (non-)existence of polynomial kernels for ${P}_{\ell}$-free
  edge modification problems.
\newblock {\em Algorithmica}, pages 1--27, 2012.
\newblock Online First.
\newblock \href {http://dx.doi.org/http://dx.doi.org/10.1007/s00453-012-9619-5}
  {\path{doi:http://dx.doi.org/10.1007/s00453-012-9619-5}}.

\bibitem{GuoN07a}
J.~Guo and R.~Niedermeier.
\newblock Invitation to data reduction and problem kernelization.
\newblock {\em SIGACT News}, 38(1):31--45, 2007.
\newblock \href {http://dx.doi.org/10.1145/1233481.1233493}
  {\path{doi:10.1145/1233481.1233493}}.

\bibitem{HarnikN10}
D.~Harnik and M.~Naor.
\newblock On the compressibility of $\mathcal{NP}$ instances and cryptographic
  applications.
\newblock {\em SIAM J. Comput.}, 39(5):1667--1713, 2010.
\newblock \href {http://dx.doi.org/10.1137/060668092}
  {\path{doi:10.1137/060668092}}.

\bibitem{HermelinKSWW11}
D.~Hermelin, S.~Kratsch, K.~Soltys, M.~Wahlstr\"om, and X.~Wu.
\newblock Hierarchies of inefficient kernelizability.
\newblock {\em CoRR}, abs/1110.0976, 2011.

\bibitem{HermelinW12a}
D.~Hermelin and X.~Wu.
\newblock Weak compositions and their applications to polynomial lower bounds
  for kernelization.
\newblock In {\em Proc. 23rd SODA}, pages 104--113, 2012.

\bibitem{JansenB12}
B.~M.~P. Jansen and H.~L. Bodlaender.
\newblock Vertex cover kernelization revisited.
\newblock {\em Theory of Computing Systems}, pages 1--37, 2012.
\newblock Online First.
\newblock \href {http://dx.doi.org/10.1007/s00224-012-9393-4}
  {\path{doi:10.1007/s00224-012-9393-4}}.

\bibitem{JansenK11b}
B.~M.~P. Jansen and S.~Kratsch.
\newblock Data reduction for graph coloring problems.
\newblock In {\em Proc. 18th FCT}, pages 90--101, 2011.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-22953-4_8}
  {\path{doi:10.1007/978-3-642-22953-4_8}}.

\bibitem{JansenK12}
B.~M.~P. Jansen and S.~Kratsch.
\newblock On polynomial kernels for structural parameterizations of odd cycle
  transversal.
\newblock In {\em Proc. 6th IPEC}, pages 132--144, 2011.
\newblock \href {http://dx.doi.org/10.1007/978-3-642-28050-4_11}
  {\path{doi:10.1007/978-3-642-28050-4_11}}.

\bibitem{Kratsch12}
S.~Kratsch.
\newblock Co-nondeterminism in compositions: a kernelization lower bound for a
  {R}amsey-type problem.
\newblock In {\em Proc. 23rd SODA}, pages 114--122, 2012.

\bibitem{KratschPRR12}
S.~Kratsch, M.~Pilipczuk, A.~Rai, and V.~Raman.
\newblock Kernel lower bounds using co-nondeterminism: Finding induced
  hereditary subgraphs.
\newblock In {\em Proc. 13th SWAT}. Springer, 2012.
\newblock To appear.

\bibitem{KratschW11a}
S.~Kratsch and M.~Wahlstr{\"o}m.
\newblock Representative sets and irrelevant vertices: New tools for
  kernelization.
\newblock {\em CoRR}, abs/1111.2195, 2011.

\bibitem{KratschW12}
S.~Kratsch and M.~Wahlstr{\"o}m.
\newblock Compression via matroids: a randomized polynomial kernel for odd
  cycle transversal.
\newblock In {\em Proc. 23rd SODA}, pages 94--103, 2012.

\bibitem{LokshtanovMS11a}
D.~Lokshtanov, D.~Marx, and S.~Saurabh.
\newblock Lower bounds based on the exponential time hypothesis.
\newblock {\em Bulletin of the EATCS}, 105:41--72, 2011.

\bibitem{MisraRS11}
N.~Misra, V.~Raman, and S.~Saurabh.
\newblock Lower bounds on kernelization.
\newblock {\em Discrete Optimization}, 8(1):110--128, 2011.
\newblock \href {http://dx.doi.org/10.1016/j.disopt.2010.10.001}
  {\path{doi:10.1016/j.disopt.2010.10.001}}.

\bibitem{Niedermeier06}
R.~Niedermeier.
\newblock {\em Invitation to Fixed-Parameter Algorithms}.
\newblock Oxford University Press, 2006.

\bibitem{Niedermeier10}
R.~Niedermeier.
\newblock Reflections on multivariate algorithmics and problem
  parameterization.
\newblock In {\em Proc. 27th STACS}, pages 17--32, 2010.
\newblock \href {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2495}
  {\path{doi:10.4230/LIPIcs.STACS.2010.2495}}.

\bibitem{ReedSV04}
B.~A. Reed, K.~Smith, and A.~Vetta.
\newblock Finding odd cycle transversals.
\newblock {\em Oper. Res. Lett.}, 32(4):299--301, 2004.
\newblock \href {http://dx.doi.org/10.1016/j.orl.2003.10.009}
  {\path{doi:10.1016/j.orl.2003.10.009}}.

\bibitem{Thomasse10}
S.~Thomass{\'e}.
\newblock A quadratic kernel for feedback vertex set.
\newblock {\em ACM Transactions on Algorithms}, 6(2), 2010.
\newblock \href {http://dx.doi.org/10.1145/1721837.1721848}
  {\path{doi:10.1145/1721837.1721848}}.

\bibitem{Yap83}
C.-K. Yap.
\newblock Some consequences of non-uniform conditions on uniform classes.
\newblock {\em Theor. Comput. Sci.}, 26:287--300, 1983.
\newblock \href {http://dx.doi.org/10.1016/0304-3975(83)90020-8}
  {\path{doi:10.1016/0304-3975(83)90020-8}}.

\end{thebibliography}
