The top of the minimum weight coverage in a tree with weighted vertices

Question

For a tree with non-oriented edges, where the weight of a vertex is its degree, find the vertex of the covering of minimum weight.

That's what I think:

Since the vertex coverage will need to contain enough vertices to cover all the edges, this means that regardless of the vertices in the cover, the sum of the weights of all the vertices will be the same (equal to the number of edges), so we don’t need any special algorithm to search for the answer, we only need to find the top cover of the minimum size (cover with minimum vertices).

Is this correct, or am I missing something obvious?

Answer 1

Is this correct, or am I missing something obvious?

Two vertices having the same edge; eg.,...

A -- B -- C Weights: B = 2; A = 1; C = 1 

{ A, C } and { B } are both weighted minimum vertex coverings by your definition.

Only { B } is the standard minimum vertex coverage.

EDIT: ... best example showing another reason:

 A -- B -- C -- D Weights: B = 2; C = 2; A = 1; D = 1 

{ A, C } , { B, D } , { B, C } are all standard minimal coverings of vertices.

Only { A, C } and { B, D } are weighted minimum vertex coverings by your definition. Intuitively, this happens because the vertex { B, C } vertex twice occupies the edge B -- C

---

The first counter example disproves that all weighted MVCs (according to your definition) are standard MVCs. The second counter example disproves that all standard MVCs are weighted MVCs.

After some thought ... you are right that a weighted MVC for a tree is any VC with a cost equal to the number of edges.

Finding a weighted MVC is actually quite simple. If you draw a tree and select all the vertices from every second level (it doesn't matter if you start from the first or second level), you get a valid weighted MVC according to your definition (since all edges are covered, not one edge is counted twice).

... in a more general sense, the collection of all weighted MVCs is the set of all neighborless VCs. For example, in a tree where none of the parents is a parent, a set of leaf nodes is also a valid weighted MVC.