# [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,

**motcle: **

**Résumé: **
Let G=(V,E) be an undirected graph and let L be a
list of K pairs (source s_{i}, sink t_{i}) 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 s_{i} from t_{i} 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.