5
$\begingroup$

Usually in (integral) multi-commodity flow problems the graph is assumed to be directed. Instead, I am working with an undirected graph. Is it possible to transform it in a digraph?

Does such a transformation work in both the continuous and integral case?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Replace each undirected edge with two directed arcs in opposite directions. The original capacity constraint on each edge now applies to the sum of the arcs in both directions. If the costs are positive, every optimal solution will have flow in at most one of the two directions.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for your answer! So, if I got it right: consider an undirected edge with capacity 1. The corresponding digraph will have 2 edges, both with capacity 1. Whilst the corresponding constraint is still upper-bounded by 1, but now it considers the sum of the flows. Would be great if you could share some reference on the topic. $\endgroup$
    – Daniele Cuomo
    Oct 8, 2021 at 14:19
  • 1
    $\begingroup$ Network Flows (1993) discusses this transformation on page 39. $\endgroup$
    – RobPratt
    Oct 8, 2021 at 15:29
  • 1
    $\begingroup$ Yes, that is weaker but still valid. $\endgroup$
    – RobPratt
    Jun 27, 2022 at 18:34
  • $\begingroup$ I'm not convinced though. If we don't apply some penalty, different commodities may use both the arcs as it is not actually a cycling flow. $\endgroup$
    – Daniele Cuomo
    Jun 27, 2022 at 18:51
  • 1
    $\begingroup$ Oops, yes, sorry. I was thinking only of single commodity. $\endgroup$
    – RobPratt
    Jun 27, 2022 at 18:56

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.