BTechibtechi.in
Loading Loading
Free IIT Madras BS notes, PYQs and mock tests at btechi.in

Advanced Algorithms · Iterative compression & FPT

21 questions · 45 marks · 3 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

Advanced Algorithms

Iterative compression & FPT

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
MCQ: Exactly 1 option is correct. Negative marking applies.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

End Term · 31 Aug 2025 (FN)End Term

Q1MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D

End Term · 31 Aug 2025 (AN)End Term

Q2MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D

Quiz 2 · 3 Aug 2025 (AN)Quiz 2

Read the passage below, then answer Q3–Q14
Q3MCQ3 Marks·Choose one option
Key ↓
A graph G is a cluster graph if and only if it does not have an induced path on 3 vertices.
1. ATRUE
2. BFALSE
Q4MCQ2 Marks·Choose one option
Key ↓
1. A
2. B
3. C
Q5MCQ2 Marks·Choose one option
Key ↓
In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on S is not a cluster graph, we can immediately return YES.
1. ATRUE
2. BFALSE
Q6MCQ2 Marks·Choose one option
Key ↓
In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on the vertices of S is not a cluster graph, we can immediately return NO.
1. ATRUE
2. BFALSE
Q7MCQ2 Marks·Choose one option
Key ↓
If 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 vertices in S which are in different cliques, then we can delete it and leave the parameter unchanged.
1. ATRUE
2. BFALSE
Q8MCQ2 Marks·Choose one option
Key ↓
If 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 vertices in S which are in different cliques, then we can delete it and decrease the parameter by 1.
1. ATRUE
2. BFALSE
Q9MCQ2 Marks·Choose one option
Key ↓
If 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 all vertices in a clique of G[S], then we can delete it and leave the parameter unchanged.
1. ATRUE
2. BFALSE
Q10MCQ2 Marks·Choose one option
Key ↓
If 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 all vertices in a clique of G[S], then we can delete it and decrease the parameter by 1.
1. ATRUE
2. BFALSE
Q11MCQ2 Marks·Choose one option
Key ↓
After modifying the input instance, we can solve DISJOINT CLUSTER VERTEX DELETION by solving a matching problem on a bipartite graph.
1. ATRUE
2. BFALSE
Q12MCQ2 Marks·Choose one option
Key ↓
DISJOINT CLUSTER VERTEX DELETION is polynomial time solvable.
1. ATRUE
2. BFALSE
Q13MCQ2 Marks·Choose one option
Key ↓
DISJOINT CLUSTER VERTEX DELETION is NP-hard.
1. ATRUE
2. BFALSE
Q14MCQ2 Marks·Choose one option
Key ↓
1. ATRUE
2. BFALSE
Read the passage below, then answer Q15–Q21
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.
Q15MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 2 shows a valid intermediate instance in the reduction with k= 2.
1. ATRUE
2. BFALSE
Q16MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 3 shows a valid intermediate instance in the reduction with k= 2.
1. ATRUE
2. BFALSE
Q17MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 4 shows a valid intermediate instance in the reduction with k= 2.
1. ATRUE
2. BFALSE
Q18MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 5 shows a valid intermediate instance in the reduction with k= 2.
1. ATRUE
2. BFALSE
Q19MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 4 shows a valid intermediate instance in the reduction with k= 1.
1. ATRUE
2. BFALSE
Q20MCQ2 Marks·Choose one option
Key ↓
The graph in Figure 1 has a FVS disjoint from S of size 2.
1. ATRUE
2. BFALSE
Q21MCQ2 Marks·Choose one option
Key ↓
The graph in Figure 1 has a FVS disjoint from S of size 1.
1. ATRUE
2. BFALSE

Official Key

Master Answer Key & Explanations

Official answer keys from IIT Madras BS past papers. Click any question to review.

Reveal Key

Q1D

Q2C

Q3A

Q4A

Q5B

Q6A

Q7B

Q8A

Q9B

Q10A

Q11A

Q12A

Q13B

Q14A

Q15B

Q16A

Q17B

Q18A

Q19B

Q20A

Q21A

Questions and answer keys are reproduced from the official IIT Madras BS papers. Topics and repeated question types are BTechi’s own grouping. BTechi is not affiliated with IIT Madras.