Advanced Algorithms · Quiz 2 · May 2025

Advanced Algorithms · Quiz 2 · May 2025

← Course papers · Start practice / exam

Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.

0 / 26 published solutions

Question 203 MCQ · 3.0 marks

A graph G is a cluster graph if and only if it does not have an induced path on 3 vertices.

6406534473921.

TRUE

6406534473922.

FALSE

A published solution is not available for this question yet.

Report a correction for Q203

Question 204 MCQ · 2.0 marks

6406534473923.

6406534473924.

6406534473925.

A published solution is not available for this question yet.

Report a correction for Q204

Question 205 MCQ · 2.0 marks

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on S is not a cluster graph, we can immediately return YES.

6406534473926.

TRUE

6406534473927.

FALSE

A published solution is not available for this question yet.

Report a correction for Q205

Question 206 MCQ · 2.0 marks

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.

6406534473928.

TRUE

6406534473929.

FALSE

A published solution is not available for this question yet.

Report a correction for Q206

Question 207 MCQ · 2.0 marks

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.

6406534473930.

TRUE

6406534473931.

FALSE

A published solution is not available for this question yet.

Report a correction for Q207

Question 208 MCQ · 2.0 marks

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.

6406534473932.

TRUE

6406534473933.

FALSE

A published solution is not available for this question yet.

Report a correction for Q208

Question 209 MCQ · 2.0 marks

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.

6406534473934.

TRUE

6406534473935.

FALSE

A published solution is not available for this question yet.

Report a correction for Q209

Question 210 MCQ · 2.0 marks

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.

6406534473936.

TRUE

6406534473937.

FALSE

A published solution is not available for this question yet.

Report a correction for Q210

Question 211 MCQ · 2.0 marks

After modifying the input instance, we can solve DISJOINT CLUSTER VERTEX DELETION by solving a matching problem on a bipartite graph.

6406534473938.

TRUE

6406534473939.

FALSE

A published solution is not available for this question yet.

Report a correction for Q211

Question 212 MCQ · 2.0 marks

DISJOINT CLUSTER VERTEX DELETION is polynomial time solvable.

6406534473940.

TRUE

6406534473941.

FALSE

A published solution is not available for this question yet.

Report a correction for Q212

Question 213 MCQ · 2.0 marks

DISJOINT CLUSTER VERTEX DELETION is NP-hard.

6406534473942.

TRUE

6406534473943.

FALSE

A published solution is not available for this question yet.

Report a correction for Q213

Question 214 MCQ · 2.0 marks

6406534473944.

TRUE

6406534473945.

FALSE

A published solution is not available for this question yet.

Report a correction for Q214

Question 215 MCQ · 2.0 marks

Based on the above data, answer the given subquestions.

6406534473946.

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

6406534473947.

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

6406534473948.

We may no longer get a valid solution.

A published solution is not available for this question yet.

Report a correction for Q215

Question 216 MCQ · 2.0 marks

Based on the above data, answer the given subquestions.

6406534473949.

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

6406534473950.

We still get a valid solution, and the algorithm becomes a (3/2)-approximation.

6406534473951.

We may no longer get a valid solution.

A published solution is not available for this question yet.

Report a correction for Q216

Question 217 MCQ · 2.0 marks

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.

6406534473952.

TRUE

6406534473953.

FALSE

A published solution is not available for this question yet.

Report a correction for Q217

Question 218 MCQ · 2.0 marks

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 3 shows a valid intermediate instance in the reduction with k= 2.

6406534473954.

TRUE

6406534473955.

FALSE

A published solution is not available for this question yet.

Report a correction for Q218

Question 219 MCQ · 2.0 marks

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 4 shows a valid intermediate instance in the reduction with k= 2.

6406534473956.

TRUE

6406534473957.

FALSE

A published solution is not available for this question yet.

Report a correction for Q219

Question 220 MCQ · 2.0 marks

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 5 shows a valid intermediate instance in the reduction with k= 2.

6406534473958.

TRUE

6406534473959.

FALSE

A published solution is not available for this question yet.

Report a correction for Q220

Question 221 MCQ · 2.0 marks

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 4 shows a valid intermediate instance in the reduction with k= 1.

6406534473960.

TRUE

6406534473961.

FALSE

A published solution is not available for this question yet.

Report a correction for Q221

Question 222 MCQ · 2.0 marks

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.

The graph in Figure 1 has a FVS disjoint from S of size 2.

6406534473962.

TRUE

6406534473963.

FALSE

A published solution is not available for this question yet.

Report a correction for Q222

Question 223 MCQ · 2.0 marks

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.

The graph in Figure 1 has a FVS disjoint from S of size 1.

6406534473964.

TRUE

6406534473965.

FALSE

A published solution is not available for this question yet.

Report a correction for Q223

Question 224 MCQ · 1.0 marks

Based on the above data, answer the given subquestions.

6406534473966.

6406534473967.

6406534473968.

6406534473969.

A published solution is not available for this question yet.

Report a correction for Q224

Question 225 MCQ · 1.0 marks

Based on the above data, answer the given subquestions.

6406534473970.

6406534473971.

6406534473972.

6406534473973.

A published solution is not available for this question yet.

Report a correction for Q225

Question 226 MCQ · 1.0 marks

Based on the above data, answer the given subquestions.

6406534473974.

6406534473975.

6406534473976.

6406534473977.

A published solution is not available for this question yet.

Report a correction for Q226

Question 227 NAT · 2.0 marks

Based on the above data, answer the given subquestions.

For n= 4, calculate the number of sequences of length 4 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

A published solution is not available for this question yet.

Report a correction for Q227

Question 228 NAT · 2.0 marks

Based on the above data, answer the given subquestions.

For n = 5, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.

A published solution is not available for this question yet.

Report a correction for Q228