Consider the problem of cycle covering: Given a graph G, we look for a set C of cycles such that all vertex of V(G) are in at least one cycle of C and the number of cycles in C is minimum.
My task is to show that this problem does not admit an absolute approximation, i.e., there cannot be an algorithm H such that for all instances I of the problem, H(I) <= OPT(I) + k, where OPT(I) is the optimal value for I and k is a number greater or equal to 1. The usual technique is to show that if this algorithm existed, we could solve in polinomial time some NP-hard problem.
Does anyone know which problem could be used for that?
Suppose there is an algorithm H such that there is a positive integer k such that for every graph G, H(G)<=OPT(G)+k holds, where OPT(G) denotes the minimum number of cycles necessary to cover all nodes of G and the runtime of H is polynomially bounded in n, where n is the number of nodes of G.
Given any graph G, create a graph G' which consists out of k+1 isomorphic copies of G; note that the number of nodes in G' is (k+1)n, which is polynomially bounded in n. The following two cases can occur:
If G contains a Hamiltonian cycle, then OPT(G')=k+1 and H(G')<=OPT(G')+k=k+1+k=2k+1.
If G does not contain a Hamiltonian cycle, then OPT(G')>=2k+2>2k+1 hence H(G')>2k+1.
In total, H can be used to decide in a runtime bound ponlynomially bounded in n whether G contains a Hamiltonian cycle; however, as the decision whether G has a Hamiltonian cycle is an NP-complete decision problem, this is impossible unless P=NP holds.
Note: This approach is called 'gap creation', as instances are transformed in such a way that there is a gap in the objective value of