Statement 1: su Given a graph G=(V, E) in which each vertex v € V has an associated positive weight w(v), we can Q use linear programming to find the lower bound on the weight of the minimum-weight vertex cover.

Statement 2 : Q The lower bound can be found by maximizing the following ∑n w(v)x(v) v∈V subject to Q x(u) + x(v) ≥ 1 for each (u, v) ∈ V x(v) ≤ 1 for each v ∈ V x(v) ≥ 0 for each v ∈ V In the light of the above statements, choose the most appropriate answer from the options given below:

1. ABoth statement I and Statement II are correct
2. BBoth Statement I and Statement II are incorrect
3. CStatement I is correct but Statement II is incorrect
4. DStatement I is incorrect and Statement II is correct

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. Statement I is correct but Statement II is incorrect

Explanation

The LP relaxation of weighted vertex cover gives a lower bound on the optimal weight (Statement I true). It must minimize Σ w(v)x(v), with constraints over edges (u, v) ∈ E, not maximize, so Statement II is incorrect.