Skip to Main content Skip to Navigation
Conference papers

Kernelization via Combinatorial Optimization

Stéphan Thomassé 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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,...
Document type :
Conference papers
Complete list of metadatas
Contributor : Stephan Thomasse <>
Submitted on : Friday, June 12, 2009 - 10:15:33 AM
Last modification on : Tuesday, January 22, 2019 - 7:10:05 PM


  • 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⟩



Record views