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,...
Type de document :
Communication dans un congrès
EuroComb'09: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. 2009, Electronic Notes in Discrete Mathematics. 〈http://eurocomb09.labri.fr/pmwiki/pmwiki.php〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00394592
Contributeur : Stephan Thomasse <>
Soumis le : vendredi 12 juin 2009 - 10:15:33
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00394592, version 1

Collections

Citation

Stéphan Thomassé. Kernelization via Combinatorial Optimization. EuroComb'09: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. 2009, Electronic Notes in Discrete Mathematics. 〈http://eurocomb09.labri.fr/pmwiki/pmwiki.php〉. 〈lirmm-00394592〉

Partager

Métriques

Consultations de la notice

116