CODEWITHSUNDEEP
algorithmgraph
efficiencyIsBliss
efficiencyIsBliss

Reputation: 3093

Vertex cover of minimum weight in a tree with weighted vertices

Given a tree with undirected edges, where the the weight of a vertex is its degree, find the vertex cover of minimum weight.

Here's what I think:

Since the vertex cover will need to include enough vertices to cover all edges, that 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). Therefore, we don't need any special algorithm to find the answer, we only need to find the minimum size vertex cover (cover with minimum vertices).

Is this correct, or am I missing something obvious?

Upvotes: 4

Views: 3133

Answers (1)

badroit
badroit

Reputation: 1336

Is this correct, or am I missing something obvious?

Two vertices having the same edge; e.g.,...

A -- B -- C

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

{ A, C } and { B } are both weighted minimal vertex covers by your definition.

Only { B } is a standard minimal vertex cover.

EDIT:... a better example showing a different reason:

A -- B -- C -- D

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

{ A, C }, { B, D }, { B, C } are all standard minimal vertex covers.

Only { A, C } and { B, D } are weighted minimal vertex covers by your definition. Intuitively, this is because the { B, C } vertex cover counts the B -- C edge twice.

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

After some thought... you are correct in that the 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 the tree out, and pick all the vertexes from every second level (doesn't matter if you start from the first or second level), you end up with a valid weighted MVC by your definition (since all edges are covered, no edge is counted twice).

...more generally, the set of all weighted MVCs is the set of all VCs not containing neighbours. For example, in a tree where no child is a parent, the set of leaf nodes is also a valid weighted MVC.

Upvotes: 3

Related Questions