Question 3 (Matchings; 10 marks) Graph colouring problems, independent sets, and matchings are closely related. A proper vertex colouring is an assignment of colours to the vertices of a graph so that there is no edge whose endpoints have the same colour. A proper edge colouring is an assignment of colours to the edges of a graph so that there are no two edges of the same colour that share an endpoint. The vertex colouring problem asks us to find a proper vertex colouring of a graph using as few different colours as possible. The edge colouring problem asks us to find a proper edge colouring of a graph using as few different colours as possible. Both problems are NP-hard in general graphs. Colouring problems can also be stated as partitioning problems. For the vertex colouring problem, note that the set of all vertices of the same colour form an independent set: no two vertices of the same colour are connected by an edge. So vertex colouring asks us to partition the vertex set of the graph into as few independent sets as possible. For the edge colouring problem, the set of all edges of the same colour form a matching: no two edges of the same colour share an endpoint. So the edge colouring problem asks us to partition the edge set of the graph into as few matchings as possible. Both vertex colouring and edge colouring stop being NP-hard on bipartite graphs. Every bipartite graph G=(U,W,E) can trivially be vertex-coloured using only two colours: colour the vertices in U using one colour and the vertices in W using another colour. Unless there are no edges, the graph cannot be vertex-coloured using a single colour, so two is the optimal number of colours. In this assignment question, you are asked to exploit the relationship between edge colourings and matchings to obtain a polynomial-time algorithm for finding a proper edge colouring of a bipartite graph using the minimum number of colours. Note that if A = maxpeluw deg(u) is the maximum degree of all vertices in the graph, every proper edge colouring needs to use at least A colours because the edges incident to each vertex need to receive different colours. Here, you will develop an algorithm that finds an edge colouring that uses A colours 2 and thus is an optimal edge colouring. The running time of your algorithm should be O(Anm). (a) Prove that in a bipartite graph where every vertex has degree at most A, it is possible to find, in O(nm) time, a matching M with the property that every unmatched vertex has degree strictly less than A (b) Prove that the algorithm from (a) can be used to decompose the edge set of G into A matchings, in O(Anm) time. Since such a decomposition corresponds to a valid edge colouring with A colours, this gives an optimal edge colouring in O(Anm) time. Part (b) is fairly straightforward. Part (a) is the difficult part. The key claim you should prove is the following: Let a A-augmenting path be an alternating path P with endpoints u and v that satisfies the following properties: u is an unmatched vertex of degree A. Pis either an augmenting path for the current matching M or it has even lengthso the edge in P incident to v is in Mand v has degree strictly less than A. Then as long as the current matching M leaves some degree-A vertex unmatched, there exists a A-augmenting path and such a path can be found using alternating BFS from the unmatched vertices of degree A. The idea is that if Pisa A-augmenting path for M, then MePis a matching that leaves fewer degree-A vertices unmatched than M does. Thus, after at most n augmentations of M using A-augmenting paths, we obtain the desired matching that matches all vertices of degree A. Your argument that a A-augmenting path exists if there is an unmatched degree-A vertex needs to use that the graph is bipartite because the claim is wrong for some non-bipartite graphs. Here is the outline of one strategy that you could use: Assume that there exists an unmatched degree-A vertex ue U (if all unmatched degree-A vertices are in W, then we exchange the roles of U and W). Then run alternating BFS from u and let T be the alternating tree this constructs. You should be able to prove that T must either contain an unmatched vertex in w or a vertex in U of degree less than A. In the former case, you should be able to conclude that there exists an augmenting path for M. In the latter case, there exists an even-length alternating path from u to some vertex of degree less than A. Question 3 (Matchings; 10 marks) Graph colouring problems, independent sets, and matchings are closely related. A proper vertex colouring is an assignment of colours to the vertices of a graph so that there is no edge whose endpoints have the same colour. A proper edge colouring is an assignment of colours to the edges of a graph so that there are no two edges of the same colour that share an endpoint. The vertex colouring problem asks us to find a proper vertex colouring of a graph using as few different colours as possible. The edge colouring problem asks us to find a proper edge colouring of a graph using as few different colours as possible. Both problems are NP-hard in general graphs. Colouring problems can also be stated as partitioning problems. For the vertex colouring problem, note that the set of all vertices of the same colour form an independent set: no two vertices of the same colour are connected by an edge. So vertex colouring asks us to partition the vertex set of the graph into as few independent sets as possible. For the edge colouring problem, the set of all edges of the same colour form a matching: no two edges of the same colour share an endpoint. So the edge colouring problem asks us to partition the edge set of the graph into as few matchings as possible. Both vertex colouring and edge colouring stop being NP-hard on bipartite graphs. Every bipartite graph G=(U,W,E) can trivially be vertex-coloured using only two colours: colour the vertices in U using one colour and the vertices in W using another colour. Unless there are no edges, the graph cannot be vertex-coloured using a single colour, so two is the optimal number of colours. In this assignment question, you are asked to exploit the relationship between edge colourings and matchings to obtain a polynomial-time algorithm for finding a proper edge colouring of a bipartite graph using the minimum number of colours. Note that if A = maxpeluw deg(u) is the maximum degree of all vertices in the graph, every proper edge colouring needs to use at least A colours because the edges incident to each vertex need to receive different colours. Here, you will develop an algorithm that finds an edge colouring that uses A colours 2 and thus is an optimal edge colouring. The running time of your algorithm should be O(Anm). (a) Prove that in a bipartite graph where every vertex has degree at most A, it is possible to find, in O(nm) time, a matching M with the property that every unmatched vertex has degree strictly less than A (b) Prove that the algorithm from (a) can be used to decompose the edge set of G into A matchings, in O(Anm) time. Since such a decomposition corresponds to a valid edge colouring with A colours, this gives an optimal edge colouring in O(Anm) time. Part (b) is fairly straightforward. Part (a) is the difficult part. The key claim you should prove is the following: Let a A-augmenting path be an alternating path P with endpoints u and v that satisfies the following properties: u is an unmatched vertex of degree A. Pis either an augmenting path for the current matching M or it has even lengthso the edge in P incident to v is in Mand v has degree strictly less than A. Then as long as the current matching M leaves some degree-A vertex unmatched, there exists a A-augmenting path and such a path can be found using alternating BFS from the unmatched vertices of degree A. The idea is that if Pisa A-augmenting path for M, then MePis a matching that leaves fewer degree-A vertices unmatched than M does. Thus, after at most n augmentations of M using A-augmenting paths, we obtain the desired matching that matches all vertices of degree A. Your argument that a A-augmenting path exists if there is an unmatched degree-A vertex needs to use that the graph is bipartite because the claim is wrong for some non-bipartite graphs. Here is the outline of one strategy that you could use: Assume that there exists an unmatched degree-A vertex ue U (if all unmatched degree-A vertices are in W, then we exchange the roles of U and W). Then run alternating BFS from u and let T be the alternating tree this constructs. You should be able to prove that T must either contain an unmatched vertex in w or a vertex in U of degree less than A. In the former case, you should be able to conclude that there exists an augmenting path for M. In the latter case, there exists an even-length alternating path from u to some vertex of degree less than A