Statement 1: Given a graph G=(V,E) in which each vertex v∈V has an associated…
2022
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
\(\sum_{v \in V}^{n} \mathrm{w}(v) \mathrm{x}(v)\)
\(\text { subject to }\)
\(x(u)+x(v) \geq 1 \text { for each }(u, v) \in V\)
\(\quad x(v) \leq 1 \text { for each } v \in V\)
\(\quad x(v) \geq 0 \text { for each } v \in V\)
In the light of the above statements, choose the most appropriate answer from the options given below:
- A.
Both statement I and Statement II are correct
- B.
Both statement I and Statement II are incorrect
- C.
Statement I is correct but Statement II is incorrect
- D.
Statement I is incorrect and Statement II is correct
Attempted by 6 students.
Show answer & explanation
Correct answer: C
Answer: Statement 1 is correct; Statement 2 is incorrect.
Why Statement 1 is correct:
The minimum-weight vertex cover can be formulated as an integer program. Relaxing the integrality constraints to allow variables in [0,1] gives a linear program whose optimal value is a lower bound on the integer optimum.
Correct LP relaxation (for reference):
Minimize the weighted sum: minimize sum over v in V of w(v) x(v).
Subject to covering constraints: x(u) + x(v) ≥ 1 for each edge (u,v) in E.
Bounds: 0 ≤ x(v) ≤ 1 for each v in V.
Why this LP gives a lower bound:
Every integral vertex cover (with x(v) in {0,1}) is feasible for the relaxed LP, so the LP optimal value is less than or equal to the integer optimum.
What is wrong in the given Statement 2:
It states a maximization problem; the correct LP is a minimization of the weighted sum.
The covering constraint must be enforced for each edge (u,v) in E, not for each pair of vertices in V.
The variable bounds 0 ≤ x(v) ≤ 1 are correct, but they do not fix the other two mistakes.
Therefore the correct conclusion is that Statement 1 is true and Statement 2, as written, is false.