3
$\begingroup$

I know that finding a Hamiltonian circuit is in NP and I know that finding an Eulerian circuit is in P. However, what about the following problem:

  • Must leave the starting vertex and visit every other vertex;
  • You may only return to the start after visiting every other vertex;
  • You can visit the same vertex multiple times, as long as it's not the starting vertex;
  • You don't have to use every edge in the graph, but each edge can only be used once.

Is that in P or NP-hard? I tried different approaches to this but now I don't know if I'm wasting my time in case this problem doesn't have an efficient solution.

$\endgroup$
  • $\begingroup$ Without loss of generality the path never returns to the start vertex (otherwise truncate the path just before it first returns to the starting vertex, and the result still meets all your conditions), so you're asking if there is a path that starts at the starting vertex, never returns to the starting vertex, visits every vertex at least once, and traverses each edge at most once. It's certainly in NP. $\endgroup$ – D.W. Mar 15 '18 at 0:20
  • $\begingroup$ If the starting vertex doesn't have at least two edges, the answer is false. Otherwise isn't this equivalent to whether deleting zero or more edges admits an Eulerian cycle? Also, nitpicking but NP includes P so the question is whether it is in P or NP $\setminus$ P. $\endgroup$ – Solomonoff's Secret Mar 15 '18 at 1:03
  • $\begingroup$ @Solomonoff'sSecret, I don't think it's equivalent to checking for a Eulerian cycle, because the Eulerian cycle might violate the 2nd requirement (it might return to the starting vertex before visiting every other vertex). Am I missing something? $\endgroup$ – D.W. Mar 15 '18 at 6:27
  • $\begingroup$ @Solomonoff'sSecret How to determine whether deleting zero or more edges admits an Eulerian cycle? $\endgroup$ – xskxzr Mar 15 '18 at 6:50
  • 3
    $\begingroup$ For directed graph, it is NP-hard. $\endgroup$ – xskxzr Mar 15 '18 at 16:04
3
$\begingroup$

This problem is NP-hard.

Consider the following variants:

Variant 1: given a graph where each vertex has degree at most three, determine if there is a Hamiltonian path.

Variant 2: given a graph, determine if there is a trail (a path without repeated edges) that visits every vertex at least once.

Variant 1 is NP-hard [1].

Variant 1 can be reduced to variant 2 by mapping to the same graph.

If there is a Hamiltonian path on the graph, the Hamiltonian path is certainly a trail that visits every vertex at least once.

On the other hand, if there is a trail from $u$ to $v$ that visits every vertex at least once, since every vertex in the graph has degree at most three, every vertex except $u$ and $v$ must appear exactly once on the trail. If every vertex appears exactly once, the trail itself is a Hamiltonian path. If $u$ and/or $v$ appear twice, remove the first and/or the last edges on the trail respectively, then the trail becomes a Hamiltonian path. Anyway there is a Hamiltonian path in the graph.

So variant 2 is NP-hard.


Suppose the problem in OP is in P. Given an instance of variant 2, construct a new graph for every pair of vertexes $(u,v)$ by adding a new vertex $s$ and new edges $(s,u)$ and $(v,s)$. Now there is a trail that visits every vertex at least once in the original graph if and only if the answer to the problem in OP on at least one of these new graphs is "yes". So one can solve variant 2 in polynomial time by solving the problem in OP on these new graphs. So the problem in OP is NP-hard.


[1] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.