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?

$\endgroup$

1 Answer 1

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.

$\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$ Commented Oct 8, 2021 at 14:19
  • 1
    $\begingroup$ Network Flows (1993) discusses this transformation on page 39. $\endgroup$
    – RobPratt
    Commented Oct 8, 2021 at 15:29
  • 1
    $\begingroup$ Yes, that is weaker but still valid. $\endgroup$
    – RobPratt
    Commented 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$ Commented Jun 27, 2022 at 18:51
  • 1
    $\begingroup$ Oops, yes, sorry. I was thinking only of single commodity. $\endgroup$
    – RobPratt
    Commented Jun 27, 2022 at 18:56

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.