\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

computational complexityinverse problemsHamiltonian cyclecoNP-completeness3-dimensional matchinggraph gadget

Mathematics Subject Classification ID

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

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

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

Cited in

(4)

• Mathematical Foundations of Computer Science 2003
• Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete
• All superlinear inverse schemes are coNP-hard
• 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)