Multicut is FPT

Nicolas Bousquet 1 Jean Daligault 1 Stéphan Thomassé 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Let G=(V,E) be a graph on n vertices and R be a set of pairs of vertices in V called requests. A multicut is a subset F of E such that every request xy of R is cut by F, i.e. every xy-path of G intersects F. We show that there exists an O(f(k)nc) algorithm which decides if there exists a multicut of size at most k. In other words, the Multicut problem parameterized by the solution size k is Fixed-Parameter Tractable.
Type de document :
Communication dans un congrès
STOC'11: Symposium on Theory of Computing, United States. pp.459-468, 2011
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00741933
Contributeur : Nicolas Bousquet <>
Soumis le : lundi 15 octobre 2012 - 15:17:45
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00741933, version 1

Collections

Citation

Nicolas Bousquet, Jean Daligault, Stéphan Thomassé. Multicut is FPT. STOC'11: Symposium on Theory of Computing, United States. pp.459-468, 2011. 〈lirmm-00741933〉

Partager

Métriques

Consultations de la notice

78