1
$\begingroup$

Suppose you got a directed acyclic graph of positvely and negatively weighed nodes $T\hspace{-0.02 in}$.
Now I have to find the the subset ​ $M\subseteq T$ ​ such that the sum of
the weights of the nodes in $M$ is maximised, but if ​ $v \in M$ ​ then all
children of $v$ as well as their children, and so on have to be in $M$ too.

For now my algorithm is as follows:

  1. calculate the depth of each node (how many nodes you have to
    traverse at maximum to reach one which doesn't have any children)
  2. for all nodes $v$ of depth $n$ do the following:
    1. add up the weight of $v$ and the weights of all children and grandchildren,
      ... (you get the idea) of $v$
    2. if the last step added up to a positive value then mark $v$ and
      all children of $v$ as in $M$ and don't consider them any further
    3. if the last step marked any node with the current depth then repeat
      for this depth (since the sums changed) otherwise increment n.

This works fine for some DAGs: ​ ​ ​ (Note: ​ the edges are directed downwards) enter image description here

As expected all nodes except the top node are in $M$

But for othes the algorithm falls short:

enter image description here

The algorithm outputs that ​ $M = \emptyset$ , ​ whereas ​ $M=T$ ​ should be the case.

Is there an algorithm which solves a similar problem?
If no, how can I correct my solution? ​ Any help is highly appreciated.

PS: ​ ​ ​ I apollogize for the use of MS Paint. ​ Sorry for that.

$\endgroup$
  • 1
    $\begingroup$ 35. Bundeswettbewerb Informatik, Runde 2, Aufgabe 1 shame on you. $\endgroup$ – W.Pohl Jan 29 '17 at 11:13
  • $\begingroup$ Translation: This is more or less directly a task in the current national CS competition in Germany, due in April 2017. $\endgroup$ – Raphael Jan 29 '17 at 12:03
  • $\begingroup$ If so, do you want me to request deletion by a moderator ? $\endgroup$ – Cooki3Tube Jan 29 '17 at 12:38
  • $\begingroup$ Two cases: 1) You are participating in the contest. You already got an answer, so don't delete. Reference the answer in your solution. 2) You are not participating in the contest. Why would you delete? You've done nothing wrong. -- That said, you can always delete your own posts. (Except if you have an accepted answer, which is undoable.) $\endgroup$ – Raphael Jan 29 '17 at 13:15
  • 1
    $\begingroup$ @W.Pohl Since the problem seems to be rather standard, calling shame on people without knowing they participate in the contest is rather shameful. Also, if the creators of the contest use a textbook problem without thinking about the power of Google, well... I find it hard to punish students for using all resources at hand, provided they give proper credit. (Of course, if too little own work remains, top grades are no longer possible.) $\endgroup$ – Raphael Jan 29 '17 at 13:20
3
$\begingroup$

I forget the name but it's a classic minimum-cut problem. You can always consider min-cut approach when you want to choose an optimal subset.

(Edit: It's called "project selection problem".)

Think about cutting nodes into two partitions $S$, $T$ and $S$ is what we choose. Ideally we want $S$ to contain all the positive nodes and avoid any negative node. However, it's not always possible. If there exists an edge $(u,v)$, $u\in S\to v\in S$. In the min-cut model, it means we can't cut this edge, so we set $capacity(u,v)=\inf$. Next consider what we should pay if we can't assign them ideally.

Create a source $s$ and a target $t$. For each node $u$, if $w_u$ is positive, add an edge $(s,u)$ and set $capacity(s,u)=w_u$. It means we lose $w_u$ if $u\notin S$. If $w_u$ is negative, add $(u,t)$ and set $capacity(u,t)=-w_u$. It means we lose $-w_u$ if $u \in S$.

The answer is $\sum_{w_u>0} w_u-min cut(s,t)$, and $M$ is the source partition.

$\endgroup$
  • $\begingroup$ Thanks a lot. Do you mean the Stoer-Wagner-Algorithm? $\endgroup$ – Cooki3Tube Dec 28 '16 at 9:17
  • $\begingroup$ No, I mean the problem. I found that it's called "project selection problem", which you can even find in "max-flow min-cut theorem" wikipedia page. $\endgroup$ – aaaaajack Dec 28 '16 at 10:51
  • $\begingroup$ FYI: This problem is part of an ongoing contest (see question). You may want to hold back your answer until after the deadline. $\endgroup$ – Raphael Jan 29 '17 at 12:04
  • $\begingroup$ @Raphael Is it necessary? This problem is so classic that it can be found everywhere, for example jeffe.cs.illinois.edu/teaching/algorithms/notes/… Anyway I don't know how this contest works, so I'll hold it back if you think it's necessary. How to hide the answer? Just click "delete"? $\endgroup$ – aaaaajack Jan 29 '17 at 12:39
  • $\begingroup$ I see. There's probably no need to act in this case; it's nobody's fault if the creators of the contest were a little lazy. (They really should account for Google these days.) That said, deleting and later undeleting would be the way to do it, yes. $\endgroup$ – Raphael Jan 29 '17 at 13:17

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.