Parameterized Complexity of Vertex Cover Variants

Important variants of theVERTEX COVER problem (among others, CONNECTED VERTEX COVER, CAPACITATED VERTEX COVER, and MAXIMUM PARTIAL VERTEX COVER) have been intensively studied in terms of polynomial-time approximability. By way of contrast, their parameterized complexity has so far been completely open. We close this gap here by showing that, with the size of the desired vertex cover as the parameter, CONNECTED VERTEX COVER and CAPACITATED VERTEX COVER are both fixed-parameter tractable while MAXIMUM PARTIAL VERTEX COVER is W[1]-complete. This answers two open questions from the literature. The results extend to several closely related problems. Interestingly, although the considered variants of VERTEX COVER behave very similar in terms of constant factor approximability, they display a wide range of different characteristics when investigating their parameterized complexities.     

Vertex Cover Problem Parameterized Above and Below Tight Bounds

We study the well-known Vertex Cover problem parameterized above and below tight bounds. We show that two of the parameterizations (both were suggested by Mahajan et al. in J. Comput. Syst. Sci. 75(2):137–153, 2009) are fixed-parameter tractable and two other parameterizations are W[1]-hard (one of them is, in fact, W[2]-hard).     

随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.     

Vertex Cover Kernelization Revisited

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G′,k′) in polynomial time with the guarantee that G′ has at most 2k′ vertices (and thus $\mathcal{O}((k')^{2})$ edges) with k′≤k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Θ(k ²) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number $\mathop{\mathrm{\mbox {\textsc{vc}}}}(G)$ since $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)\leq\mathop{\mathrm{\mbox{\textsc{vc}}}}(G)$ and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ : an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G′,X′,k′) such that |V(G′)|≤2k and $|V(G')| \in\mathcal{O}(|X'|^{3})$ . A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have a polynomial kernel when parameterized by the cardinality of a given vertex cover of the graph unless NP ? coNP/poly and the polynomial hierarchy collapses to the third level.     

Crown Structures for Vertex Cover Kernelization

Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are studied and compared both theoretically and experimentally with each other and with older, more primitive kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crown-free subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time.     

Private Approximation of Clustering and Vertex Cover

Private approximation of search problems deals with finding approximate solutions to search problems while disclosing as little information as possible. The focus of this work is on private approximation of the vertex cover problem and two well studied clustering problems – k-center and k-median. Vertex cover was considered in (Beimel, Carmi, Nissim, and Weinreb, STOC, 2006) and we improve their infeasibility results. Clustering algorithms are frequently applied to sensitive data, and hence are of interest in the contexts of secure computation and private approximation. We show that these problems do not admit private approximations, or even approximation algorithms that are allowed to leak a significant number of bits of information. For the vertex cover problem we show a tight infeasibility result: every algorithm that ρ(n)-approximates vertex-cover must leak Ω(n/ρ(n)) bits (where n is the number of vertices in the graph). For the clustering problems we prove that even approximation algorithms with a poor approximation ratio must leak Ω(n) bits (where n is the number of points in the instance). For these results we develop new proof techniques, which are simpler and more intuitive than those in Beimel et al., and yet allow for stronger infeasibility results. Our proofs rely on the hardness of the promise problem where a unique optimal solution exists (Valiant and Vazirani, Theoretical Computer Science, 1986), on the hardness of approximating witnesses for NP-hard problems (Kumar and Sivakumar, CCC, (1999) and Feige, Langberg, and Nissim, APPROX, (2000)), and on a simple random embedding of instances into bigger instances.     

最小顶点覆盖快速降阶算法

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.     

Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem

In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We consider two different measures for the problem. The first measure is a very natural multi-objective one for the use of evolutionary algorithms and takes into account the number of chosen vertices and the number of edges that remain uncovered. The second fitness function is based on a linear programming formulation and proves to give better results. We point out that both approaches lead to a kernelization for the Vertex Cover problem. Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e., the expected runtime is bounded by O(f(OPT)?n ^c ), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem.     

顶点覆盖问题线性内核算法

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).     

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).     

Cutting Planes and the Parameter Cutwidth

We introduce the parameter cutwidth for the Cutting Planes (CP) system of Gomory and Chvátal. We provide linear lower bounds on cutwidth for two simple polytopes. Considering CP as a propositional refutation system, one can see that the cutwidth of a CNF contradiction F is always bound above by the Resolution width of F. We provide an example proving that the converse fails: there is an F which has constant cutwidth, but has Resolution width Ω(n). Following a standard method for converting an FO sentence ψ, without finite models, into a sequence of CNFs, F _ψ,n , we provide a classification theorem for CP based on the sum cutwidth plus rank. Specifically, the cutwidth + rank of F _ψ,n is bound by a constant c (depending on ψ only) iff ψ has no (infinite) models. This result may be seen as a relative of various gap theorems extant in the literature.     

Small Vertex Cover makes Petri Net Coverability and Boundedness Easier

The coverability and boundedness problems for Petri nets are known to be Expspace-complete. Given a Petri net, we associate a graph with it. With the vertex cover number k of this graph and the maximum arc weight W as parameters, we show that coverability and boundedness are in ParaPspace. This means that these problems can be solved in space $\mathcal{O} ({\mathit{ef}}(k, W){\mathit{poly}}(n) )$ , where ef(k,W) is some super-polynomial function and poly(n) is some polynomial in the size of the input n. We then extend the ParaPspace result to model checking a logic that can express some generalizations of coverability and boundedness.     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1．1033^n),参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。     

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

We study the partial vertex cover problem. Given a graph G=(V,E), a weight function w:V→R ⁺, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. We provide a primal-dual 2-approximation algorithm which runs in O(nlog n+m) time. This represents an improvement in running time from the previously known fastest algorithm. Our technique can also be used to get a 2-approximation for a more general version of the problem. In the partial capacitated vertex cover problem each vertex u comes with a capacity k _u . A solution consists of a function x:V→ℕ₀ and an orientation of all but s edges, such that the number of edges oriented toward vertex u is at most x _u k _u . Our objective is to find a cover that minimizes ∑ _v∈V x _v w _v . This is the first 2-approximation for the problem and also runs in O(nlog n+m) time. Research supported by NSF Awards CCR 0113192 and CCF 0430650, and the University of Maryland Dean’s Dissertation Fellowship.     

Variable Formulation Search for the Cutwidth Minimization Problem

Many optimization problems are formulated as min–max problems where the objective function consist of minimizing a maximum value. In this case, it is usual that many solutions of the problem has associated the same value of the objective function. When this happens it is difficult to determine which solution is more promising to continue the search. In this paper we propose a new variant of the Variable Neighbourhood Search methodology to tackle this kind of problems. The new variant, named Variable Formulation Search, makes use of alternative formulations of the problem to determine which solution is more promising when they have the same value of the objective function in the original formulation. We do that in shaking, local search and neighbourhood change steps of the basic Variable Neighbourhood Search. We apply the new methodology to the Cutwidth Minimization Problem. Computational results show that our proposal outperforms previous algorithms in the state of the art in terms of quality and computing time.