# Digraph to flow network

Let $G=(V,E)$ be a digraph and the function $w:V \to R$. It exists at least one vertice $v'\in V$ with $w(v')>0$ and at least one vertice $v''\in V$ with $w(v'')<0$. We consider a subset $U \subseteq V$ a closed set if there doesn't exists an edge $(u,v) \in E$ such that $u \in U$ and $v \in V-U$. For each subset $A \subseteq V$, the sum of the weights of the vertices $v_1,v_2...v_k \in A$ is $w(A)=w(v_1)+w(v_2)+...+w(v_k)$ where $|A|=k$.

I need to prove that the problem of finding a subset $A \subseteq V$ of maximum $w(A)$ can be solved in polynomial time with a maximum flow algorithm for a convenable chosen network.

I think that if we write the digraph $G$ as a flow network $R=(G,s,t,w)$, $w$ being the capacity function and if I find an algorithm for finding the maximum flow, the problem is almost solved, but I am not sure how to choose the source $s$ and sink $t$, because there should be a closed set.

• “I think that if we write the digraph $G$ as a flow network $R=(G,s,t,w)$, $w$ being the capacity function” I recall that in a flow network a (non-negative) capacity function is defined for edges, whereas $f$ is a real-valued function defined for vertices. Also I guess that you look for a closed subset $A$, otherwise we don’t need a flow to find it, because any set containing all vertices of positive weight and contained in the set of vertices of non-negative weight is the required. – Alex Ravsky Jan 5 '18 at 12:14

Even though this question is quite old, I'll give an answer. As noted in the comments, I assume that what you're looking for is a closed set with maximum weight. I don't know whether there's a standard name for this problem, but I do recall seeing the following construction before.

Let $$K$$ be the sum of the positive node weights:

$$K = \sum_{v: w(v) > 0} w(v).$$

Then for any subset $$A \subseteq V$$, we have $$w(A) = \sum_{v \in A : w(v) > 0} w(v) - \sum_{v \in A: w(v) < 0} |w(v)| = K - \sum_{v \notin A: w(v) > 0} w(v) - \sum_{v \in A: w(v) < 0} |w(v)|.$$

Thus our goal is to find a closed set $$A$$ which minimizes $$\sum_{v \notin A: w(v) > 0} w(v) + \sum_{v \in A: w(v) < 0} |w(v)|$$

In order to do this, let us add a source $$s$$ and a sink $$t$$ to $$G$$. For each node $$v$$ with $$w(v) > 0$$, we add an edge $$sv$$ with capacity $$w(v)$$. Similarly, when $$w(v) < 0$$, we add an edge $$vt$$ with capacity $$|w(v)|$$. Finally, we define the capacity of each original edge to be infinite.

Now a cut $$s \in A \not\ni t$$ has finite capacity precisely if $$A-s$$ is a closed set in $$G$$. Moreover, in this case the capacity will be exactly the value that we want to minimze. Thus we only need to find a minimum cut in this network, which can be done efficiently using a flow algorithm.