Kernelization via Combinatorial Optimization - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2009

Kernelization via Combinatorial Optimization

Stéphan Thomassé


A graph parameter $\pi$ has {\it polynomial kernelization} if there exists an algorithm which has input a pair $(G,k)$ where $G$ is a graph of size $n$ and $k$ is an integer and outputs $(G',k')$ where $\pi(G)\leq k$ iff $\pi(G')\leq k'$, and $G'$ has size polynomial in $k$. Moreover the running time of the algorithm is $O(n^c)$ for some constant $c$. Roughly speaking, there exists an efficient preprocess of the instance $(G,k)$ which compress it into a instance of size polynomial in $k$. For example Vertex Cover in graphs can be kernelized to size $2k$, Feedback Vertex Set to size $4k2$, etc. The goal is to find a minimum size kernel. The design of kernelization algorithms heavily relies on combinatorial optimization tools applied to a substructure called {\it crown decomposition}. I will present some algorithms based on matchings, convex embeddings, hypergraphic matroids, $A$-disjoint paths,...
No file

Dates and versions

lirmm-00394592 , version 1 (12-06-2009)


  • HAL Id : lirmm-00394592 , version 1


Stéphan Thomassé. Kernelization via Combinatorial Optimization. EuroComb'09: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. ⟨lirmm-00394592⟩
132 View
0 Download


Gmail Facebook X LinkedIn More