Problem Detail: Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? I’m aware we can show that 3-colorable is an NP-complete problem by reducing 3-SAT to it. But I’m wondering is it possible to reduce clique to it? I know for example that if a graph with n vertices contains a subgraph which is a clique of size k, then you need at least k colors (that is, the chromatic number is at least k). So could we say that if a graph contains a clique of size 4, then it is not 3-colorable, and vice versa? Edit: Hmm..upon further thought, maybe the reduction wouldn’t work because in order to reduce clique, you can’t fix ahead of time that you’re looking for a clique of size 4? The size of the clique would be arbitrary..
Asked By : user3280193
Answered By : adrianN
A problem $P$ being NP-hard means that all problems in NP can be reduced to $P$. That’s by definition. Working out the exact reduction needed can be tricky, which is why one usually looks for a somehow similar problem to prove hardness. You probably wouldn’t try to directly reduce MINIMUM INTERVAL GRAPH COMPLETION to Tetris to prove its hardness. In general you can chain reductions. In your case, since you know 3-colorability can be used to solve 3-SAT and you know 3-SAT can be used to solve CLIQUE, you can first transform your CLIQUE instance to 3-SAT and then the resulting formula to a 3-colourability problem.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/54204
