Q1 Set Cover (SC)
CSC373 Fall’20 Tutorial 7 Solutions 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.
Solution to Q1
We have one binary variable vi ∈ {0, 1} to indicate whether element xi ∈ E is chosen in the desired set C. The IP is as follows.
Minimize ni=1 vi
Subject to:
i:xi∈Hj vi ≥ 1, for each j ∈ {1,…,m}; vi ∈ {0,1}, for each i ∈ {1,…,n}.
Note that the constraint ensures that for each set Hj, at least one of the vi-s corresponding to its elements xi-s will be set to 1. Hence, the resulting C ensures C ∩ Hj ̸= ∅ for each Hj . Subject to this, we are minimizing |C| = i vi, which gives us the desired solution.
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?
1
Solution to Q2
• P: One can brute-force and check all triplets of vertices for triangles in O(n3) time.
• NP: Given a k-clique as advice, a TM can verify in polynomial time whether all k pairs of
vertices have an edge. (Think why O(k2) is polynomial time.)
2
• co-NP: If the answer is NO (i.e. there is a non-empty subset of S with zero sum), then given such a subset as advice, a TM can verify in polynomial time that its sum is indeed zero and thus the answer to the problem is NO.
• NP: Given a Hamiltonian path as advice, a TM can verify that it includes every vertex exactly once and there is an edge between every pair of adjacent vertices (i.e. it is indeed a path).
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).
Solution to Q3
1. Given G = (V, E) for the HC problem, create G′ = (V ′, E′) for the HP problem as follows.
• Start with G′ = G.
• Choose an arbitrary vertex v ∈ V and add a copy of it (say v′) to G′: that is, for every (v,u) ∈ E, we also add (v′,u) ∈ E′.
• Add a new “start” vertex s and a new “end” vertex t. Add edges (s,v) and (t,v′) to G′. The construction of G′ from G is shown in the figure below.
WeprovethatGhasanHCifandonlyifG′ hasanHP.
First, suppose G has an HC. Then, we can construct an HP in G′ as follows: we start from s, then visit v, then follow the HC in G, and when the HC is about to return to v from some vertex (say w), we instead go from w to v′, and then v′ to t.
Next, suppose G′ has an HP. Then, because s and t have degree 1 each, they must be the two endpoints of the HP. Then, the second and the second to last vertices in the HP must v and v′.
2
Figure 1: Citation: https://math.stackexchange.com/a/1290804
Then, a HC in G can be constructed by starting at v, following the HP in G′, and instead of
reaching v′ from some vertex (say w), going from w to v to complete the cycle.
2. Given G = (V, E) for the HP problem, create G′ = (V ′, E′) for the HC problem as follows.
• Start with G′ = G.
• Addanewvertexuandaddedges(u,v)foreveryv∈V.
Note that there is a 1-1 correspondence between HPs in G and HCs in G′: (v1, . . . , vn) is an HP of
G if and only if (u,v1,…,vn) is an HC of G′ (where we return from vn to u at the end).
3