Why finding chromatic number is NP-Hard?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color .
But why the coloring is NP-HARD ? and what is the difference between it and vertex coloring ?
discrete-mathematics graph-theory computational-complexity np-complete
edited Jul 8 '15 at 15:10
Henning Makholm
231k16297529
asked Jul 8 '15 at 14:52
Mike Bluer
336
 |Â
show 3 more comments
up vote
0
down vote
favorite
We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color .
But why the coloring is NP-HARD ? and what is the difference between it and vertex coloring ?
discrete-mathematics graph-theory computational-complexity np-complete
edited Jul 8 '15 at 15:10
Henning Makholm
231k16297529
asked Jul 8 '15 at 14:52
Mike Bluer
336
4
Do you know what NP-Hard means in terms of theoretical computer science ? It essentially means that any problem in NP can be transformed so it becomes the problem of finding the chromatic number of a graph. And can you define vertex coloring ? As far as I know, it's the same thing.
– Manuel Lafond
Jul 8 '15 at 14:59
Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ?
– Mike Bluer
Jul 8 '15 at 15:02
2
Even determining whether the chromatic number is $le 3$ (that is, whether a given graph is 3-colorable) is NP-hard. You can find several descriptions of the standard reduction from CNF-SAT by googling for 3-coloring np-hard.
– Henning Makholm
Jul 8 '15 at 15:07
2
One reason is that the number of colorings we have to try grows very very fast and we don't have a clear way of deciding which colorings are "worth trying".
– Jorge Fernández
Jul 8 '15 at 15:08
@Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE
– Tandee Holwa
Jul 9 '15 at 23:22
 |Â
show 3 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color .
But why the coloring is NP-HARD ? and what is the difference between it and vertex coloring ?
discrete-mathematics graph-theory computational-complexity np-complete
edited Jul 8 '15 at 15:10
Henning Makholm
231k16297529
asked Jul 8 '15 at 14:52
Mike Bluer
336
We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color .
But why the coloring is NP-HARD ? and what is the difference between it and vertex coloring ?
discrete-mathematics graph-theory computational-complexity np-complete
discrete-mathematics graph-theory computational-complexity np-complete
edited Jul 8 '15 at 15:10
Henning Makholm
231k16297529
asked Jul 8 '15 at 14:52
Mike Bluer
336
edited Jul 8 '15 at 15:10
Henning Makholm
231k16297529
asked Jul 8 '15 at 14:52
Mike Bluer
336
edited Jul 8 '15 at 15:10
Henning Makholm
231k16297529
edited Jul 8 '15 at 15:10
Henning Makholm
231k16297529
edited Jul 8 '15 at 15:10
Henning Makholm
231k16297529
231k16297529
asked Jul 8 '15 at 14:52
Mike Bluer
336
asked Jul 8 '15 at 14:52
Mike Bluer
336
asked Jul 8 '15 at 14:52
Mike Bluer
336
336
4
Do you know what NP-Hard means in terms of theoretical computer science ? It essentially means that any problem in NP can be transformed so it becomes the problem of finding the chromatic number of a graph. And can you define vertex coloring ? As far as I know, it's the same thing.
– Manuel Lafond
Jul 8 '15 at 14:59
Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ?
– Mike Bluer
Jul 8 '15 at 15:02
2
Even determining whether the chromatic number is $le 3$ (that is, whether a given graph is 3-colorable) is NP-hard. You can find several descriptions of the standard reduction from CNF-SAT by googling for 3-coloring np-hard.
– Henning Makholm
Jul 8 '15 at 15:07
2
One reason is that the number of colorings we have to try grows very very fast and we don't have a clear way of deciding which colorings are "worth trying".
– Jorge Fernández
Jul 8 '15 at 15:08
@Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE
– Tandee Holwa
Jul 9 '15 at 23:22
 |Â
