moteur de recherche

Séminaire Algo - Eric Colin de Verdière
Séminaire Algo - Eric Colin de Verdière
6-Mar-2018 14:30
Age: 2 yrs

Eric Colin de Verdière

Approximating planar multicut

Salle de séminaire (4B05R) - Bâtiment Copernic

Let G be a graph and R a set of pairs of vertices, called pairs of terminals. A multicut is a set of edges of G whose removal disconnects each pair in R. Computing the minimum multicut is hard both from the approximation and the fixed-parameter tractability viewpoints (if the parameter is the number of terminals), even in planar edge-weighted graphs: It is APX-hard and W[1]-hard (and thus, of course, NP-hard). We give an algorithm that combines approximation and parameterized complexity: It computes a (1+ε)-approximation of the minimum multicut of a planar edge-weighted graph of size n in time f(t,ε).n log n, where t is the number of terminals and f is some (exponential) function. The result extends to graphs embeddable on a fixed surface. Most of the ingredients are taken from the field of computational topology of graphs on surfaces; I will survey these tools, and then explain how the algorithm combines them. This is joint work with Vincent Cohen-Addad and Arnaud de Mesmay.

<- Back to: Accueil