Theories of Computation: Summative Assignment 3: CLIQUE problem and polynomial bounds

Theories of Computation: Summative Assignment 3 To be handed in on Canvas before Tuesday 25th April, 12pm An undirected graph G consists of vertices and edges, and its sizeis the number of vertices. For example, here are two undirected graphs of size 4: 0 1 2 3G1=0 1 2 3G2= We take the vertices to be numbered 0;1;:::;n1, wherenis the size of the graph. A clique in G is a set of vertices with any two distinct vertices appearing in the list are related by an edge. The CLIQUE problem consists in deciding whether a given undirected graph G contains a clique of a given size. For example,G1contains a clique of length 3 but G2does not. Apropositional formula 'is constructed from atoms and the connectives :,_and^. The sizej'jof a formula is the number of occurences of atoms in it. An assignment gives value True orFalse to each atom; it is satisfying for a formula 'if it makes the formula True . The S ATproblem consists in deciding whether a given formula 'has a satisfying assignment. The purpose of this exercise is to establish a polytime reduction from C LIQUE to S AT. CourseNana.COM

1. Let’s first consider one instance: deciding whether G1above contains a clique of size 3. We’ll define a propo-

   sitional formula '3

   G1=3

   G1^3

   G1that has a satisfying assignment if and only if G1has a clique of size 3. (It

   does, but imagine that we do not yet know this.)

   Such a clique, if it exists, can be listed in increasing order. For i<3andp< 4, the atomxi;pmeans thatpis the

   ith element of the list. This forms our set At=fx0;0;:::;x 0;3;x1;0;:::;x 1;3;x2;0;:::;x 2;3gof propositional

   atoms.

   The first part of the formula will be

   3

   G1= (x0;0_x0;1_x0;2_x0;3)^(x1;0_x1;1_x1;2_x1;3)^(x2;0_x2;1_x2;2_x2;3)^

   ((x0;0^x0;1)(x0;0^x0;2)(x0;0^x0;3)(x0;1^x0;2)(x0;1^x0;3)_(x0;2^x0;3))^

   ((x1;0^x1;1)(x1;0^x1;2)(x1;0^x1;3)(x1;1^x1;2)(x1;1^x1;3)_(x1;2^x1;3))^

   ((x2;0^x2;1)(x2;0^x2;2)(x2;0^x2;3)(x2;1^x2;2)(x2;1^x2;3)(x2;2^x2;3)) to express having a list of 3vertices ofG1. Write a formula 3 G1, shorter than 3 G1, to express that the list is in increasing order and represents a clique. Hint: First describe the relationship between the 0th and 1st element of the list. For example, for G2above, it would be (x0;0^x1;2)(x0;1^x1;2)_(x0;1^x1;3). There is no need to use negation in your formula. [3 marks] 1

2. Now let us extend this definition to 'k G=k G^k Gfor an undirected graph Gof any sizenand anykn. Again, if a clique exists, it can be listed in increasing order. For i<k andp<n , the atomxi;pmeans thatpis theith element of the list. To begin, we write k G=^ i<k p<nxi;p! ^^ i<k: p<q<n(xi;p^xi;q)! to express having a list of kvertices ofG. Give a formula k Gto express that the list is in increasing order and represents a clique. The set of edges is writtenE, so(p;q)2Emeans that there is an edge from ptoq. [3 marks]
3. Show that the size of 'k Gis polynomially bounded by the size of G, that is, there exists a polynomial Psuch thatj'k GjP(n). Hint: You can find polynomial bounds for jk Gjand forjk Gjindependently. This means that you can partially answer this question even if you could not answer the previous ones. [3 marks]
4. It follows that the time taken to construct 'k G fromGis polynomial in the size of G(since we can check in linear time whether (p;q)2E). Using what you know about the SAT problem, explain in a few lines what you could deduce about the C LIQUE problem if it were the case that P=NP. [3 marks]