|
|
Discrete Mathematics and Optimization Seminar
|
Monday, Mar. 8th, 2010
|
Integer Multicommodity Flows in Planar Graphs
Guyslain Naves
McGill
|
A commodity in a capacitated graph G is a pair of vertices (source, sink) and a demand value associated to this pair.
Given a set of commodities H, a multicommodity flow is a set of flows, one for each commodity, such that the sum of the
flows on each edge e is at most the capacity of e. We want to decide if there is a multicommodity flow such that the flow
for each commodity is equal to its demand. When there is only one commodity, this is the decision version of the classic
flow problem. If we force the flows to be integral, it defines the integer multicommodity flow problem. When the capacities
are uniformly equal to one, this is the edge-disjoint paths problem. I will survey the main results in the field of integer
multicommodity flows, and then introduce two new results when G is a planar graph:
- the problem is NP-complete with only two commodities (in undirected and directed acyclic cases),
- the uncapacitated problem is polynomial when G is a planar acyclic digraph, G+H is Eulerian, and the number of commodities is fixed.
|
|
|
|