How can I calculate the maximum possible sum of vertices in a weighted DAG excluding vertices directly connected by an edge? This is a vertex selection problem where each vertex has a weight.
In this first graph which is a tree rooted at A the answer would be 30. The vertices that are chosen to be part of the sum are B, E, F, H, and I. A and B cannot be both included since they are directly connected by an edge. The same applied to vertices C and D.
Edges:
A B
B C
B D
C E
C F
D H
D I
Weight of each vertex:
A 1
B 10
C 1
D 1
E 5
F 5
H 5
I 5
In this second graph the answer would be 40 and the vertices included in the sum would be A, B, E, and F. C is skipped over since either A and B are included or only C is included. D is skipped over since either E and F are included or only D is included.
Edges:
A C
B C
C D
D E
D F
Weight of each vertex:
A 10
B 10
C 1
D 2
E 10
F 10