Experimental Analysis of Approximation Algorithms for the Vertex Cover and Set Covering Problems

Several approximation algorithms with proven performance guarantees have been proposed to find approximate solutions to classical combinatorial optimization problems. However, theoretical results may not reflect the experimental performance of the proposed algorithms. As a consequence, a question arises: how “far” from the theoretically proved performance are the experimental results? We conduct a controlled empirical study of approximation algorithms for the Vertex Cover and the Set Covering Problems. Many authors have proposed approximation algorithms for those problems. Our main goal is to better understand their strengths, weaknesses, and operation. Although we implement more than one algorithm to find feasible solutions to either problems, this work does not emphasize competition between them. The quality of the solutions related to the theoretical performance guarantees are analyzed instead. The computational experiments showed that the proven performance guarantees of all tested algorithms did not forecast well the empirical performance.     

Implicit branching and parameterized partial cover problems

Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well-known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems has been intensively studied in planar graphs and in graphs excluding a fixed graph H as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems.     

Subexponential algorithms for partial cover problems

Partial Cover problems are optimization versions of fundamental and well-studied problems like Vertex Cover and Dominating Set. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number k of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by k. It was recently shown by Amini et al. (2008) [1] that Partial Vertex Cover and Partial Dominating Set are fixed parameter tractable on large classes of sparse graphs, namely H-minor-free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time ²O(k)nO(1).During the last decade there has been an extensive study on parameterized subexponential algorithms. In particular, it was shown that the classical Vertex Cover and Dominating Set problems can be solved in subexponential time on H-minor-free graphs. The techniques developed to obtain subexponential algorithms for classical problems do not apply to partial cover problems. It was left as an open problem by Amini et al. (2008) [1] whether there is a subexponential algorithm for Partial Vertex Cover and Partial Dominating Set. In this paper, we answer the question affirmatively by solving both problems in time not only on planar graphs but also on much larger classes of graphs, namely, apex-minor-free graphs. Compared to previously known algorithms for these problems our algorithms are significantly faster and simpler.     

一类弱集合覆盖问题的近似算法

在近似算法领域,集合覆盖（Set Cover）是研究的比较早和比较透彻的问题之一．该文提出了一类与集合覆盖很相似的问题：集合击中和弱集合b-覆盖,并且给出了解决它们的近似算法,还证明了它们的不可近似性．     

Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

A sequence of exact algorithms to solve the Vertex Cover and Maximum Independent Set problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194^kk² + n) for the parameterized Vertex Cover problem on degree-3 graphs, and a simple algorithm of running time O(1.1255ⁿ) for the Maximum Independent Set problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.     

支配问题的研究进展

复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT)。利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法。文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面。     

Distributed algorithms for covering, packing and maximum weighted matching