show 3 more comments
4
Do you know what NP-Hard means in terms of theoretical computer science ? It essentially means that any problem in NP can be transformed so it becomes the problem of finding the chromatic number of a graph. And can you define vertex coloring ? As far as I know, it's the same thing.
– Manuel Lafond
Jul 8 '15 at 14:59
Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ?
– Mike Bluer
Jul 8 '15 at 15:02
2
Even determining whether the chromatic number is $le 3$ (that is, whether a given graph is 3-colorable) is NP-hard. You can find several descriptions of the standard reduction from CNF-SAT by googling for 3-coloring np-hard.
– Henning Makholm
Jul 8 '15 at 15:07
2
One reason is that the number of colorings we have to try grows very very fast and we don't have a clear way of deciding which colorings are "worth trying".
– Jorge Fernández
Jul 8 '15 at 15:08
@Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE
– Tandee Holwa
Jul 9 '15 at 23:22
4
4
Do you know what NP-Hard means in terms of theoretical computer science ? It essentially means that any problem in NP can be transformed so it becomes the problem of finding the chromatic number of a graph. And can you define vertex coloring ? As far as I know, it's the same thing.
– Manuel Lafond
Jul 8 '15 at 14:59
Do you know what NP-Hard means in terms of theoretical computer science ? It essentially means that any problem in NP can be transformed so it becomes the problem of finding the chromatic number of a graph. And can you define vertex coloring ? As far as I know, it's the same thing.
– Manuel Lafond
Jul 8 '15 at 14:59
Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ?
– Mike Bluer
Jul 8 '15 at 15:02
Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ?
– Mike Bluer
Jul 8 '15 at 15:02
2
2
Even determining whether the chromatic number is $le 3$ (that is, whether a given graph is 3-colorable) is NP-hard. You can find several descriptions of the standard reduction from CNF-SAT by googling for 3-coloring np-hard.
– Henning Makholm
Jul 8 '15 at 15:07
Even determining whether the chromatic number is $le 3$ (that is, whether a given graph is 3-colorable) is NP-hard. You can find several descriptions of the standard reduction from CNF-SAT by googling for 3-coloring np-hard.
– Henning Makholm
Jul 8 '15 at 15:07
2
2
One reason is that the number of colorings we have to try grows very very fast and we don't have a clear way of deciding which colorings are "worth trying".
– Jorge Fernández
Jul 8 '15 at 15:08
One reason is that the number of colorings we have to try grows very very fast and we don't have a clear way of deciding which colorings are "worth trying".
– Jorge Fernández
Jul 8 '15 at 15:08
@Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE
– Tandee Holwa
Jul 9 '15 at 23:22
@Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE
– Tandee Holwa
Jul 9 '15 at 23:22
 |Â
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
A decision problem A is NP-hard means that if you can solve A in polynomial in input size, you can solve any NP problem in polynomial time (in input size). The mechanism to convert a problem B to a problem A (in polynomial time) is called a reduction from B to A.
3-COLOURABILITY
Input: A graph G
Question: Is G 3-colourable (i.e., is $chi(G)leq 3)$ ?
The problem 3-COLOURABILITY is NP-hard because there is a polynomial time reduction from 3-SAT to 3-COLOURABILITY and there is a reduction from SAT to 3-SAT. It is proven that if you can solve SAT in polynomial time, you can solve any NP problem in polynomial time (Cook's theorem). Hence, checking if chromatic number is at most 3 is hard and therefore finding chromatic number exactly must be hard as well.
Note: (Read this in case you get interested in reductions)
You can find a reduction from NAE SAT to 3-COLOURABILITY more easily (i think so).
answered Sep 7 at 4:50
Cyriac Antony
1049
The first sentence of this is often found in popular treatments, but is slightly incorrect. As written it would be satisfied by any problem outside P, but if P≠NP then there exist NP-intermediate problems, which by definition are neither in P nor NP-hard. Instead, NP-hardness is defined explicitly by the existence of (poly-time many-one) reductions.
– Henning Makholm
Sep 7 at 5:29
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
A decision problem A is NP-hard means that if you can solve A in polynomial in input size, you can solve any NP problem in polynomial time (in input size). The mechanism to convert a problem B to a problem A (in polynomial time) is called a reduction from B to A.
3-COLOURABILITY
Input: A graph G
Question: Is G 3-colourable (i.e., is $chi(G)leq 3)$ ?
The problem 3-COLOURABILITY is NP-hard because there is a polynomial time reduction from 3-SAT to 3-COLOURABILITY and there is a reduction from SAT to 3-SAT. It is proven that if you can solve SAT in polynomial time, you can solve any NP problem in polynomial time (Cook's theorem). Hence, checking if chromatic number is at most 3 is hard and therefore finding chromatic number exactly must be hard as well.
Note: (Read this in case you get interested in reductions)
You can find a reduction from NAE SAT to 3-COLOURABILITY more easily (i think so).
answered Sep 7 at 4:50
Cyriac Antony
1049
The first sentence of this is often found in popular treatments, but is slightly incorrect. As written it would be satisfied by any problem outside P, but if P≠NP then there exist NP-intermediate problems, which by definition are neither in P nor NP-hard. Instead, NP-hardness is defined explicitly by the existence of (poly-time many-one) reductions.
– Henning Makholm
Sep 7 at 5:29
add a comment |Â
up vote
0
down vote
A decision problem A is NP-hard means that if you can solve A in polynomial in input size, you can solve any NP problem in polynomial time (in input size). The mechanism to convert a problem B to a problem A (in polynomial time) is called a reduction from B to A.
3-COLOURABILITY
Input: A graph G
Question: Is G 3-colourable (i.e., is $chi(G)leq 3)$ ?
The problem 3-COLOURABILITY is NP-hard because there is a polynomial time reduction from 3-SAT to 3-COLOURABILITY and there is a reduction from SAT to 3-SAT. It is proven that if you can solve SAT in polynomial time, you can solve any NP problem in polynomial time (Cook's theorem). Hence, checking if chromatic number is at most 3 is hard and therefore finding chromatic number exactly must be hard as well.
Note: (Read this in case you get interested in reductions)
You can find a reduction from NAE SAT to 3-COLOURABILITY more easily (i think so).
answered Sep 7 at 4:50
Cyriac Antony
1049
The first sentence of this is often found in popular treatments, but is slightly incorrect. As written it would be satisfied by any problem outside P, but if P≠NP then there exist NP-intermediate problems, which by definition are neither in P nor NP-hard. Instead, NP-hardness is defined explicitly by the existence of (poly-time many-one) reductions.
– Henning Makholm
Sep 7 at 5:29
add a comment |Â
up vote
0
down vote
up vote
0
down vote
A decision problem A is NP-hard means that if you can solve A in polynomial in input size, you can solve any NP problem in polynomial time (in input size). The mechanism to convert a problem B to a problem A (in polynomial time) is called a reduction from B to A.
3-COLOURABILITY
Input: A graph G
Question: Is G 3-colourable (i.e., is $chi(G)leq 3)$ ?
The problem 3-COLOURABILITY is NP-hard because there is a polynomial time reduction from 3-SAT to 3-COLOURABILITY and there is a reduction from SAT to 3-SAT. It is proven that if you can solve SAT in polynomial time, you can solve any NP problem in polynomial time (Cook's theorem). Hence, checking if chromatic number is at most 3 is hard and therefore finding chromatic number exactly must be hard as well.
Note: (Read this in case you get interested in reductions)
You can find a reduction from NAE SAT to 3-COLOURABILITY more easily (i think so).
answered Sep 7 at 4:50
Cyriac Antony
1049
A decision problem A is NP-hard means that if you can solve A in polynomial in input size, you can solve any NP problem in polynomial time (in input size). The mechanism to convert a problem B to a problem A (in polynomial time) is called a reduction from B to A.
3-COLOURABILITY
Input: A graph G
Question: Is G 3-colourable (i.e., is $chi(G)leq 3)$ ?
The problem 3-COLOURABILITY is NP-hard because there is a polynomial time reduction from 3-SAT to 3-COLOURABILITY and there is a reduction from SAT to 3-SAT. It is proven that if you can solve SAT in polynomial time, you can solve any NP problem in polynomial time (Cook's theorem). Hence, checking if chromatic number is at most 3 is hard and therefore finding chromatic number exactly must be hard as well.
Note: (Read this in case you get interested in reductions)
You can find a reduction from NAE SAT to 3-COLOURABILITY more easily (i think so).
answered Sep 7 at 4:50
Cyriac Antony
1049
answered Sep 7 at 4:50
Cyriac Antony
1049
answered Sep 7 at 4:50
Cyriac Antony
1049
answered Sep 7 at 4:50
Cyriac Antony
1049
1049
The first sentence of this is often found in popular treatments, but is slightly incorrect. As written it would be satisfied by any problem outside P, but if P≠NP then there exist NP-intermediate problems, which by definition are neither in P nor NP-hard. Instead, NP-hardness is defined explicitly by the existence of (poly-time many-one) reductions.
– Henning Makholm
Sep 7 at 5:29
add a comment |Â
The first sentence of this is often found in popular treatments, but is slightly incorrect. As written it would be satisfied by any problem outside P, but if P≠NP then there exist NP-intermediate problems, which by definition are neither in P nor NP-hard. Instead, NP-hardness is defined explicitly by the existence of (poly-time many-one) reductions.
– Henning Makholm
Sep 7 at 5:29
The first sentence of this is often found in popular treatments, but is slightly incorrect. As written it would be satisfied by any problem outside P, but if P≠NP then there exist NP-intermediate problems, which by definition are neither in P nor NP-hard. Instead, NP-hardness is defined explicitly by the existence of (poly-time many-one) reductions.
– Henning Makholm
Sep 7 at 5:29
The first sentence of this is often found in popular treatments, but is slightly incorrect. As written it would be satisfied by any problem outside P, but if P≠NP then there exist NP-intermediate problems, which by definition are neither in P nor NP-hard. Instead, NP-hardness is defined explicitly by the existence of (poly-time many-one) reductions.
– Henning Makholm
Sep 7 at 5:29
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1353942%2fwhy-finding-chromatic-number-is-np-hard%23new-answer', 'question_page');
);
Post as a guest
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
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
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
4
Do you know what NP-Hard means in terms of theoretical computer science ? It essentially means that any problem in NP can be transformed so it becomes the problem of finding the chromatic number of a graph. And can you define vertex coloring ? As far as I know, it's the same thing.
– Manuel Lafond
Jul 8 '15 at 14:59
Yes, I know, but why this problem 'Chromatic Coloring' is NP-Hard ?
– Mike Bluer
Jul 8 '15 at 15:02
2
Even determining whether the chromatic number is $le 3$ (that is, whether a given graph is 3-colorable) is NP-hard. You can find several descriptions of the standard reduction from CNF-SAT by googling for 3-coloring np-hard.
– Henning Makholm
Jul 8 '15 at 15:07
2
One reason is that the number of colorings we have to try grows very very fast and we don't have a clear way of deciding which colorings are "worth trying".
– Jorge Fernández
Jul 8 '15 at 15:08
@Henning Makholm why it is NP-Hard not NP-Complete, I think it is NP-COMPLETE
– Tandee Holwa
Jul 9 '15 at 23:22