We consider the communication complexity of finding an approximate maximum matching in a graph in a multi-party message-passing communication model. The maximum matching problem is one of the most fundamental graph combinatorial problems, with a variety of applications. The input to the problem is a graph @math that has @math vertices and the set of edges partitioned over @math sites, and an approximation ratio parameter @math . The output is required to be a matching in @math that has to be reported by one of the sites, whose size is at least factor @math of the size of a maximum matching in @math . We show that the communication complexity of this problem is @math information bits. This bound is shown to be tight up to a @math factor, by constructing an algorithm, establishing its correctness, and an upper bound on the communication cost. The lower bound also applies to other graph combinatorial problems in the message-passing communication model, including max-flow and graph sparsification.
In @cite_29 , the maximum matching was presented as one of open problems in the streaming computation model. Many results have been established since then by various authors @cite_22 , @cite_35 , @cite_36 , @cite_28 , @cite_17 , @cite_23 , @cite_25 , @cite_3 , @cite_7 , @cite_8 , and @cite_19 . Many of the studies were concerned with a streaming computation model that allows for @math space; referred to as the semi-streaming computation model. The algorithms developed for the semi-streaming computation model can be directly applied to obtain a constant-factor approximation of maximum matching in a graph in the message-passing model that has a communication cost of @math bits.
@cite_35 @cite_22 @cite_7 @cite_8 @cite_36 @cite_28 @cite_29 @cite_3 @cite_19 @cite_23 @cite_25 @cite_17
1967311985 1629950647 2950256099 2762990162
In this paper we study linear-programming based approaches to the maximum matching problem in the semi-streaming model. In this model edges are presented sequentially, possibly in an adversarial order, and we are only allowed to use a small space. The allowed space is near linear in the number of vertices (and sublinear in the number of edges) of the input graph. The semi-streaming model is relevant in the context of processing of very large graphs. In recent years, there have been several new and exciting results in the semi-streaming model. However broad techniques such as linear programming have not been adapted to this model. In this paper we present several techniques to adapt and optimize linear-programming based approaches in the semi-streaming model. We use the maximum matching problem as a foil to demonstrate the effectiveness of adapting such tools in this model. As a consequence we improve almost all previous results on the semi-streaming maximum matching problem. We also prove new results on interesting variants. In this paper, we study the non-bipartite maximum matching problem in the semi-streaming model. The maximum matching problem in the semi-streaming model has received a significant amount of attention lately. While the problem has been somewhat well solved for bipartite graphs, the known algorithms for non-bipartite graphs use @math passes or @math time to compute a @math approximation. In this paper we provide the first FPTAS (polynomial in @math ) for the problem which is efficient in both the running time and the number of passes. We also show that we can estimate the size of the matching in @math passes using slightly superlinear space. To achieve both results, we use the structural properties of the matching polytope such as the laminarity of the tight sets and total dual integrality. The algorithms are iterative, and are based on the fractional packing and covering framework. However the formulations herein require exponentially many variables or constraints. We use laminarity, metric embeddings and graph sparsification to reduce the space required by the algorithms in between and across the iterations. This is the first use of these ideas in the semi-streaming model to solve a combinatorial optimization problem. We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass @math -approximation streaming algorithm can be easily obtained with space @math , where @math denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space @math is granted, for every @math . Specifically, for every @math , we show that in the one-pass turnstile streaming model, in order to compute a @math -approximation, space @math is required for constant error randomized algorithms, and, up to logarithmic factors, space @math is sufficient. Our lower bound result is proved in the simultaneous message model of communication and may be of independent interest. We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke [Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008, pp. 669–680] by devising a deterministic approach whose performance guarantee is 4.91+e. In addition, we study preemptive online algorithms, a class of algorithms related to one-pass semi-streaming algorithms, where we are allowed to maintain only a feasible matching in memory at any point in time. We provide a lower bound of 4.967 on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges that is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms.