DescriptionWe study the problem of finding the minimum vertex cover for a graph in the sliding window model. The sliding window model is similar to the original streaming model where the edges of a graph whose vertices are known, arrive sequentially in a stream. However, in the sliding window model, only the graph induced by recent w edges of the stream is considered in computing the output. Therefore, when a new edge is arrived, the oldest edge would be deleted from the graph and not considered anymore in the computation of the output. Since we are only allowed to use o(w) space, all the recent w edges of the stream cannot be stored and we cannot explicitly find the edge that is getting deleted. This implicit deletion makes the sliding window model harder when compared to the original streaming model.
In this work, we observe that the (3 + ε)-approximation algorithm (ε ∈ (0, 1)) for maximum matching in the sliding window model can give a (6+O(ε))-approximation for the minimum vertex cover problem in the sliding window model. We give a counter example to the existing analysis of a (4 + ε)-approximation algorithm for the minimum vertex cover problem in the sliding window model and provide a correct analysis for the same algorithm. Finally, we come up with a (3 + ε)-approximation algorithm for the minimum vertex cover problem in the sliding window model using ̃O(n) space, where ∼ encompasses 1/ε,logn factors with n being the number of vertices in the graph.