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.