Minimum top tree cover
There is an existing question about trees where the weight of a vertex is its degree, but I'm interested in the case where vertices can have arbitrary weights.
This is not homework, but it is one of the questions in the Algorithm Design Guide I am currently reading; the answer set gives the solution as
- Run DFS, update Score [v] [include] at each step, where v is the vertex and include is either true or false;
- If v is a sheet, set the value Score [v] [false] = 0, Score [v] [true] = w vwhere w v is the weight of the vertices v.
- During DFS, when navigating from the last child of node v, update parameter [v] [include]: Score [v] [false] = Sum for c in children (v) of measure [c] [true] and Score [v] [ true] = w v + Sum for c in children (v) min (Score [c] [true]; Score [c] [false])
- Retrieve actual coverage using backtracking metric.
However, I can't seem to translate this into something that works. (In response to a comment: what I've tried so far is drawing some small graphs with weights and running the algorithm on paper, up to the fourth step, where the "extract actual cover" part is not transparent.)
In response to Ali's answer: So, suppose I have this graph, with vertices given A
, etc., and weights in parens after:
A(9)---B(3)---C(2)
\ \
E(1) D(4)
The correct answer is clearly {B,E}
.
After going through this algorithm, we set the following values:
-
score[D][false] = 0
;score[D][true] = 4
-
score[C][false] = 0
;score[C][true] = 2
-
score[B][false] = 6
;score[B][true] = 3
-
score[E][false] = 0
;score[E][true] = 1
-
score[A][false] = 4
;score[A][true] = 12
So my question is basically what now? Doing a simple thing and repeating with a vector score
and detecting what is cheap locally doesn't work; you end up including B
. The solution based on parenting and alternation also does not work: consider the case when the weight E
is equal 1000
; now the answer is correct {A,B}
and they are adjacent. Maybe this shouldn't be misleading, but to be honest, I'm confused.
source to share
It didn't really mean anything confusing and it's just Dynamic Programming , it looks like you almost understand the whole algorithm. If I want to make it clearer, I must say:
- first prepare DFS on the graph and find the leaves.
- for each leaf assignment value, as the algorithm says.
- now start at leaves and assign values to each parent of this formula.
- start assigning values to the parent node that already have values until you reach the root of your graph.
Exactly so, by tracing back in your algorithm, it means that you are assigning a value to each node, that its child already has values. As I said above, this decision problem is called dynamic programming.
Edit just to explain your changes to the question. Since you have the following graph and the answer is clearly B, E, but you, although this algorithm just gives you B and you are wrong, this algorithm gives you B and E.
A(9)---B(3)---C(2)
\ \
E(1) D(4)
score[D][false] = 0; score[D][true] = 4
score[C][false] = 0; score[C][true] = 2
score[B][false] = 6 this means we use C and D; score[B][true] = 3 this means we use B
score[E][false] = 0; score[E][true] = 1
score[A][false] = 4 This means we use B and E; score[A][true] = 12 this means we use B and A.
and you choose 4, so you have to use B and E. if it was just B, your answer would be 3., but as you find it correctly, your answer is 4 = 3 + 1 = B + E.
Also when E = 1000
A(9)---B(3)---C(2)
\ \
E(1000) D(4)
it is 100% correct that the answer is B and A, because it is wrong to use E just because you do not want to select neighboring nodes. with this algorithm you will find the answer A and B, and by just checking you can find it too. let's say this covers:
C D A = 15
C D E = 1006
A B = 12
Although the first two answers have no neighbors, they are larger than the last answer with neighboring nodes. so it is better to use A and B for coverage.
source to share
Rollback is what was done in the previous steps. Step 4 doesn't really matter, it can also say "figure out what to do with the Score".
The tree cover vertex allows you to include alternating and adjacent vertices. It does not allow you to exclude two adjacent vertices as it must contain all edges.
The answer is given in a recursive way of calculating the score. The cost of not including the top is the cost of including its descendants. However, the cost of including a vertex is less expensive, including including its children or not including them, since both are allowed.
As your solution suggests, this can be done with DFS in order of order, in a single pass. The trick is to include a vertex if the count indicates it should be included, and include its children if it should be excluded, otherwise we would exclude two adjacent vertices.
Here's some pseudocode:
find_cover_vertex_of_minimum_weight(v)
find_cover_vertex_of_minimum_weight(left children of v)
find_cover_vertex_of_minimum_weight(right children of v)
Score[v][false] = Sum for c in children(v) of Score[c][true]
Score[v][true] = v weight + Sum for c in children(v) of min(Score[c][true]; Score[c][false])
if Score[v][true] < Score[v][false] then
add v to cover vertex tree
else
for c in children(v)
add c to cover vertex tree
source to share