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) \)