Quiz Space

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

Question 15: In Figure 1, we have a graph G and an FVS of size 3 whic…

Question 15

+2 marksOne correct option

In 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 DISJOINT FVS of size 2.

For each of the given statements in the subquestions, determine if it is true or false.

According to the reduction rules for DFVS, Figure 2 shows a valid intermediate instance in the reduction with k= 2.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • B

    FALSE

See the whole paperTake it as a mock test

Question 15 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. Q13Consider the following approximation algorithm for the weighted vertex cover problem. 1: Solve the relaxed linear progr…
  14. Q14Consider the following approximation algorithm for the weighted vertex cover problem. 1: Solve the relaxed linear progr…
  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…