As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as each edge insertion deletion is observed, is an attractive one. However, few results are known for optimization problems over such dynamic graph streams. In this paper, we introduce a new approach to handling graph streams, by instead seeking solutions for the parameterized versions of these problems where we are given a parameter @math and the objective is to decide whether there is a solution bounded by @math . By combining kernelization techniques with randomized sketch structures, we obtain the first streaming algorithms for the parameterized versions of the Vertex Cover problem. We consider the following three models for a graph stream on @math nodes: 1. The insertion-only model where the edges can only be added. 2. The dynamic model where edges can be both inserted and deleted. 3. The dynamic model where we are guaranteed that at each timestamp there is a solution of size at most @math . In each of these three models we are able to design parameterized streaming algorithms for the Vertex Cover problem. We are also able to show matching lower bound for the space complexity of our algorithms. (Due to the arXiv limit of 1920 characters for abstract field, please see the abstract in the paper for detailed description of our results)
Subsequent work has extended to the case of weighted edges (when a maximum weight matching is sought), and reducing the number of passes to provide a guaranteed approximation @cite_32 @cite_24 . While approximating the size of the vertex cover has been studied in other sublinear models, such as sampling @cite_15 @cite_1 , we are not aware of prior work that has addressed the question of finding a vertex cover over a graph stream. Likewise, parameterized complexity has not been explicitly studied in the streaming model, so we initiate it here.
@cite_24 @cite_15 @cite_1 @cite_32
2055000959 1572977974 2034543148 2156896570
In this article, we consider the problem of computing a minimum-weight vertex-cover in an n-node, weighted, undirected graph G e (V,E). We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. Our algorithm runs in an expected number of O(log n + log W) communication rounds, where W is the average vertex-weight. The previous best algorithm for this problem requires O(log n(log n + logW)) rounds and it is not fully distributed. For a maximal matching M in G, it is a well-known fact that any vertex-cover in G needs to have at least vMv vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting. A local-ratio theorem for approximating the weighted vertex cover problem is presented. It consists of reducing the weights of vertices in certain subgraphs and has the effect of local-approximation. Putting together the Nemhauser-Trotter local optimization algorithm and the local-ratio theorem yields several new approximation techniques which improve known results from time complexity, simplicity and performance-ratio point of view. The main approximation algorithm guarantees a ratio of where K is the smallest integer s.t. † This is an improvement over the currently known ratios, especially for a “practical” number of vertices (e.g. for graphs which have less than 2400, 60000, 10 12 vertices the ratio is bounded by 1.75, 1.8, 1.9 respectively). Given a graph G=(V,E), a weight function w: E?R+, and a parameter k, we consider the problem of finding a subset U?V of size k that maximizes:Max-Vertex Coverk: the weight of edges incident with vertices in U,Max-Dense Subgraphk: the weight of edges in the subgraph induced by U,Max-Cutk: the weight of edges cut by the partition (U,V ),Max-Uncutk: the weight of edges not cut by the partition (U,V ).For each of the above problems we present approximation algorithms based on semidefinite programming and obtain approximation ratios better than those previously published. In particular we show that if a graph has a vertex cover of size k, then one can select in polynomial time a set of k vertices that covers over 80 of the edges. 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.