2
$\begingroup$

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.

Thanks in advance!

$\endgroup$
  • $\begingroup$ “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. $\endgroup$ – Alex Ravsky Jan 5 '18 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.