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!
Best Answer
The network in (b) shows the situation after deletion of the $(s^*, t^*)$ arc. The $(s^*, t^*)$ arc needs to be removed in order to have a one-to-one correspondence between $s$-$t$ cuts in the primal and paths from $s^*$ to $t^*$ in the dual.
No, it doesn't belong to the dual network. Dual arcs must be between faces in the primal network. I'm not sure why they left it in figure (b), as it is a bit confusing to have it there.