It is a simple fact that cubic Hamiltonian graphs have at least two Hamiltonian cycles. Finding such a cycle is NP-hard in general, and no polynomial time algorithm is known for the problem of finding a second Hamiltonian cycle when one such cycle is given as part of the input. We investigate the ocmplexity of approximatingthis problem where by a feasible osultio we mean a(nother) cycle in the graph. First we prove a negative result showin that the LONGEST PATH problem is not constant approximable in cubic Hamiltonian graphs unless P=NP. No such negative result was previously known for this problem in Hamiltonian graphs. In strong opposition with this result we show that there is polynomial time approximation scheme for finding another cycle in cubic Hamiltonian graphs if a Hamiltonian cycle is given in the input.
展开▼
