Inverse HAMILTONIAN CYCLE and inverse 3DIMENSIONAL MATCHING are coNP-complete
In this paper, we show that the inverse problems of HAMILTONIAN CYCLE and 3DIMENSIONAL MATCHING are coNP-complete. This completes the study of inverse problems of the six natural NP-complete problems from Garey and Johnson (1979) [2] and answers an open question from Chen (2003) [1]. We show that the coNP-completeness of the inverse problem of HAMILTONIAN CYCLE holds for undirected as well as for directed graphs. (C) 2012 Published by Elsevier B.V.
hamiltonian cycle 3dimensional matching conp-completeness inverse problems computational complexity