Question

(a) Given a graph G = (V, E) and a number k (1 ≤ k ≤ n), the CLIQUE problem
asks us whether there is a set of k vertices in G that are all connected to one
another. That is, each vertex in the ”clique” is connected to the other k − 1
vertices in the clique; this set of vertices is referred to as a ”k-clique.” Show
that this problem is in class NP (verifiable in polynomial time) by providing
a function isClique(G,X,k) that, given a graph G in a form of adjacency
list stored in dictionary, and list of vertices X, checks whether a given set of
vertices X in fact a k-clique.

(b) In the comments, provide an answer - what is the running time of your algo-
rithm in terms of n and k, and why does it imply that CLIQUE is in NP?

(c) Thoroughly test your code. Test your program on the friendship graph you
created earlier. Test it on other graphs, try to make one test graph to be
”typical” and two to be in some way special, flawed or degenerate (a graph
without edges at all, or with several connected components, or only with
|V | − 1 edges, or with edges between all vertices, etc). Each of the graphs
should have at minimum seven vertices.

Please include your code for the isClique(G,X,k) function. It should expect to take as input a graph G, a list of vertices X, and a number k which is the length of X. It should return True if X is a k-clique in G, and False otherwise. Note that if X has a size different from k, then it is not a k-clique. Recall graphs are stored as dictionaries:

G = {1:[2,3],2:[1,3],3:[1,2]}

is a graph with three vertices, all connected (here [1,2,3] is a 3-clique, so isClique(G,[1,2,3],3) should return True).

in python

Answer 1

The Clique problem is NP-complete.

Proof. Lets use abbreviation CP for the Clique problem. IS is the Independent Set problem.

It suffices to show (a) the clique problem is in NP, and (b) IS ≤_p CP.

1. Part (a) is easy. We need to find a nondeterministic polynomial-time algorithm for CP.

   Pair (G, K) is in CP if there exists a set of vertices S of size at least K so that for every pair of vertices u and v in S, {u,v} is an edge in G.

   The evidence is a set of vertices S of size at least K. The evidence is accepted if {u,v} is an edge in G, for every pair of vertices u, v in S.

2. Part (b) is also easy. Define f(G, K) = (G, K). Then

   (G,K) ∈ IS	⇔	G has an independent set of size at least K
   	⇔	G has a clique of size at least K
   	⇔	(G, K) ∈ CP

b.

"k-Clique problem" is NP-complete, and "k-Clique problem for a fixed k" is easily solvable in polynomial time, and there is no contradiction here.

Let F be a function "size of the problem" -> "time required to solve it".

"size of the problem" here is a length of an input string, which describes the problem. I guess it's not an obvious thing. It depends on "encoding". If we have a graph with ?n vertices, we will need at least ???(?)log(n) characters to encode a single node id, there may be about ?∗?n∗n edges, so we need ~ ?∗?∗???(?)n∗n∗log(n) characters to describe all the edges. To fully describe the problem we also need to include the "k" in the input string, so that the machine would know what kind of clique it is looking for. Probably some additional "formatting" characters would be necessary to delimit.

May be there are a little more compact ways to construct an input string. But looks like "size of the problem" is ?(??)O(nl) for some ?l. I am not ready to prove it.

If ?k is fixed, it's easy to construct a Turing machine which checks if k-Clique exists in a given graph. This machine would require polynomial time to solve the problem. Either ?(??)O(nm) or ?(O("size of the problem"?)m) - it does not really matter since "size of the problem" is ?(??)O(nl).

But if ?k is not fixed, there is no way to construct a Turing machine which would solve the problem in ?(O("size of the problem"?)m) time. Size of the problem "is there a ?n-Clique in 2∗?2∗n nodes graph" is polynomial of ?n, but all the techniques we used to solve the problem for a fixed ?k would not help us to solve this problem fast (in polynomial of ?n or polynomial of "size of the problem" time).

def k_subsets(lst, k):
	if len(lst) < k:
	return []
	if len(lst) == k:
	return [lst]
	if k == 1:
	return [[i] for i in lst]
	return k_subsets(lst[1:],k) + map(lambda x: x + [lst[0]], k_subsets(lst[1:], k-1))
	# Checks if the given list of nodes forms a clique in the given graph.
	def is_clique(G, nodes):
	for pair in k_subsets(nodes, 2):
	if pair[1] not in G[pair[0]]:
	return False
	return True
	# Determines if there is clique of size k or greater in the given graph.
	def k_clique_decision(G, k):
	nodes = G.keys()
	for i in range(k, len(nodes) + 1):
	for subset in k_subsets(nodes, i):
	if is_clique(G, subset):
	return True
	return False
	def make_link(G, node1, node2):
	if node1 not in G:
	G[node1] = {}
	(G[node1])[node2] = 1
	if node2 not in G:
	G[node2] = {}
	(G[node2])[node1] = 1
	return G
	def break_link(G, node1, node2):
	if node1 not in G:
	print "error: breaking link in a non-existent node"
	return
	if node2 not in G:
	print "error: breaking link in a non-existent node"
	return
	if node2 not in G[node1]:
	print "error: breaking non-existent link"
	return
	if node1 not in G[node2]:
	print "error: breaking non-existent link"
	return
	del G[node1][node2]
	del G[node2][node1]
	return G
	def k_clique(G, k):
	k = int(k)
	if not k_clique_decision(G, k):
	return False
	if k == 1:
	return [G.keys()[0]]
	for node1 in G.keys():
	for node2 in G[node1].keys():
	G = break_link(G, node1, node2)
	if not k_clique_decision(G, k):
	G = make_link(G, node1, node2)
	for node in G.keys():
	if len(G[node]) == 0:
	del G[node]
	return G.keys()