4

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?

efficiencyIsBliss
  • 3,043
  • 7
  • 38
  • 44
  • 1
    "find the vertex cover of minimum weight": This should be clarified as "find a (any) vertex cover of minimum weight". – Nayuki Aug 15 '11 at 01:14

1 Answers1

3

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.

badroit
  • 1,316
  • 15
  • 28
  • I don't see how these are counter examples. I understand that in the first case, only `{B}` is a minimal vertex cover, but we're not going for the minimal VC, we are going for the minimal weight VC and by that definition, `{A, C}` is a valid answer. However, if we ran the algorithm for just the minimal VC, we would get `{B}` and that would also be a minimal weight VC. – efficiencyIsBliss Aug 15 '11 at 02:55
  • For the second example, I don't see why the fact that the `B -- C` edge is counted twice makes it an incorrect answer. The definition of a VC is that each edge should have `atleast` one vertex in the cover. – efficiencyIsBliss Aug 15 '11 at 02:57
  • @efficiencyIsBliss Erm... *"I understand that in the first case, only `{B}` is a minimal vertex cover, but we're not going for the minimal VC, we are going for the minimal weight VC and by that definition, `{A, C}` is a valid answer."* That's *exactly* what my answer says. That's exactly why it's a counter-example to the claim in your question *"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)."* – badroit Aug 15 '11 at 03:55
  • *"I don't see why the fact that the B -- C edge is counted twice makes it an incorrect answer."* My answer states that it's a *valid* (minimal) vertex cover, but an invalid weighted minimal vertex cover (by your definition) since the weight of `{ B, C }` is `4`, whereas, e.g., the weight of `{A, C}` is `3`. Is my answer really that misinterpretable? – badroit Aug 15 '11 at 04:03