CSC 425/520: Assignment #3: Fall 2016
Due at the beginning of class on Friday Nov. 18.

Instructions for all assignments:

1. Draw boxes for your marks on the top of the first page of your submission. Place a 0 in the corresponding box for any questions you omit. For this assignment:

   Question	1	2	3	4	5	6	7
   Marks	0	0	0	0	0	0	0

2. Questions should be in order.
3. Show your work unless otherwise stated.
4. Please put your name on your assignment.

For questions #1 and #2, the algorithms presented operate by assigning colors to the vertices. Initially all vertices are white (undecided). Red vertices are in the dominating set, and blue ones are excluded. The dominating set D returned by the algorithm is the set of red vertices.

1. [10 marks] One iteration of Algorithm #1 (Random Vertex Order Greedy) from the course project behaves as follows. A random permutation p of 0 to n-1 is generated. Then for i from 0 to n-1, vertex p[i] is colored blue as long as the resulting colored graph has no blue vertices with all blue neighbours. Otherwise, p[i] is colored red.

   Given a graph G and a minimum dominating set D, does there always exist some permutation p so that Algorithm #1 returns D? If you answer "yes", then explain how to compute such a permutation p from the dominating set D. If your answer is "no", give a counterexample consisting of a graph G and a minimum dominating set D, and show that there is no permutation of the vertices for which the algorithm returns D.

2. [10 marks] One iteration of Algorithm #2 (Random BFS order greedy) from the course project behaves as follows. A random root vertex r is selected. BFS is performed on the graph starting with vertex r. When the neighbours of a vertex are traversed, they are traversed in random order. The queue for the BFS contains a permutation p of the vertices that we will call a BFS-ordering. Algorithm #2 then proceeds as per Algorithm #1 using the BFS-ordering p.

   Given a graph G and a minimum dominating set D, does there always exist some BFS-ordering p so that Algorithm #1 returns D? If you answer "yes", then explain how to compute such a BFS-ordering p from the dominating set D. If your answer is "no", give a counterexample consisting of a graph G and a minimum dominating set D, and show that there is no BFS-ordering of the vertices for which the algorithm returns D.

3. The Queen graph of dimension d from the course project has n= d² vertices corresponding to squares on a d by d grid. Two vertices are adjacent if their squares lie on the same row, column, diagonal or back diagonal. Justify your answers for all parts of this question.
   (a) [2 marks] Give a formula in terms of d for the degree of the vertex in the upper left-hand corner of the grid.
   (b) [2 marks] Assume that d is an odd number. Give a formula in terms of d for the degree of the vertex in the middle of the grid.
   (c) [2 marks] Assume that d is an even number. In this case, there are 4 squares in the "middle" of the grid. Give a formula in terms of d for the degree of one of these squares in the middle. Note: by symmetry, all four of these vertices have the same degree.
   (d) [4 marks] Find a function f(n) so that the degree of each vertex is in THETA(f(n)). Choose f(n) so that it is as simple as possible.
   (e) [5 marks] Prove that the degrees of the vertices in the queen graph are in O(f(n)) by using the definition of Big Oh that uses constants c and n₀.
   (f) [5 marks] Prove that the degrees of the vertices in the queen graph are in OMEGA(f(n)) by using the definition of OMEGA that uses constants c and n₀.
4. The distance between two vertices u and v in a graph G is the length of a shortest path (measured in number of edges) between u and v. The diameter of a graph is the maximum distance between a pair of vertices.
   (a) [5 marks] The hypercube graph of dimension d has 2^d vertices each labelled with a different d-bit string. Two vertices are adjacent if their bit strings differ in exactly one position. Find a formula f(d) for the diameter of the dimension-d hypercube. Justify your answer.
   (b) [5 marks] The distance-2 hypercube graph has edges between two vertices if their bit strings differ in at most two positions. Find a formula g(d) that gives the diameter of the distance-2 hypercube graph. Justify your answer.
   (c) [5 marks] Is f(d) in THETA of g(d)? Justify your answer using the definition of THETA that uses constants c and n₀.
5. Suppose that a company has n boxes and the weights of the boxes in pounds are w₁, w₂, w₃, ... w_n. They want to ship the boxes in some delivery trucks. Each delivery truck can hold a maximum of K pounds. Consider the following greedy algorithm for loading boxes onto the trucks. The boxes are considered in some arbitrary order. As many as possible (without exceeding the weight limit K) are placed onto the first truck until you encounter a container whose addition would exceed the weight limit. Then this truck is considered to be full and is sent off. The process continues with a fresh truck.

   (a) [5 marks] Give an example of weights and a truck capacity K such that this greedy algorithm does not use a minimum possible number of trucks. Justify your answer.

   (b) [5 marks] Prove that this greedy algorithm is within a factor of 2 for any set of weights and any truck capacity K.

   (c) [5 marks] Describe an infinite family of problems such that the number of trucks used by the greedy algorithm is at least 1.5 times the minimum number of trucks needed.

6. [5 marks] Suppose n sensors are randomly distributed on the ground. Two sensors can communicate with each other if they are at most 10 feet apart. If the sensors are distributed so that every sensor has at least n/2 neighbours, is this sufficient to guarantee that the resulting graphs is connected? Decide whether you think this is true or not and then justify your answer.
7. The problem 3_COLOURABLE takes as input a graph G on n vertices and m edges and returns true if the vertices of G can be coloured so that if two vertices are adjacent they are coloured with different colours and false otherwise.
   (a) [5 marks] Prove that 3-COLOURABLE is in NP by describing an appropriate representation of a solution together with a polynomial time check function.
   (b) [10 marks] Explain how you could solve 3-COLOURABLE using a function which solves 3-SAT.
   Hint: try using three variables for each vertex v of the graph denoted by (v, 1), (v, 2) and (v, 3). If the final solution has (v, i) set to true, then v should be coloured with colour i. You need clauses which guarantee that:
   1. each vertex gets at least one colour,
   2. each vertex gets at most one colour, and
   3. if two vertices are adjacent, they must receive different colours.
   You can include clauses with only 2 variables in your solution.
   (c) [5 marks] Suppose the 3-SAT routine takes time p(r, c) where r is the number of variables and c is the number of clauses, and p is some polynomial in r and c. How much time does it take to solve 3-COLOURABLE as discussed above for a graph G with n vertices and m edges? Do not assume that m = n (n-1)/2, but instead express your answer as a function of n and m.
   (d) [5 marks] Does your work for parts (a)-(c) together with the assumption that 3-SAT is NP-complete prove that 3-COLOURABLE is NP-complete? If not, what would you have to do to prove it?