3
$\begingroup$

As stated in this paper, there is a technique to reformulate a multi-commodity flow problem (MCF) with undirected edges to its equivalent version with directed edges.

By quoting them:

The reformulation involves adding two additional nodes and four additional arcs for each undirected arc.

However, just from this sentence I can't figure out the shape of the new graph. I also have problem to retrieve the original reference describing in detail such transformation.

Can someone explain how to do this? Also, considering that I am working with a minimisation MCF, is there a more efficient transformation?

$\endgroup$

1 Answer 1

3
$\begingroup$

From the reference provided in the paper (exercise on page 689 of the classic book Ahuja et al., 1993). The transformation is just to turn an undirected edge to a directed version. In this case also taking care of capacities and costs. There are many more useful transformations in this book.

For an undirected edge $i$ and $j$, we add two nodes $i'$ and $j'$ and 4 new edges (total of 5 directed edges) with two cycles. Only the edge between $i'$ and $j'$ has a capacity and cost associated with it. The rest have a capacity of $\infty$ and a cost of 0.

It is very clear with a picture:

Ahuja, R., Magnanti, T., & Orlin, J. (1993). Network flows: theory, algorithms, and applications. PrenticeHall, Upper Saddle River, NJ.

$\endgroup$
3
  • $\begingroup$ Thanks a lot! It would be great if you may share other maybe better solutions! $\endgroup$ Jun 29, 2022 at 12:27
  • $\begingroup$ Here's a link to the reference. yalma.fime.uanl.mx/~roger/work/teaching/… $\endgroup$ Jun 29, 2022 at 12:30
  • 1
    $\begingroup$ Nice that you found a link! This transformation is the appropriate one here. What I meant is that there are other useful ones, see Section 2.4 page 38, depending on what you want to achieve. $\endgroup$ Jun 30, 2022 at 9:03

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.