**Friday, 16:15 - 16:40 h, Room: H 3013**

**Christophe Weibel**

When the cut condition is enough: Characterization of multiflow problems by forbidden minors

**Coauthors: Amit Chakrabarti, Lisa Fleischer**

**Abstract:**

For a supply graph *G=(V,E)* and a demand graph *H=(V,F)*,

an assignment of capacities to the

edges of *G* and demands to the edges of *H* is said to satisfy the

*cut condition* if for any cut in the graph, the total demand

crossing the cut is no more than the total capacity crossing it.

The pair *(G,H)* is called *cut-sufficient* if for any

assignment of capacities and demands that satisfy the cut condition,

the demands defined on *H* can be routed within the

network with capacities defined on *G*.

A pair *(G, H)* is said to contain another pair *(G', H')* as a minor

if it is possible to obtain *(G', H')* from *(G, H)* by contracting

edges of *G* and deleting edges of *G* and *H*. We propose

to characterize cut-sufficient pairs by forbidden minors.

In particular, we prove a previous conjecture giving the minimal set of forbidden minors

for instances with a series-parallel supply graph, and propose a

conjecture extending our results to planar supply graphs.

Talk 3 of the invited session Fri.3.H 3013

**"Flows, cuts, and sparsifiers"** [...]

Cluster 2

**"Combinatorial optimization"** [...]