| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437266 | Theoretical Computer Science | 2012 | 17 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
