Is Hamiltoncycle and Euler cycle NP-complete or not?

Question

Question: Determine which of these computational problems are NP-complete.

1. Determining whether a number with $n$ digits is a prime number.
2. Determining whether a graph with $n$ nodes has a hamiltoncycle.
3. Determining whether a graph with $n$ nodes has an eulercycle.
4. Determining whether a graph with $n$ nodes can be coloured with $2$ colors.
5. Determining whether a graph with $n$ nodes can be colored with $3$ colors.

---

My Attempts:

1) I'm not sure if this is correct because the question specifies the number of digits to be $n$ and not that the actual prime number is $n$. So in the latter case, we only need to check the division of $n$ with primes that are less than $\sqrt{n}$. This reasoning doesnt feel correct.

2) So if we first choose one node we can choose among $n$ of them, then we can choose to go to $n-1$ other nodes, and then $n-2$ and so on. So we get $n!$ which is not in polynomial time, thus it is NP-complete.

3) This one is trickier, i can't really use a similar argument as for the hamiltoncycle. I don't know the number of edges. How should I think here?

4) I assume that a coloring here should be such that no neighbouring/connected nodes have the same colour. But I have no idea how these $n$ nodes are connected in order to figure this out?

5) Same question as 4) essentially.

Answer 1

1):

It is known that primality testing is in P. But this is not at all straightforward. You can read about the algorithm here or consult the paper itself: https://en.wikipedia.org/wiki/AKS_primality_test

The problem with your argumentation is that when we refer to polynomial time we mean that with respect to the input length. Now to represent n we need $O(log(n))$ bits. So the input length is order $O(log(n))$. Your proposed algorithm of checking all the values up to $\sqrt{n}$ would satisfy (for asymptotic complexity): $$\Omega(\sqrt{n}) = \Omega(\sqrt{exp(log(n))}) = \Omega(exp(1/2log(n)))$$

Thus that is at least exponential in the input length.

2):

This is in fact NP-complete. In order to prove this you have to prove that it is in NP and that it is NP-hard. It is not too hard to prove that it is in NP: You could guess a circle consisting of all nodes and check in polynomial time that it is actually hamiltonian. It is more difficult to prove that this is NP-hard. You might want to have a look at reductions for this.

Note that your argument is not valid. You cannot conclude that something is NP-complete just because the only algorithm you found is outside of P.

3):

It is even possible to find an Eulerian path in linear time (in the number of edges). Note that there are at most $n^2$ edges in any simple undirected graph (where n is the number of nodes). You can try to find a polynomial algorithm yourself or just look it up on wikipedia. Hint to find the algorithm: Be Greedy.

4):

Your assumption is correct. Note that a graph can be colored with 2 colors if and only if it is bipartite. This can be done in polynomial time. My hint is to look at BFS (breadth first search).

5):

This is NP-complete. In order to show that you have to show that it is in NP (just give a nondeterministic polynomial algorithm that solves it) and that it is NP-hard. Again this is not very straightforward and you'll need to know about reductions to do this.

Link to wikipedia's page about reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)

Feel free to ask if anything I wrote is unclear or if you'd like more information on reductions.