Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

5 Downloads (Pure)

Abstract

On the occasion of Hans Bodlaender’s 60th birthday, I give a personal account of our history and work together on the technique of cross-composition for kernelization lower bounds. I present several simple new proofs for polynomial kernelization lower bounds using cross-composition, interlaced with personal anecdotes about my time as Hans’ PhD student at Utrecht University. Concretely, I will prove that Vertex Cover, Feedback Vertex Set, and the H-Factor problem for every graph H that has a connected component of at least three vertices, do not admit kernels of (formula presented) bits when parameterized by the number of vertices n for any (formula presented), unless (formula presented). These lower bounds are obtained by elementary gadget constructions, in particular avoiding the use of the Packing Lemma by Dell and van Melkebeek.

Original languageEnglish
Title of host publicationTreewidth, Kernels, and Algorithms
Subtitle of host publicationEssays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday
EditorsFedor V. Fomin, Stefan Kratsch, Erik Jan van Leeuwen
PublisherSpringer
Pages89-111
Number of pages23
ISBN (Electronic)978-3-030-42071-0
ISBN (Print)978-3-030-42070-3
DOIs
Publication statusPublished - 21 Apr 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12160 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Cross-composition
  • Graph problems
  • Kernelization lower bounds

Fingerprint

Dive into the research topics of 'Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds'. Together they form a unique fingerprint.

Cite this