<p>Given a graph on <span class="math-container">$n$</span> vertices it is <strong>strongly</strong> <span class="math-container">$NP$</span>-complete to decide it is <span class="math-container">$3$</span>-colorable while it is easy to decide it is <span class="math-container">$n$</span>-colorable.</p>

<ol>
<li><p>Is there a parsimonious reduction from <strong>SUBSET-SUM</strong> to <strong>GRAPH-3-COLORABILITY</strong> or <strong>K-INDEPENDENT SET</strong>?</p></li>
<li><p>Is there a deterministic reduction from <strong>GRAPH-3-COLORABILITY</strong> to <strong>UNAMBIGUOUS-GRAPH-3-COLORABILITY</strong> or <strong>K-INDEPENDENT SET</strong> to <strong>UNMAMBIGUOUS-K-INDEPENDENT SET</strong>?</p></li>
</ol>

CC BY-SA 4.0
2019-04-23T21:10:01.553Z
This is a bit of a strange question. Polynomial time separations can be crossed by changing computer architecture, so I think you'd have to be very specific about what context you want a polynomial separation to hold on.
Stella Biderman
CC BY-SA 4.0
2019-04-23T21:10:18.840Z
Pragmatically speaking, a polynomial time separation in a cryptographic scheme is a sign that the scheme doesn't work for usual purposes.
Stella Biderman
CC BY-SA 4.0
2019-08-04T10:12:01.980Z
I think it's better to stick to a single question, not a list of questions. I also think it's better to start a new question rather than change an old one into something completely different.
Sasho Nikolov
CC BY-SA 4.0
2019-08-04T13:42:39.363Z
In planar graphs 6 coloring is trivial, and 4 coloring is doable in polynomial time, but 3 coloring is hard. So I don't see if there is any point to define a function like f(n), as for example in complete graphs it should be at least n and in planar graphs it should be a constant.
Saeed
CC BY-SA 4.0
2019-08-05T22:38:10.827Z
Simplified posting.
VS.
<cc.complexity-theory><parameterized-complexity><graph-colouring><subset-sum><independent-set>
Difficulty of graph coloring and independent set?
VS.
# Difficulty of graph coloring and independent set?

(Asked by: username_0 on 2019-03-23)

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.

1. Is there a parsimonious reduction from **SUBSET-SUM** to **GRAPH-3-COLORABILITY** or **K-INDEPENDENT SET**?
2. Is there a deterministic reduction from **GRAPH-3-COLORABILITY** to **UNAMBIGUOUS-GRAPH-3-COLORABILITY** or **K-INDEPENDENT SET** to **UNMAMBIGUOUS-K-INDEPENDENT SET**?

**Tags:** cc.complexity-theory, parameterized-complexity, graph-colouring, subset-sum, independent-set

> **Comments:**
> **username_1**: This is a bit of a strange question. Polynomial time separations can be crossed by changing computer architecture, so I think you'd have to be very specific about what context you want a polynomial separation to hold on.  
> **username_1**: Pragmatically speaking, a polynomial time separation in a cryptographic scheme is a sign that the scheme doesn't work for usual purposes.  
> **username_2**: I think it's better to stick to a single question, not a list of questions. I also think it's better to start a new question rather than change an old one into something completely different.  
> **username_3**: In planar graphs 6 coloring is trivial, and 4 coloring is doable in polynomial time, but 3 coloring is hard. So I don't see if there is any point to define a function like f(n), as for example in complete graphs it should be at least n and in planar graphs it should be a constant.  
> **username_0**: Simplified posting.  

---

## 0 answers

