Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover

摘要

In the Maximum Subset Matching problem, which generalizes the maximum matching problem, we are given a graph G = (V, E) and S is contained in V. The goal is to determine the maximum number of vertices of S that can be matched in a matching of G. Our first result is a new randomized algorithm for the Maximum Subset Matching problem that improves upon the fastest known algorithms for this problem. Our algorithm runs in O(ms~((ω-1)/2)) time if m ≥ s~((ω+1)/2) and in O(s~ω) time if m < s~((ω+1)/2), where ω < 2.376 is the matrix multiplication exponent, m is the number of edges from S to VS, and s = |S|. The algorithm is based, in part, on a method for computing the rank of sparse rectangular integer matrices. Our second result is a new algorithm for the All-Pairs Shortest Paths (APSP) problem. Given an undirected graph with n vertices, and with integer weights from {1,…,W} assigned to its edges, we present an algorithm that solves the APSP problem in O(Wn~(ω(1,1,μ)) time where n~μ = vc(G) is the vertex cover number of G and ω(1,1,μ) is the time needed to compute the Boolean product of an n × n matrix with an n×n~μ matrix. Already for the unweighted case this improves upon the previous O(n~(2+μ)) and O(n~ω) time algorithms for this problem. In particular, if a graph has a vertex cover of size O(n~(0.29)) then APSP in unweighted graphs can be solved in asymptotically optimal O(n~2) time, and otherwise it can be solved in O(n~(1.844) uc(G)~(0.533)) time. The common feature of both results is their use of algorithms developed in recent years for fast (sparse) rectangular matrix multiplication.