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

DOI10.1016/J.TCS.2011.08.020MaRDI QIDQ418733zbMATH OpenOpenAlexFDO

Authors Harald Hempel, Michael Krüger

Publication date 30 May 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.08.020

zbMATH Keywords

3-dimensional matchingcomputational complexitycoNP-completenessgraph gadgetHamiltonian cycleinverse problems

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete
• Mathematical Foundations of Computer Science 2003
• Inverse NP problems
• The Inverse Satisfiability Problem
• Algorithmic Applications in Management

Cites work

• All superlinear inverse schemes are coNP-hard
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete
• Mathematical Foundations of Computer Science 2003
• The Inverse Satisfiability Problem

Cited in

(4)

• All superlinear inverse schemes are coNP-hard
• Mathematical Foundations of Computer Science 2003
• Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete
• Inverse NP problems

This page was built for publication: \textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418733)