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

DOI10.1016/j.tcs.2011.08.020zbMath1246.68124OpenAlexW2007310587MaRDI QIDQ418733

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

computational complexityinverse problemsHamiltonian cyclecoNP-completeness3-dimensional matchinggraph gadget

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) 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) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Unnamed Item
• Unnamed Item
• All superlinear inverse schemes are coNP-hard
• The Inverse Satisfiability Problem
• Mathematical Foundations of Computer Science 2003
• Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete

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