We describe a 3/2approximation algorithm, \lse, for computing a bedgecover
of minimum weight in a graph with weights on the edges.
The bedgecover problem is a generalization of the betterknown Edge Cover problem in graphs,
where the objective is to choose a subset C of edges in the graph such that
at least a specified number b(v) of edges in C are incident on each vertex v.
In the weighted bedgecover problem, we minimize the sum of the weights of the edges in C.
We prove that the Locally Subdominant edge (LSE) algorithm computes the same bedge cover as the one obtained by the Greedy algorithm for the problem.
However, the Greedy algorithm requires edges to be sorted
by their effective weights, and these weights need to be updated after each iteration.
These requirements make the Greedy algorithm sequential and impractical for massive graphs.
The LSE algorithm avoids the sorting step, and is amenable for parallelization.
We implement the algorithm on a serial machine and compare its performance against a
collection of approximation algorithms for the bedge cover problem.
Our results show that the algorithm is 3 to 5 times faster than the
Greedy algorithm on a serial processor.
The approximate edge covers obtained by the LSE algorithm have weights
greater by at most 17% of the optimal weight for problems where
we could compute the latter.
We also investigate the relationship between the bedge cover and the bmatching problems,
show that the latter has a faster implementation since edge weights are static in this
algorithm, and obtain a heuristic solution for the former from the latter.
more »
« less
A Parallel 2/3Approximation Algorithm for VertexWeighted Matching
We consider the maximum vertexweighted matching problem (MVM), in which nonnegative weights are assigned to the vertices of a graph, and the weight of a matching is the sum of the weights of the matched vertices. Although exact algorithms for MVM are faster than exact algorithms for the maximum edgeweighted matching problem, there are graphs on which these exact algorithms could take hundreds of hours. For a natural number k, we design a k/(k + 1)approximation algorithm for MVM on nonbipartite graphs that updates the matching along certain short paths in the graph: either augmenting paths of length at most 2k + 1 or weightincreasing paths of length at most 2k. The choice of k = 2 leads to a 2/3approximation algorithm that computes nearly optimal weights fast. This algorithm could be initialized with a 2/3approximate maximum cardinality matching to reduce its runtime in practice. A 1/2approximation algorithm may be obtained using k = 1, which is faster than the 2/3approximation algorithm but it computes lower weights. The 2/3approximation algorithm has time complexity O(Δ2m) while the time complexity of the 1/2approximation algorithm is O(Δm), where m is the number of edges and Δ is the maximum degree of a vertex. Results from our serial implementations show that on average the 1/2approximation algorithm runs faster than the Suitor algorithm (currently the fastest 1/2approximation algorithm) while the 2/3approximation algorithm runs as fast as the Suitor algorithm but obtains higher weights for the matching.
One advantage of the proposed algorithms is that they are wellsuited for parallel implementation since they can process vertices to match in any order. The 1/2 and 2/3approximation algorithms have been implemented on a shared memory parallel computer, and both approximation algorithms obtain good speedups, while the former algorithm runs faster on average than the parallel Suitor algorithm. Care is needed to design the parallel algorithm to avoid cyclic waits, and we prove that it is livelock free.
more »
« less
 Award ID(s):
 1637534
 NSFPAR ID:
 10181551
 Date Published:
 Journal Name:
 SIAM 2020 Workshop on Combinatorial Scientific Computing
 Page Range / eLocation ID:
 1221
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r} + wr/n)) time. When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the wellknown HopcroftKarp (HK) algorithm, which runs in O(m sqrt{n}) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sublinear in n and wr=O(n^{gamma}) for gamma < 3/2, then we can compute maximum cardinality matching in G in o(m sqrt{n}) time. Using our algorithm, we obtain a new O~(n^{4/3}/epsilon^4) time algorithm to compute an epsilonapproximate bottleneck matching of A,B subsetR^2 and an 1/(epsilon^{O(d)}}n^{1+(d1)/(2d1)}) poly log n time algorithm for computing epsilonapproximate bottleneck matching in ddimensions. All previous algorithms take Omega(n^{3/2}) time. Given any graph G(A cup B,E) that has an easily computable balanced vertex separator for every subgraph G'(V',E') of size V'^{delta}, for delta in [1/2,1), we can apply our algorithm to compute a maximum matching in O~(mn^{delta/1+delta}) time improving upon the O(m sqrt{n}) time taken by the HKAlgorithm.more » « less

