Assignment 5 Part I Solution

Graph Colouring. Consider the family of decision problems “k-colour,” for positive integers k, defined as follows. (Note that this defines infinitely many decision problems, one for each k).



Input: Undirected graph G = (V ; E).




Question: Is it possible to assign a colour to each vertex of G (where the same colour can be assigned to more than one vertex), so that every edge of G has endpoints with different colours and no more than k different colours are used?




For example, if G is a cycle on 5 vertices, the answer is “no” for the 2-colour problem but “yes” for the 3-colour problem.




Assume that 3-colour is NP-complete.




Write a detailed proof that k-colour is NP-complete for all k 3.




Graph Colouring, continued. Prove that 3-colour is polynomial-time self-reducible.



Start by writing down a precise definition of the search problem you are trying to solve, and explain what you are doing (and to what purpose) at each stage. Write your algorithms in pseudo-code (with comments to make your intentions clear), and remember to include a detailed argument of correctness and runtime analysis.




Hint: For any undirected graph G = (V ; E) and any vertices u; v 2 V , let Guv be the graph obtained by merging u and v into a single vertex (and getting rid of duplicate edges). For example, if G = (V ; E) with V = {a; b; c; d; e} and E = {(a; b);(b; c);(c; d);(d; e);(e; a)}, then Gbe = (Vbe; Ebe) with Vbe = {a; be; c; d} and Ebe = {(a; be);(be; c);(c; d);(d; be)}. Think about how the colourability of G relates to the colourability of Guv for pairs u; v 2 V that are not adjacent (i.e., (u; v) < E).




There will be one more question on approximation algorithms, coming soon in Part II!




























Dept. of Computer Science, University of Toronto, St. George Campus page 1 of 1
CSC 373 H1 Assignment #5—Part II







Worth: 7.5% (best four of the five assignments) Due: before 6:00pm on Wed. 3 April




Required filename for MarkUs submission: a5.pdf




(Use a single file to submit your answers for both Part I and Part II.)




Remember to write the full name and MarkUs username of every group member (up to three) prominently on your submission.







Please read and understand the policy on Collaboration given on the Course Information Sheet. Then, to protect yourself, list on the front of your submission every source of information you used to complete this homework (other than your own lecture and tutorial notes). For example, indicate clearly the name of every student from another group with whom you had discussions, the title and sections of every textbook you consulted (including the course textbook), the source of every web document you used (including documents from the course webpage), etc.




For each question, please write up detailed answers carefully. Make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.










Suppose that the City of Toronto is considering a plan to install traffic light cameras at various intersections. They have a map of the intersections in a neighbourhood of Toronto (shown on the right), and estimates ai;j of the number of accidents that could be prevented



at intersection (i; j) by installing a camera there. However, the camera technology makes it impossible to install cameras at intersections (i 1; j), (i + 1; j), (i; j 1), and (i; j + 1) (for those intersections that exist) if there is a camera at intersection (i; j). As you can guess, they would like to select intersections where to install cameras in order to maximize the total number of accidents prevented.







a 1
a 2


am;n
m;
m;


















:
:




:
:
:




:
:
:
:


a2;2






a2;n










a2;1
















a1;1
a1;2






a1;n










Write a greedy algorithm to try and select intersections in order to maximize the total number of accidents prevented. (Hint: There is a natural greedy strategy to try here—use it!—the goal is not to come up with a fancy algorithm.)



Then, give a precise counter-example to show that your greedy algorithm does not always find an optimum solution. State clearly the solution found by your algorithm, and show that it is not optimum by giving another selection with a larger number of accidents prevented.




Find and prove a bound on the approximation ratio of your algorithm. (Hint: Let S be the selection returned by your greedy algorithm and let T be any other valid selection of intersections. Show that for all (i; j) 2 T , either (i; j) 2 S or there is an adjacent (i0; j0) 2 S with ai0;j0 ai;j . What does this means for all (i; j) 2 S and their adjacent corners?)

































Dept. of Computer Science, University of Toronto, St. George Campus page 1 of 1