I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.
We now show how to transform a minimum cut problem on an s-t planar network (s means source and t means sink) into a shortest path problem. In the given s-t planar network, we first draw a new arc joining the nodes s and t so that the arc stays within the unbounded face of the network [see Figure 8.8(b)]; this construction creates a new face of the network, which we call the additional face, but maintains the network's planarity. We then construct the dual of this network; we designate the node corresponding to the additional face as the dual source s * and the node corresponding to the unbounded face as the dual sink t*. We set the cost of an arc in the dual network equal to the capacity of the corresponding arc in the primal network. The dual network contains the arc (s*, t*) which we delete from the network. Figure 8.8(b) shows this construction: the dashed lines are the arcs in the dual network.
- How shall I understand the one before the last sentence "The dual network contains the arc (s*, t*) which we delete from the network"? Why I don't see an arc between s* and t* in the dual network?
- Does the dash arc (s, t) constructed at the beginning belong to the dual network? I guess not, because s and t are not vertices in the dual graph, isn't it?
Thanks and regards!