We describe a paradigm for designing parallel algorithms via approximation, and illustrate it on the bedgecover problem. A bedgecover of minimum weight in a graph is a subset $C$ of its edges such that at least a specified number $b(v)$ of edges in $C$ is incident on each vertex $v$, and the sum of the edge weights in $C$ is minimum. The Greedy algorithm and a variant, the LSE algorithm, provide $3/2$approximation guarantees in the worstcase for this problem, but these algorithms have limited parallelism. Hence we design two new $2$approximation algorithms with greater concurrency. The MCE algorithm reduces the computation of a bedgecover to that of finding a b'matching, by exploiting the relationship between these subgraphs in an approximation context. The LSENW is derived from the LSEalgorithm using static edge weights rather than dynamically computing effective edge weights. This relaxation gives LSE a worse approximation guarantee but makes it more amenable to parallelization. We prove that both the MCE and LSENW algorithms compute the same bedgecover with at most twice the weight of the minimum weight edge cover. In practice, the $2$approximation and $3/2$approximation algorithms compute edge covers of weight within $10\%$ the optimal. We implement three of the approximation algorithms, MCE, LSE, and LSENW on shared memory multicore machines, including an Intel Xeon and an IBM Power8 machine with 8 TB memory. The MCE algorithm is the fastest of these by an order of magnitude or more. It computes an edge cover in a graph with billions of edges in $20$ seconds using two hundred threads on the IBM Power8. We also show that the parallel depth and work can be bounded for the Suitor and bSuitor algorithms when edge weights are random.more » « less

Megow, Nicole ; Smith, Adam (Ed.)Maximum weight independent set (MWIS) admits a 1/kapproximation in inductively kindependent graphs [Karhan Akcoglu et al., 2002; Ye and Borodin, 2012] and a 1/(2k)approximation in kperfectly orientable graphs [Kammer and Tholey, 2014]. These are a parameterized class of graphs that generalize kdegenerate graphs, chordal graphs, and intersection graphs of various geometric shapes such as intervals, pseudodisks, and several others [Ye and Borodin, 2012; Kammer and Tholey, 2014]. We consider a generalization of MWIS to a submodular objective. Given a graph G = (V,E) and a nonnegative submodular function f: 2^V → ℝ_+, the goal is to approximately solve max_{S ∈ ℐ_G} f(S) where ℐ_G is the set of independent sets of G. We obtain an Ω(1/k)approximation for this problem in the two mentioned graph classes. The first approach is via the multilinear relaxation framework and a simple contention resolution scheme, and this results in a randomized algorithm with approximation ratio at least 1/e(k+1). This approach also yields parallel (or lowadaptivity) approximations. Motivated by the goal of designing efficient and deterministic algorithms, we describe two other algorithms for inductively kindependent graphs that are inspired by work on streaming algorithms: a preemptive greedy algorithm and a primaldual algorithm. In addition to being simpler and faster, these algorithms, in the monotone submodular case, yield the first deterministic constant factor approximations for various special cases that have been previously considered such as intersection graphs of intervals, disks and pseudodisks.more » « less

In this paper, we generalize the recently studied stochastic matching problem to more accurately model a significant medical process, kidney exchange, and several other applications. Up until now the stochastic matching problem that has been studied was as follows: given a graph G= (V,E), each edge is included in the realized subgraph of G independently with probability pe, and the goal is to find a degreebounded subgraph Q of G that has an expected maximum matching that approximates the expected maximum matching of G. This model does not account for possibilities of vertex dropouts, which can be found in several applications, e.g. in kidney exchange when donors or patients opt out of the exchange process as well as in online freelancing and online dating when online profiles are found to be faked. Thus, we will study a more generalized model of stochastic matching in which vertices and edges are both realized independently with some probabilities pv, pe, respectively, which more accurately fits important applications than the previously studied model. We will discuss the first algorithms and analysis for this generalization of the stochastic matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least 0.6568 in unweighted graphs, and 1/2+ε in weighted graphs for some constant ε >0. We further improve our result for unweighted graphs to 2/3 using edge degree constrained subgraphs (EDCS).more » « less