1
$\begingroup$

Show that graph is not Hamiltonian. Is this an NP-complete problem?

My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle than there is a path that can be traced with DFS that covers all vertices and comes back to the original source. Right?

I am not exactly sure though. Maybe my assumption is stupid! I just started to read on NP-complete problems. Need your help here...

$\endgroup$
2
  • 1
    $\begingroup$ Showing that NOT-HAMCYCLE is NP-hard is a reasonable undergrad CS exercise. Showing that it is NP-complete would upend theoretical computer science. Are you sure you're not being asked to demonstrate the former? $\endgroup$
    – Kyle Jones
    May 2, 2015 at 22:18
  • $\begingroup$ @KyleJones I am not asked to demonstrate anything.. this is a question professor asked us during the lecture and nobody answered. So I am just curious $\endgroup$
    – YohanRoth
    May 2, 2015 at 22:54

2 Answers 2

5
$\begingroup$

You probably know that showing a graph is Hamiltonian is an NP-complete problem. Thus, showing that a graph is not Hamiltonian is a co-NP-complete problem. It is an open problem as to whether or not a co-NP-complete problem can also be NP-complete.

So, the short answer is, "we don't know yet!"

$\endgroup$
1
$\begingroup$

(This answer is wrong but by virtue of apnortons comment below it might yet prove instructional to someone else but me)

I'm a bit in doubt after reading the authorative answer by apnorton, but it seems to me the NP-completeness of (is-not-Hamiltonian) can still be proven. For this one would need to a) show that (is-not-Hamiltonian) is in NP and b) find a polynomial time reduction of (is-Hamiltonian) or another NP-complete problem to (is-not-Hamiltonian).

The first property can be proven by demonstrating a verifier for the problem, i.e. a deterministic Turing machine that accepts or rejects a given candidate solution in polynomial time. It's a bit of handwaving, but I'd imagine this can be constructed analogously to a verifier for (is-Hamiltonian).

The second property can be demonstrated by showing that $\neg$ (is-Hamiltonian) is equivalent to (is-not-Hamiltonian) $\cup$ (syntactically incorrect graph encodings). Assuming there exist polynomial time syntactical validation procedures for graph encodings, this constitutes a polynomial time reduction and so (is-not-Hamiltionian) would be NP-complete.

$\endgroup$
3
  • 1
    $\begingroup$ You'd need a polynomial-time deterministic verifier for (is-not-Hamiltonian), not just a deterministic verifier, to prove (is-not-Hamiltonian) is in NP. This (NP = coNP) would flip the wigs of most theoreticians as much as if P turned out to be equivalent to NP. Tough get for a class assignment, which this question clearly is. $\endgroup$
    – Kyle Jones
    May 2, 2015 at 22:16
  • 1
    $\begingroup$ Your "first property" hand-waving is unsound. This is because verifying the existence of something is easy (just check that one solution is valid), while verifying the nonexistence of something is very hard (for this, you'd have somehow check that no possible solution is valid if you were to use the same approach as before. $\endgroup$
    – apnorton
    May 3, 2015 at 2:02
  • $\begingroup$ @apnorton Thanks for the clarification. Your answer popped up just as I was wrapping up, so I thought I'd leave mine for further comments. I can see what you mean and I appreciate your explanation. $\endgroup$
    – Fasermaler
    May 3, 2015 at 18:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .