# 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