|
 
|
[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 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
BibTeX
| @inproceedings { | |||
| CRB04, | |||
| 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}", | |
| year | = | 2004, | |
| month | = | "January", | |
| pages | = | "23", | |
| } | |||
