Approximation algorithms for the <i>L</i>-distance vertex cover problem

概要

論文の詳細を見る
Given a graph G and an integer L ≧ 0, an L-distance vertex cover (L-VC) is a set U of vertices such that each edge can be reached from some vertex in U via at most L edges. The L-distance vertex cover problem asks to find an L-VC of the minimum size. This problem generalizes the well-known Vertex Cover problem with L = 0 and is known to be NP-hard for any fixed L. This paper proposes centralized and distributed approximation algorithm with guarantees Δ(Δ-1) L-1 / 2 for odd L ≧ 1 and 2Δ(Δ-1) L / 2-1 for even L ≧ 2 (or 2 for L = 0) respectively, where Δ is the maximum degree of vertices. The running time of the centralized version is O(m+n), where m and n are the number of edges and the number of vertices respectively. On the other hand, the distributed version requires O(L(ΔL+1 + log* n)) rounds (respectively O(L(ΔL+2 + log* n)) rounds) for odd L (even L), where log* n is the iterated logarithm of n.
2012-09-27