A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals

TY - GEN

T1 - A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals

AU - Cohen-addad, Vincent

AU - De Verdière, Éric Colin

AU - De Mesmay, Arnaud

N1 - Conference code: 29

PY - 2018

Y1 - 2018

N2 - For an undirected edge-weighted graph G and a set R of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from G disconnects each pair in R. We provide an algorithm computing a (1+ϵ)approximation of the minimum multicut of a graph G in time (g + t)(O(g+t)3) (1/ϵ)O(g+t) n log n, where g is the genus of G and t is the number of terminals. This is tight in several aspects, as the minimum multicut problem is both APX-hard and W[1]-hard (parameterized by the number of terminals), even on planar graphs (equivalently, when g = 0). Our result, in the field of fixed-parameter approximation algorithms, mostly relies on concepts borrowed from computational topology of graphs on surfaces. In particular, we use and extend various recent techniques concerning homotopy, homology, and covering spaces (even in the planar case). We also exploit classical ideas stemming from approximation schemes for planar graphs and low-dimensional geometric inputs. A key insight towards our result is a novel characterization of a minimum multicut as the union of some Steiner trees in the universal cover of the surface in which G is embedded.

AB - For an undirected edge-weighted graph G and a set R of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from G disconnects each pair in R. We provide an algorithm computing a (1+ϵ)approximation of the minimum multicut of a graph G in time (g + t)(O(g+t)3) (1/ϵ)O(g+t) n log n, where g is the genus of G and t is the number of terminals. This is tight in several aspects, as the minimum multicut problem is both APX-hard and W[1]-hard (parameterized by the number of terminals), even on planar graphs (equivalently, when g = 0). Our result, in the field of fixed-parameter approximation algorithms, mostly relies on concepts borrowed from computational topology of graphs on surfaces. In particular, we use and extend various recent techniques concerning homotopy, homology, and covering spaces (even in the planar case). We also exploit classical ideas stemming from approximation schemes for planar graphs and low-dimensional geometric inputs. A key insight towards our result is a novel characterization of a minimum multicut as the union of some Steiner trees in the universal cover of the surface in which G is embedded.

U2 - 10.1137/1.9781611975031.95

DO - 10.1137/1.9781611975031.95

M3 - Article in proceedings

SP - 1439

EP - 1458

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Czumaj, Artur

PB - Society for Industrial and Applied Mathematics

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 7 January 2018 through 10 January 2018

ER -