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!

  • $\begingroup$ Schrijver's book on Combinatorial Optimization discusses several aspects of multiflows in Vol C. $\endgroup$ Commented 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$ Commented Jan 6, 2023 at 17:44

1 Answer 1


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.


Your Answer

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

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