1
$\begingroup$

I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar question but it considers an undirected graph or to be precise I don't catch Andreas Björklund's last comment.

Can anyone help? Thank you in advance!

Improve this question
$\endgroup$
2
  • $\begingroup$ Schrijver's book on Combinatorial Optimization discusses several aspects of multiflows in Vol C. $\endgroup$
    – Chandra Chekuri
    Jan 2, 2016 at 4:55
  • $\begingroup$ Just to add another variant to the puzzle: what would be the minimal example for a fractional optimal solution to a 2-commodity network flow problem where the underlying directed network has no cycles? $\endgroup$
    – Tuomo Takkula
    Jan 6 at 17:44

1 Answer 1

Reset to default
2
$\begingroup$

You can use the example for an undirected edge with unit capacities, but replace each undirected edge from A to B with a set of directed edges that look like this.

enter image description here

Each edge has a unit capacity. And if you have $x$ units of flow from A to B and $y$ units of flow from B to A, you can route it as long as $x+y \leq 1$.

This is the gadget referred to in Andreas Björklund's comment.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.