1 We are looking for the shortest directed cycle C in the dual that
is oriented clockwise around t and counterclockwise around s (it
separates s and t in a topological sense).

a) The algorithm from class might fail, since the cycle C that we
are looking for might cross the shortest path P from a vertex on the
face s* to a vertex on the face t* several times. (find an example!)
The algorithm we showed clearly used the fact that in the undirected
case the cycle and the path cross once. (Try to clarify to yourself
where exactly!)

b) In this case C cannot cross P more than once, since P is shortest
in both directions. If C crosses P twice, we can simply use P as the
path between every two vertices in which they cross. Therefore we
can cut the graph along P and continue exactly as in the undirected
algorithm.

c) Yes.

Let P' be the "upper" copy of P (after we split it into two parallel
paths as in class, and let P'' be the "lower" copy. Every vertex v
in P has a copy v_1 in P' and a copy v_2 in P''. Let P_v be the
shortest path from v_1 to v_2. We  claim that P_v cannot intersect
P_u for two vertices u and v on P and this is what we need for the
divide and conquer to work.

Assume, for a contradiction, that this is not the case. Let x be the
first vertex of P_u in which P_u crosses P_v, let y be the last such
vertex. If x comes before y also in P_v, then the subpath from x to
y on one of the paths P_v or P_u is not shortest and we get a
contradiction. If y comes before x in P_v, then P_v cannot be a
simple path which is again a contradiction.

2) Fix u(e) = f(e) for every edge. Find a feasible circulation that
saturates an edge on every clockwise residual cycle using a shortest
path computation as shown in class. Subtract this circulation from
the flow. The resulting flow f' does not contain any residual
clockwise cycle and has the same value as f. Now "reverse" the flow
f' and repeat the procedure again. This will eliminate the
counterclockwise residual cycles and will not create any clockwise
cycles since we only decrease flow on edges.