Kernelization via Combinatorial Optimization - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Kernelization via Combinatorial Optimization

Stéphan Thomassé

Résumé

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,...
Fichier non déposé

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00394592 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More