CSC 545 Homework 4 (version 1)
Please upload a single PDF file containing
your submission (ensuring scans of handwritten work are legible) on Gradescope by that time.
The questions are drawn from the material in the lectures on graph matchings.
The homework is worth a total of 100 points. When point breakdowns are not given for the
parts of a problem, each part has equal weight.
Please remember to start each problem on a new page, and mark the corresponding pages in
your submission for each homework problem on Gradescope. Conciseness counts!
(1) (Augmenting a matching) (50 points) For an undirected graph G = (V, E), let M be
a matching, P be an augmenting path for M, and consider the augmentation Mf = M ⊕ P.
(Note: Recall that operation ‘⊕’ denotes the symmetric difference between two sets:
namely, A ⊕ B := (A−B) ∪ (B−A).)
(a) (30 points) Prove that the augmentation Mf is also a matching.
(b) (20 points) Prove that the augmented matching Mf has size |Mf| = |M| + 1.
(2) (Path and cycle cover) (50 points) Given a directed graph G = (V, E), a path and cycle
cover of G is an edge subset C ⊆ E such that the subgraph (V, C) consists of vertex-disjoint
directed paths and directed cycles. In other words, in C, every vertex has both in-degree
and out-degree at most 1.
Given a directed graph G with edge weights ω, design an algorithm that finds a path
and cycle cover C of maximum total weight P
e∈C ω(e) in O(mn + n
2
log n) time, where
n and m are the number of vertices and edges of G.
(Hint: Reduce the problem of computing a maximum weight path and cycle cover to
the problem of computing a maximum weight matching in a bipartite graph.)
(Note: If graph G is acyclic, then an algorithm for path and cycle cover will find an
optimal covering of G by disjoint paths.)
