[CRB04] Maximum edge disjoint paths and minimum unweighted multicut problems in grid graphs

Conférence Internationale avec comité de lecture : Contributed talk, Proceedings Graph Theory (GT'04), Paris, January 2004, pp.23,
Résumé: Let G=(V,E) be an undirected graph and let L be a list of K pairs (source si, sink ti) of terminal vertices of G (or nets). The maximum edge disjoint paths problem (MaxEDP) consists in maximizing the number of nets linked by edge disjoint paths. The related minimum multicut problem (MinUWMC) is to find a minimum set of edges whose removal separates si from ti for each i in an augmented graph (i.e., where each terminal vertex is linked to the graph by a unique edge). Both problems are NP-hard even in planar graphs. MaxEDP defined in rectilinear grids where any vertex can be a terminal is also NP-hard. However, A. Frank gives in [Frank82] necessary and sufficient conditions for the existence of K edge disjoint paths when the terminals are two-sided (i.e. they are all distinct and lie on the uppermost and lowermost lines of the grid): thus, solving MaxEDP is equivalent to removing the minimum number of nets in order to fulfill Frank's conditions. We prove that this can be done by solving a polynomial number of linear programs having totally unimodular constraints matrices. Then, we show that, in two-sided augmented grids, MinUWMC is polynomial time solvable via linear programming, by using a duality relationship with a continuous multiflow problem. As a by-product, the gap between the optimal values of MaxEDP and MinUWMC is proved to be at most one.

Collaboration: LIPN


@inproceedings {
title="{Maximum edge disjoint paths and minimum unweighted multicut problems in grid graphs}",
author=" M.-C. Costa and F. Roupin and C. Bentz ",
booktitle="{Contributed talk, Proceedings Graph Theory (GT'04), Paris}",