\textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete (Q418733)

The inverse problems of 3-satisfiability, vertex cover, clique and partition problems have been shown to be coNP-complete by \textit{D. Kavvadias} and \textit{M. Sideri} [SIAM J. Comput. 28, No. 1, 152--163 (1998; Zbl 0917.68079)] and \textit{H. Chen} [Lect. Notes Comput. Sci. 2747, 338--347 (2003; Zbl 1124.68368)]. In this paper it is shown that the inverse problems of Hamiltonian cycle and 3-dimensional matching are also coNP-complete. The proofs of the main theorems use some graph gadgets defined by the authors. This completes the study of inverse problems of the six natural NP-complete problems from [\textit{M. R. Garey} and \textit{D. S. Johnson}, Computers and intractability. A guide to the theory of NP-completeness. San Francisco, CA: W. H. Freeman and Company (1979; Zbl 0411.68039)] and answers an open question raised by Chen [loc. cit.]. The coNP-completeness of the inverse problem of Hamiltonian cycle is shown to hold for undirected as well as for directed graphs. In particular, it is proved that inverting the natural verifiers of HC and 3DM is complete for the class coNP.