Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

What is an algorithm to calculate the maximum "score" possible in a directed graph, with the constraint that edges with the same value can only be traversed once? For example, in the graph below, given that you can use each of a, b, and c once, the best path is to use a and b to get to 7, and c to get to 2, for a score of 9.

enter image description here

Edit: This is another way to formulate the problem:
Given: A set $S$ of $(key:value)$ pairs, where the key itself is a non-empty set of variables, eg - $S = \{(\{a\}:2), (\{c\}:2), (\{a, b\}:7), (\{b\}:3), (\{c\}:1)\}$. Keys may not be unique, so the word 'key' may be misleading.
Required: A subset $S' \subseteq S$ such that the total sum of values of each member of $S'$ is maximized.
Constraint: Each variable present in any of the keys of $S$ (eg. $a, b$ etc.) belongs to the list (key) of exactly one member of $S'$
For example, $S' = \{(\{c\}:2), (\{a, b\}:7)\}$ has a total value of 9, and each of $a, b, c$ occur in exactly one list.

share|improve this question
1  
can you explain your problem in more detail ? how is the directed graph constructed ? and what do you want to obtain ? Tell us more about what is this problem applicable to. –  AJed Jan 26 '13 at 2:26
    
Essentially, I have several workers that return proposals, that may be mutually exclusive. They each pertain to a single value. I.e.: "With a or c, I will provide 2." "With a and b I will provide 7." "With b, I will provide 3." "With c, I will provide 1." Except that, of course, in my real domain it will be more complex. –  syrion Jan 26 '13 at 2:36
    
This is similar to the problem solved e.g. by Dijkstra's algorithm (just that looks for minimal cost, not maximal benefit). –  vonbrand Jan 26 '13 at 3:47
    
From your example, all you have to do is to compares the values of the leaves $O(|V|)$. Find the leaf $l$ with highest score, and find the path from $s$ to $l$ .. $O(h)$ , where $h$ is height of the tree (btw: is it a tree ? or it can be any general DAG ?). Am I getting right ? –  AJed Jan 26 '13 at 3:53
    
I am looking for a total score--probably unclear, but you start at S repeatedly until your keys are exhausted. –  syrion Jan 26 '13 at 3:59
show 7 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.