I'm interested in the idea behind a NP completeness problem. It should be checked that Hamiltonian Path is in NP. As an indication, the problem Euler graph is in NP.

Definition of Euler graph: An Euler graph is defined by the fact that there is a circular path through a directed graph that touches every edge exactly once.

At this point, we could now take a simple directed graph, as in Figure 1. Here the Euler circle is easy to spot, even the Hamiltonian Path is easy to see. But let's look at a slightly more complicated case, shown in Figure 2. Here you can also see the Eulergraph, the HP is not possible. Or at least an HP would not touch every node once, but several times.

enter image description here

So the idea should be to transform an Euler graph into another directed graph so that its property is preserved, but still an HP is possible?

I would be interested in your opinions now, how would you show HP's NP completeness by knowing that Eulergraph is in NP?

Thanks for your interest!

  • $\begingroup$ I don't think Eulergraph is in NP, so can you give a reference for that? For directed graphs, any connected graph where every vertex has the same indegree as outdegree is Eulerian. Finding the Eulerian circuit is almost trivial - just take any path as long as you don't cause the unvisited subgraph to become disconnected. $\endgroup$ – Jaap Scherphuis Feb 13 '18 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.