Solving NP-hard problems in 'almost trees': Vertex cover

Abstract

We present an algorithm which finds a minimum vertex cover in a graph G(V, E) in time O(|V|+( a k)2 k 3), where for connected graphs G the parameter a is defined as the minimum number of edges that must be added to a tree to produce G, and k is the maximum a over all biconnected components of the graph. The algorithm combines two main approaches for coping with NP-completeness, and thereby achieves better running time than algorithms using only one of these approaches. © 1985.