A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover. converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best. In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log(2) n) time using O(Delta(2)(m + n)/log n) processors on an EREW-PRAM, while the RNC algorithm runs in O(log n) expected time using O(m + n) processors on a CRCW-PRAM, when a given graph has n vertices and in edges with maximum vertex degree of Delta. (C) 2004 Elsevier B.V. All rights reserved.