On approximating maximum covering cycles in undirected graphs

摘要

We consider the problem to find a cycle in an undirected graph such that a maximum number of nodes is in the cycle or adjacent to a node in the cycle. The problem is known to be NP-hard and we strengthen this result by showing that there is no constant factor approximation algorithm unless P=NP.