Reformulating undirected to directed edges for MCF

Question

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?

Answer 1

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.