A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs

摘要

Given a weighted planar bipartite graph G(A∪B, E) where each edge has a positive integer edge cost, we give an O(n~(4/3) log n C) time algorithm to compute minimum-cost perfect matching; here C is the maximum edge cost in the graph. The previous best known planarity exploiting algorithm has a running time of O(n~(3/2) log n) and is achieved by using planar separators (Lipton and Tarjan '80). Our algorithm is based on the bit-scaling paradigm (Gabow and Tarjan '89). For each scale, our algorithm first executes O(n~(1/3)) iterations of Gabow and Tarjan's algorithm in O(n~(4/3)) time leaving only O(n~(2/3)) vertices unmatched. Next, it constructs a compressed residual graph H with O(n~(2/3)) vertices and O(n) edges. This is achieved by using an r-division of the planar graph G with r = n~(2/3). For each partition of the r-division, there is an edge between two vertices of H if and only if they are connected by a directed path inside the partition. Using existing efficient shortest-path data structures, the remaining O(n~(2/3)) vertices are matched by iteratively computing a minimum-cost augmenting path each taking O(n~(2/3)) time. Augmentation changes the residual graph, so the algorithm updates the compressed representation for each affected partition in O(n~(2/3)) time. We bound the total number of affected partitions over all the augmenting paths by O(n~(2/3) log n). Therefore, the total time taken by the algorithm is O(n~(4/3)).