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

DOI10.1016/J.TCS.2011.08.020zbMATH Open1246.68124OpenAlexW2007310587MaRDI QIDQ418733FDOQ418733

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Inverse Satisfiability Problem
• All superlinear inverse schemes are coNP-hard
• Mathematical Foundations of Computer Science 2003
• Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete

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)