Quiz Space

Advanced Algorithms · Quiz 2 · 3 Aug 2025 · May 2025 term

Question 13: Consider the following approximation algorithm for the w…

Question 13

+2 marksOne correct option

Consider the following approximation algorithm for the weighted vertex cover problem.

1: Solve the relaxed linear program corresponding to the given problem:

Minimize∑i=1nweight(vi)⋅xiSubject toxi+xj≥1for all edges (vi,vj)∈E0≤xi≤1for 1≤i≤n\begin{aligned} &\text{Minimize} \quad && \textstyle\sum_{i=1}^{n} \mathit{weight}(v_i) \cdot x_i \\ &\text{Subject to} \quad && x_i + x_j \geq 1 \quad \text{for all edges } (v_i, v_j) \in E \\ & && 0 \leq x_i \leq 1 \quad \text{for } 1 \leq i \leq n \end{aligned}

2: C←{vi∈V:xi≥1/2}C \leftarrow \{v_i \in V : x_i \geq 1/2\}

3: return CC

Based on the above data, answer the given subquestions.

  1. A

    We still get a valid solution, and the algorithm remains a 2-approximation.

  2. B

    We still get a valid solution, and the algorithm becomes a 3-approximation.

  3. C

    We may no longer get a valid solution.

Show answer

Correct answer

  • B

    We still get a valid solution, and the algorithm becomes a 3-approximation.

See the whole paperTake it as a mock test

Question 13 of 26 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 3 Aug 2025, in the May 2025 term (IIT M IMPROVEMENT AN EXAM QIM2 03 Aug 2025). It carries 2 marks.

More questions from this paper

  1. Q1A graph G is a cluster graph if and only if it does not have an induced path on 3 vertices.
  2. Q2Consider the following algorithm for finding a smallest-sized subset of vertices S \subseteq V(G) such that the subgrap…
  3. Q3In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on S is not a cluster graph, we can immediatel…
  4. Q4In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on the vertices of S is not a cluster graph, w…
  5. Q5If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to at least two v…
  6. Q6If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to at least two v…
  7. Q7If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to some but not a…
  8. Q8If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to some but not a…
  9. Q9After modifying the input instance, we can solve DISJOINT CLUSTER VERTEX DELETION by solving a matching problem on a bi…
  10. Q10DISJOINT CLUSTER VERTEX DELETION is polynomial time solvable.
  11. Q11DISJOINT CLUSTER VERTEX DELETION is NP-hard.
  12. Q12A graph is called a cluster graph if and only if it is a disjoint union of cliques. The CLUSTER VERTEX DELETION (CVD) p…
  13. Q14Consider the following approximation algorithm for the weighted vertex cover problem. 1: Solve the relaxed linear progr…
  14. Q15In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DI…
  15. Q16In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DI…
  16. Q17In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DI…
  17. Q18In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DI…
  18. Q19In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DI…
  19. Q20In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DI…
  20. Q21In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DI…
  21. Q22Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  22. Q23Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  23. Q24Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  24. Q25Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  25. Q26Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…