Advanced Algorithms · Quiz 2 · 3 Dec 2023 · September 2023 term

Question 18: The EXACT-COVER-BY-3-SETS problem is defined as the foll…

Question 18

+3 marksOne correct option

The EXACT-COVER-BY-3-SETS problem is defined as the following: given a finite set $X$ with $|X| = 3q$ and a collection $C$ of 3-element subsets of $X$ , does $C$ contain an exact cover for $X$ , that is, a subcollection $C' \subseteq C$ such that every element of $X$ occurs in exactly one member of $C'$ ?

The EXACT-COVER-BY-4-SETS problem is defined as the following: given a finite set $X$ with $|X| = 4q$ and a collection $C$ of 4-element subsets of $X$ , does $C$ contain an exact cover for $X$ , that is, a subcollection $C' \subseteq C$ such that every element of $X$ occurs in exactly one member of $C'$ ?

Given that EXACT-COVER-BY-3-SETS is NP-Complete, is EXACT-COVER-BY-4-SETS also NP-Complete?

A
Yes, because there is a reduction from EXACT-COVER-BY-3-SETS to EXACT- COVER-BY-4-SETS.
B
Yes, because there is a reduction from EXACT-COVER-BY-4-SETS to EXACT- COVER-BY-3-SETS.
C
EXACT-COVER-BY-4-SETS may or may not be NP-Complete.

Show answer

Correct answer

A
Yes, because there is a reduction from EXACT-COVER-BY-3-SETS to EXACT- COVER-BY-4-SETS.

See the whole paper Take it as a mock test

Question 18 of 20 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 3 Dec 2023, in the September 2023 term (IIT M DEGREE AN2 EXAM QDB2 03 Dec 2023). It carries 3 marks.

Question 18: The EXACT-COVER-BY-3-SETS problem is defined as the foll…

Question 18

More questions from this paper