All Questions
1 question
3
votes
0
answers
319
views
Difficulty of graph coloring and independent set?
Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable.
Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-...
- 549