This paper gives poly-logarithmic-round, distributed δ-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio δ is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with δ = 2). Via duality, the paper also gives poly-logarithmic-round, distributed δ-approximation algorithms for Fractional Packing linear programs (where δ is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where δ is the maximum size of any of the hyperedges; for graphs δ = 2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms.     

Randomized approximation of bounded multicovering problems

The problem of finding approximate solutions for a subclass of multicovering problems denoted byILP(k, b) is considered. The problem involves findingx∈{0,1} ⁿ that minimizes ∑ _j x _j subject to the constraintAx≥b, whereA is a 0–1m×n matrix with at mostk ones per row,b is an integer vector, andb is the smallest entry inb. This subclass includes, for example, the Bounded Set Cover problem whenb=1, and the Vertex Cover problem whenk=2 andb=1. An approximation ratio ofk−b+1 is achievable by known deterministic algorithms. A new randomized approximation algorithm is presented, with an approximation ratio of (k−b+1)(1−(c/m)^1/(k−b+1)) for a small constantc>0. The analysis of this algorithm relies on the use of a new bound on the sum of independent Bernoulli random variables, that is of interest in its own right. The first author was supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Israeli Science Foundation. This work was done white the third author was at the Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel.     

A generalization of Nemhauser and Trotter?s local optimization theorem

The Nemhauser–Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotter?s result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser–Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away “easy parts” of the input instance, finally leaving a “hard core” whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d?0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser–Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d?1 and, for any ?>0, an O(k1+?)-vertex problem kernel for d?2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.     

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

Abstract. There is an error in our paper ``An Approximation Algorithm for Minimum-Cost Vertex- Connectivity Problems' (Algorithmica (1997), 18:21—43). In that paper we considered the following problem: given an undirected graph and values r _ij for each pair of vertices i and j , find a minimum-cost set of edges such that there are r _ij vertex-disjoint paths between vertices i and j . We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal—dual approach which has led to approximation algorithms for many edge-connectivity problems. The algorithms work in a series of stages; in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r _ij = k for all i,j , we described a polynomial-time algorithm that claimed to output a solution of cost no more than 2 H (k) times optimal, where H = 1 + 1/2 + · · · + 1/n . This result is erroneous. We describe an example where our primal—dual augmentation subroutine, when augmenting a k -vertex connected graph to a (k+1) -vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum. In the case r _ij ∈ {0,1,2} for all i,j , we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k -vertex connected case does hold, and that the algorithm performs as claimed.     

Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2 ^m l ^O(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2 ⁿ n ^O(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732 ⁿ ) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.     

Approximation preserving reductions for set covering,vertex covering and independent set hierarchies under differential approximationa

The notion of approximability preserving reductions between different problems deserves special attention in approximability theory. These kinds of reductions allow us polynomial time conversion of some already known ‘good’ approximation algorithms for some NP-hard problems into ones for some other NP-hard problems. In this context, we consider reductions for set covering and vertex covering hierarchies. Our results are then extended to hitting set and independent set hierarchies. Here, we adopt the differential approximation ratio that has the natural property to be stable under affine transformations of the objective function of a problem.     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

Linear kernelizations for restricted 3-Hitting Set problems

In this paper, we study the 3-Hitting Set problem, also called the Vertex Cover problem on 3-uniform hypergraphs. We provide linear kernelizations for this problem and its dual problem in three types of 3-uniform hypergraphs. Moreover, we obtain lower bounds on the kernel size for them by the parametric duality technique.     

Parameterized algorithm for eternal vertex cover

In this paper we initiate the study of a “dynamic” variant of the classical Vertex Cover problem, the Eternal Vertex Cover problem introduced by Klostermeyer and Mynhardt, from the perspective of parameterized algorithms. This problem consists in placing a minimum number of guards on the vertices of a graph such that these guards can protect the graph from any sequence of attacks on its edges. In response to an attack, each guard is allowed either to stay in his vertex, or to move to a neighboring vertex. However, at least one guard has to fix the attacked edge by moving along it. The other guards may move to reconfigure and prepare for the next attack. Thus at every step the vertices occupied by guards form a vertex cover. We show that the problem admits a kernel of size k⁴(k+1)+2k, which shows that the problem is fixed parameter tractable when parameterized by the number of available guards k. Finally, we also provide an algorithm with running time O(²O(k²)+nm) for Eternal Vertex Cover, where n is the number of vertices and m the number of edges of the input graph. In passing we also observe that Eternal Vertex Cover is NP-hard, yet it has a polynomial time 2-approximation algorithm.     

Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost

This paper describes a simple greedy Δ-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most Δ variables of the problem. (A simple example is Vertex Cover, with Δ=2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems.     

Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover

We present a new method of solving graph problems related to Vertex Cover by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the Vertex Cover problem. In the case of Connected Vertex Cover, we take the upper bound from O ^*(6 ^k ) to O ^*(2.7606 ^k ) without large hidden factors. For Tree Cover, we show a complexity of O ^*(3.2361 ^k ), improving over the previous bound of O ^*((2k) ^k ). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated. Supported by the DFG under grant RO 927/6-1 (TAPI).     

Approximation algorithms for terrain guarding

We present approximation algorithms and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications in telecommunications, namely in the setting up of antenna networks for wireless communication. Our approximation algorithms transform the terrain guarding instance into a Minimum Set Cover instance, which is then solved by the standard greedy approximation algorithm [J. Comput. System Sci. 9 (1974) 256-278]. The approximation algorithms achieve approximation ratios of O(logn), where n is the number of vertices in the input terrain. We also briefly discuss some heuristic approaches for solving other variations of terrain guarding problems, for which no approximation algorithms are known. These heuristic approaches do not guarantee non-trivial approximation ratios but may still yield good solutions.     

Set multi-covering via inclusion–exclusion

Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion–exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O^*((2t)ⁿ) time and O^*((t+1)ⁿ) space where t is the maximum value in the coverage requirement set (The O^*(f(n)) notation omits a polylog(f(n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion–exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)].     

Exponential-time approximation of weighted set cover

The Set Cover problem belongs to a group of hard problems which are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. In recent years, many researchers design exact exponential-time algorithms for problems of that kind. The goal is getting the time complexity still of order O(cn), but with the constant c as small as possible. In this work we extend this line of research and we investigate whether the constant c can be made even smaller when one allows constant factor approximation.In fact, we describe a kind of approximation schemes—trade-offs between approximation factor and the time complexity. We use general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate r, one can transform any O^∗(cn)-time¹ algorithm for Set Cover into a (1+lnr)-approximation algorithm running in time O^∗(cn/r). We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems.