(a) State three famous computational problems known to be NP-complete. (1 mark)
ID: 3758864 • Letter: #
Question
(a) State three famous computational problems known to be NP-complete. (1 mark) (b) State one famous computational problem known to be in NP and co-NP, but not known to be in P. (1 mark) (c) State one famous computational problem that was first proved to be in P in this century. (1 mark) (d) Formally define the decision problem Independent Set. (2 marks) (e) Give a polynomial-time reduction (both directions) between Independent Set and the following problem Clique. For Clique. the input is a graph G and a nonnegative integer k. The question is: does the graph have a subgraph H that is a clique (every vertex of H is connected to every other) with at least k vertices? (5 marks)Explanation / Answer
Definition: An independent set is a set I V of vertices such that for all u, v 2 I, (u, v) /2 E.
• Definition: The independent set decision problem is as follows: Given a graph G, is there an independent
set I of vertices of size at most k?
Show that Independent Set is NP-Complete.
Solution: Our solution consists of two parts. We first show that Independent Set (IS) is in NP
and then we show that IS is NP-Hard.
– NP: In order to show that IS € NP, we must show that there exists a polynomial time witness
algorithm that takes an instance of the problem and a certificate as parameters, and verifies
that the certificate is a yes instance of the particular inputed problem. Thus, our instance is an
unweighted graph G, and our certificate is a set of vertices. Our algorithm performs 2 steps:
1. Checks that the all vertices in the certificate are vertices in the graph.
2. Checks that there are no edges between any two vertices in the certificate.
This algorithm runs in O(V + E), and is thus clearly polynomial time. Thus, IS € NP.
(Note:here ‘€’ means belongs to)
NP-Hard: In order to show that IS € NP-Hard, we will reduce from Clique to IS. Our
reduction consists of demonstrating a polynomial time conversion of an instance of Clique to an
instance of IS, and an if-and-only-if proof that a yes instance of Clique maps to a yes instance
of IS and vice versa.
1. We will convert an instance of Clique to an instance of IS in the following manner. An
instance of Clique is a graph G and an integer k. We will construct Gc, the complement of
G, and pass Gc, k to IS.
2. Now we will show that a yes instance of Clique maps to a yes instance of IS and vice versa.
· =) Assume G is a yes instance of Clique, or assume that there exists a clique C of size
k in G. Thus, for any u, v € C, (u, v) € E. Thus, (u, v) not belongs to Ec. Thus, the vertices in C
form an indepedent set in Gc. Thus, Gc is a yes instance of IS.
· (= Assume Gc is a yes instance of IS, or assume that there exists an independent set I
of size k in Gc. Thus, for any u, v € I, (u, v) /2 Ec. Thus, (u, v) € E. Thus, the vertices
in I form a clique in G. Thus, G is a yes instance of Clique
Thus, since we have shown that IS is in both NP and NP-Hard, we have shown that IS 2 NP-Complete
b. When G is a tree (not necessarily binary), is this problem still NP-Complete?
Solution: No.
We will store two values with every vertex, maxin and maxout, referring to the size of the largest indepedent
set possible if that particular vertex is either in or out of the independent set. Our polynomial-time
algorithm to find a maximum-cardinality independent set is thus constructed as follows.
1. DFS down to a leaf. Let maxin = 1 and maxout = 0.
2. Begin to recurse back out of tree. For each interior node, maxin and maxout are defined as follows:
maxin = 1 +children maxout (31)
maxout =childrenmaxin (32)
3. Thus, to determine the largest independent set, we simply take the max(maxin, maxout) of the
root.
This algorithm clearly runs in O(V + E) time because we are only augmenting DFS with a few
arithmetic operations per step
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.