I'm working on exercises from Combinatorial Optimization by Cook et al. and I'm a little stuck on how to proceed with the following problem:
Given digraph $G, u\in \textbf{R}^E$, and $r,s\in V$, find $R, r\in R\subset V\backslash\{s\}$ such that $u(\delta(R))-u(\delta(\bar{R}))$ is minimized. (Hint this is much easier than the minimum cut problem).
I'm a little thrown by the hint as proceeding like the minimum cut problem was my initial instinct. I'd be quite interested in a more efficient approach to this. Thanks for any insight.
Ok, I thought more about this question and I think I have a solution that I've given below, however it seems like it disregards the hint. Any thoughts?
Clearly we know the flow entering $R$ and the flow leaving $\bar{R}$ must be at most than the capacity of the edges in $\delta(R)$ and $\delta(\bar{R})$ respectively, i.e.
$x(\delta(R))\leq u(\delta(R))$ and $x(\delta(\bar{R}))\leq u(\delta(\bar{R}))$
So if we subtract these two inequalities we get:
$x(\delta(R))-x(\delta(\bar{R}))\leq u(\delta(R))-u(\delta(\bar{R}))$
Notice that if $r\in R$ and $s\in\bar{R}$ that the LHS is just the net flow into $s$, denoted $f_x(s)$. So if we maximize the flow into $s$, that is find the maximum flow for $G$ that value for $f_x(s)$ will be the minimum value for the RHS. Thus if we find the $R$ that corresponds to the minimum cut set for the maximum flow $f_x(s)$ that will minimize the RHS.
My issue is that this feels like it violates the hint?
As @RobPratt pointed out my earlier argument is flawed. What if instead we construct a new directed graph $G^+$ such that $V(G^+)=V(G)$ and $E(G^+)=E(G)\cup\{(v,u) : (u,v)\in E(G)~\text{and}~(v,u)\notin E(G)\}$ if for each edge $(u,v)\in E(G)$ with $(v,u)\notin E(G)$ and assign capacities to each $e\in E(G^+)$ by the following procedure: if $e$ is also an edge in $G$, then $u_{G^+}(e)=u_{G}(e)$. And if $e\in E(G^+)$ but not $e\notin E(G)$, then $u_{G^+}(e)=0$.
Now construct a second directed graph from $G^+$, denoted $G^*$, as follows $V(G^*)=V(G)$ and
$E(G^*)=\left\{\begin{array}{ll} (u,v) & \text{if}~ u_{G^+}(u,v)-u_{G^+}(v,u)\geq0\\(v,u) & \text{if}~ u_{G^+}(v,u)-u_{G^+}(u,v)\geq0\\\end{array}\right.\\$
And assign capacities to the edges in $E(G^*)$ as follows: if $u_{G^+}(u,v)-u_{G^+}(v,u)\geq0$, then $u_{G^*}(u,v)=u_{G^+}(u,v)-u_{G^+}(v,u)$. And if $u_{G^+}(u,v)-u_{G^+}(v,u)\leq0$, then $u_{G^*}(v,u)=u_{G^+}(v,u)-u_{G^+}(u,v)$.
Now, if we find the maximum flow across $G^*$, the corresponding minimum cut $\delta(R)$ gives us,by construction, $u_{G^*}(\delta(R))=u_{G^+}(\delta(R))-u_{G^+}(\delta(\bar{R}))=u_G(\delta(R))-u_G(\delta(\bar{R}))$.