Q1 Set Cover (SC)
CSC373 Fall’20 Tutorial 7 Nov 3, 2020
Given a set of elements E = {x1,x2,…,xn} and a collection S = {H1,H2,…,Hm} containing subsetsofE,wewanttofindasmallestsubsetCofEsuchthatC∩Hj ̸=∅foreveryHj ∈S. Write an integer program for this.
Q2 Complexity
Are the following decision problems in P/NP/co-NP? Give the strongest possible answer (i.e. if you can show that the decision problem is in P, use that instead of NP or co-NP).
1. TRIANGLE
Input: An undirected graph G = (V, E).
Question: Does G contain a “triangle” (i.e. a subset of three vertices such that there is an edge between any two of them)?
2. CLIQUE
Input: An undirected graph G = (V, E) and a positive integer k.
Question: Does G contain a k-clique (i.e. a subset of k vertices such that there is an edge between any two of them)?
3. NON-ZERO
Input: A set of integers S.
Question: Does every non-empty subset of S have non-zero sum?
4. HAMILTONIAN-PATH (HP)
Input: An undirected graph G = (V, E).
Question: Does G contain a simple path that includes every vertex?
Q3 Reductions
Consider the Hamiltonian Cycle (HC) problem, which is similar to the HP problem described above.
HAMILTONIAN-CYCLE (HC)
Input: An undirected graph G = (V, E).
Question: Does G contain a simple cycle that includes every vertex?
1. The textbook CLRS shows that HC is is NP-complete (Subsection 34.5.3). Give a reduction from HC to HP (i.e. HC ≤p HP) to prove HP is also NP-complete.
2. Suppose instead that we knew HP is NP-complete, and wanted to use it to show that HC is NP-complete. Give a reduction from HP to HC (i.e. HP ≤p HC).
1