Q73.Marks: +2.0UGC NET Paper 2: Computer Science 11 March 2023
Statement 1: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to find the lower bound on the weight of the minimum-weight vertex cover.
Statement 2: The lower bound can be found by maximizing the following
\(\rm\sum_{v \in V}^n {w}(v) {x}(v)\)
subject to
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.Both statement I and Statement II are correct
2.Both statement I and Statement II are incorrect
3.Statement I is correct but Statement II is incorrect ✓ Correct
4.Statement I is incorrect and Statement II is correct
Solution
The correct answer is Statement I is correct but Statement II is incorrect
Key PointsI'll break down the two statements and explain why they are both considered correct:
Statement 1:
Given a graph \(G = (V, E)\) in which each vertex \(v \in V\) has an associated positive weight \(w(v)\), we can use linear programming to find the lower bound on the weight of the minimum-weight vertex cover.
Explanation:
This statement is correct. Linear programming can be used to find the lower bound on the weight of the minimum-weight vertex cover by formulating it as an optimization problem.
Statement 2:
The lower bound can be found by maximizing the following
\( \sum_{v \in V}^n w(v) x(v)\)
subject to
\(x(u) + x(v) \geq 1 \text{ for each } (u, v) \in E\)
\(x(v) \leq 1 \text{ for each } v \in V\)
\(x(v) \geq 0 \text{ for each } v \in V\)
Explanation: This is incorrect. For the minimum weight vertex cover problem, the objective function should be minimized, not maximized. Also, the constraint x(u) + x(v) ≥ 1 should be for each edge (u, v) ∈ E (not V). With these corrections, the model will be like this: It should be instead of \(\sum_{v \in V}^n w(v) x(v)\).
So, the corrected objective function should be: \( \sum_{v \in V} w(v) x(v) \)
