skip to main content


Title: New Approximation Algorithms for Minimum Weighted Edge Cover
We describe two new 3/2-approximation algorithms and a new 2-approximation algorithm for the minimum weight edge cover problem in graphs. We show that one of the 3/2-approximation 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/2-approximation algorithms on serial computers. Many of these algorithms can be extended to solve the 6-Edge cover problem as well. We show the relation of these algorithms to the K-Nearest Neighbor graph construction in semi-supervised learning and other applications.  more » « less
Award ID(s):
1637534
NSF-PAR ID:
10109986
Author(s) / Creator(s):
Date Published:
Journal Name:
2018 Proceedings of the Eighth SIAM Workshop on Combinatorial Scientific Computing
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We describe a paradigm for designing parallel algorithms via approximation, and illustrate it on the b-edgecover problem. A b-edgecover 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 worst-case 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 b-edgecover to that of finding a b'-matching, by exploiting the relationship between these subgraphs in an approximation context. The LSE-NW 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 LSE-NW algorithms compute the same b-edgecover 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 LSE-NW on shared memory multi-core 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 b-Suitor algorithms when edge weights are random. 
    more » « less
  2. We describe a 3/2-approximation algorithm, \lse, for computing a b-edgecover of minimum weight in a graph with weights on the edges. The b-edgecover problem is a generalization of the better-known 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 b-edgecover 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 b-edge 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 b-edge 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 b-edge cover and the b-matching 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
  3. We consider the maximum vertex-weighted matching problem (MVM), in which non-negative 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 edge-weighted 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 non-bipartite graphs that updates the matching along certain short paths in the graph: either augmenting paths of length at most 2k + 1 or weight-increasing paths of length at most 2k. The choice of k = 2 leads to a 2/3-approximation algorithm that computes nearly optimal weights fast. This algorithm could be initialized with a 2/3-approximate maximum cardinality matching to reduce its runtime in practice. A 1/2-approximation algorithm may be obtained using k = 1, which is faster than the 2/3-approximation algorithm but it computes lower weights. The 2/3-approximation algorithm has time complexity O(Δ2m) while the time complexity of the 1/2-approximation 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/2-approximation algorithm runs faster than the Suitor algorithm (currently the fastest 1/2-approximation algorithm) while the 2/3-approximation 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 well-suited for parallel implementation since they can process vertices to match in any order. The 1/2- and 2/3-approximation 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 live-lock free. 
    more » « less
  4. 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) non-adaptive queries. This improves over the best-known 2-approximation 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/2-approximation lower bound for stochastic graphs whose edges realizations demonstrate mild correlations. 
    more » « less
  5. We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This family includes variations of min sum set cover, several scheduling and search problems, and problems in Boolean function evaluation. We define a new problem, called the min sum ordering problem (MSOP), which generalizes all these problems using a cost and a weight function defined on subsets of a finite set. Assuming a polynomial time α-approximation algorithm for the problem of finding a subset whose ratio of weight to cost is maximal, we show that under very minimal assumptions, there is a polynomial time [Formula: see text]-approximation algorithm for MSOP. This approximation result generalizes a proof technique used for several distinct problems in the literature. We apply this to obtain a number of new approximation results. Summary of Contribution: This paper provides a general framework for min sum ordering problems. Within the realm of theoretical computer science, these problems include min sum set cover and its generalizations, as well as problems in Boolean function evaluation. On the operations research side, they include problems in search theory and scheduling. We present and analyze a very general algorithm for these problems, unifying several previous results on various min sum ordering problems and resulting in new constant factor guarantees for others. 
    more » « less