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!

  • 1
    $\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

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.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.