Is Hamiltoncycle and Euler cycle NP-complete or not?Every $t$-coloring of $K_{2t+1}$ contains a monochromatic...
What is the fastest integer factorization to break RSA?
How can I deal with my CEO asking me to hire someone with a higher salary than me, a co-founder?
How to stretch the corners of this image so that it looks like a perfect rectangle?
Using "tail" to follow a file without displaying the most recent lines
Can a virus destroy the BIOS of a modern computer?
Different meanings of こわい
Why was Sir Cadogan fired?
Can someone clarify Hamming's notion of important problems in relation to modern academia?
Venezuelan girlfriend wants to travel the USA to be with me. What is the process?
Implication of namely
Forgetting the musical notes while performing in concert
What Exploit Are These User Agents Trying to Use?
OP Amp not amplifying audio signal
Unlock My Phone! February 2018
How can a day be of 24 hours?
In the UK, is it possible to get a referendum by a court decision?
Do Iron Man suits sport waste management systems?
How could indestructible materials be used in power generation?
Is it "common practice in Fourier transform spectroscopy to multiply the measured interferogram by an apodizing function"? If so, why?
How badly should I try to prevent a user from XSSing themselves?
What are the G forces leaving Earth orbit?
Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?
What is required to make GPS signals available indoors?
Is it a bad idea to plug the other end of ESD strap to wall ground?
Is Hamiltoncycle and Euler cycle NP-complete or not?
Every $t$-coloring of $K_{2t+1}$ contains a monochromatic cycleComplete graph-coloringColouring $n$ vertices with $(n-1)$ colours in a graph with chromatic number $n$Check existence of walk visiting every node in graph odd-timesUse of pigeonhole principle in ramsey-theorem about monochromatic triangles.Alternating cycle in a graphGraph Coloring : How to Think about Algorithms Exercise 1.6.2Complete graphs in the plane with colored edges where an edge don't cross edges with same colorIs it possible to start with a partially colored graph for a graph $G$ and complete it into a coloring with $chi(G)$ colors?A new graph invariant? The maximum number of non-equivalent colorings with $n$ colors.
$begingroup$
Question: Determine which of these computational problems are NP-complete.
- Determining whether a number with $n$ digits is a prime number.
- Determining whether a graph with $n$ nodes has a hamiltoncycle.
- Determining whether a graph with $n$ nodes has an eulercycle.
- Determining whether a graph with $n$ nodes can be coloured with $2$ colors.
- 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.
discrete-mathematics graph-theory
$endgroup$
add a comment |
$begingroup$
Question: Determine which of these computational problems are NP-complete.
- Determining whether a number with $n$ digits is a prime number.
- Determining whether a graph with $n$ nodes has a hamiltoncycle.
- Determining whether a graph with $n$ nodes has an eulercycle.
- Determining whether a graph with $n$ nodes can be coloured with $2$ colors.
- 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.
discrete-mathematics graph-theory
$endgroup$
$begingroup$
For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
$endgroup$
– frabala
Mar 18 at 13:52
$begingroup$
What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
$endgroup$
– Parseval
Mar 18 at 14:21
1
$begingroup$
You're right. I falsely assumed constant time for checking the degree of a node.
$endgroup$
– frabala
Mar 18 at 14:29
add a comment |
$begingroup$
Question: Determine which of these computational problems are NP-complete.
- Determining whether a number with $n$ digits is a prime number.
- Determining whether a graph with $n$ nodes has a hamiltoncycle.
- Determining whether a graph with $n$ nodes has an eulercycle.
- Determining whether a graph with $n$ nodes can be coloured with $2$ colors.
- 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.
discrete-mathematics graph-theory
$endgroup$
Question: Determine which of these computational problems are NP-complete.
- Determining whether a number with $n$ digits is a prime number.
- Determining whether a graph with $n$ nodes has a hamiltoncycle.
- Determining whether a graph with $n$ nodes has an eulercycle.
- Determining whether a graph with $n$ nodes can be coloured with $2$ colors.
- 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.
discrete-mathematics graph-theory
discrete-mathematics graph-theory
asked Mar 18 at 13:38
ParsevalParseval
3,0721719
3,0721719
$begingroup$
For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
$endgroup$
– frabala
Mar 18 at 13:52
$begingroup$
What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
$endgroup$
– Parseval
Mar 18 at 14:21
1
$begingroup$
You're right. I falsely assumed constant time for checking the degree of a node.
$endgroup$
– frabala
Mar 18 at 14:29
add a comment |
$begingroup$
For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
$endgroup$
– frabala
Mar 18 at 13:52
$begingroup$
What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
$endgroup$
– Parseval
Mar 18 at 14:21
1
$begingroup$
You're right. I falsely assumed constant time for checking the degree of a node.
$endgroup$
– frabala
Mar 18 at 14:29
$begingroup$
For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
$endgroup$
– frabala
Mar 18 at 13:52
$begingroup$
For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
$endgroup$
– frabala
Mar 18 at 13:52
$begingroup$
What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
$endgroup$
– Parseval
Mar 18 at 14:21
$begingroup$
What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
$endgroup$
– Parseval
Mar 18 at 14:21
1
1
$begingroup$
You're right. I falsely assumed constant time for checking the degree of a node.
$endgroup$
– frabala
Mar 18 at 14:29
$begingroup$
You're right. I falsely assumed constant time for checking the degree of a node.
$endgroup$
– frabala
Mar 18 at 14:29
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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 argumentation 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.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3152801%2fis-hamiltoncycle-and-euler-cycle-np-complete-or-not%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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 argumentation 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.
$endgroup$
add a comment |
$begingroup$
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 argumentation 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.
$endgroup$
add a comment |
$begingroup$
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 argumentation 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.
$endgroup$
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 argumentation 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.
answered Mar 18 at 20:23
araomisaraomis
4039
4039
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3152801%2fis-hamiltoncycle-and-euler-cycle-np-complete-or-not%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
For (3), it is known that a graph has an eulerian cycle if and only if all the nodes have an even degree. That's linear on the number of nodes.
$endgroup$
– frabala
Mar 18 at 13:52
$begingroup$
What do you mean by "Thats linear on the number of nodes"? So the problem is then to check whether or not all of these $n$ nodes have an even degree. How is this a linear problem?
$endgroup$
– Parseval
Mar 18 at 14:21
1
$begingroup$
You're right. I falsely assumed constant time for checking the degree of a node.
$endgroup$
– frabala
Mar 18 at 14:29