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
A new 3/2approximation algorithm for the bedge cover problem
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
 Award ID(s):
 1637534
 NSFPAR ID:
 10039355
 Date Published:
 Journal Name:
 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing
 Page Range / eLocation ID:
 5261
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


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

We describe two new 3/2approximation algorithms and a new 2approximation algorithm for the minimum weight edge cover problem in graphs. We show that one of the 3/2approximation algorithms, the Dual cover algorithm, computes the lowest weight edge cover relative to previously known algorithms as well as the new algorithms reported here. The Dual cover algorithm can also be implemented to be faster than the other 3/2approximation algorithms on serial computers. Many of these algorithms can be extended to solve the 6Edge cover problem as well. We show the relation of these algorithms to the KNearest Neighbor graph construction in semisupervised learning and other applications.more » « less

We study the stochastic vertex cover problem. In this problem, G = (V, E) is an arbitrary known graph, and G⋆ is an unknown random subgraph of G where each edge e is realized independently with probability p. Edges of G⋆ can only be verified using edge queries. The goal in this problem is to find a minimum vertex cover of G⋆ using a small number of queries. Our main result is designing an algorithm that returns a vertex cover of G⋆ with size at most (3/2+є) times the expected size of the minimum vertex cover, using only O(n/є p) nonadaptive queries. This improves over the bestknown 2approximation algorithm by Behnezhad, Blum and Derakhshan [SODA’22] who also show that Ω(n/p) queries are necessary to achieve any constant approximation. Our guarantees also extend to instances where edge realizations are not fully independent. We complement this upperbound with a tight 3/2approximation lower bound for stochastic graphs whose edges realizations demonstrate mild correlations.more » « less

We consider the Max3Section problem, where we are given an undirected graph G = (V, E) equipped with nonnegative edge weights w : E → R+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max3Section is closely related to other wellstudied graph partitioning problems, e.g., MaxCut, Max3Cut, and MaxBisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max3Section much harder to cope with compared to, e.g., MaxBisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result.more » « less