4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Stella Biderman Apr 23 at 21:10
  • 1
    $\begingroup$ Pragmatically speaking, a polynomial time separation in a cryptographic scheme is a sign that the scheme doesn't work for usual purposes. $\endgroup$ – Stella Biderman Apr 23 at 21:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Aug 4 at 10:12
  • $\begingroup$ 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. $\endgroup$ – Saeed Aug 4 at 13:42
  • $\begingroup$ Simplified posting. $\endgroup$ – VS. Aug 5 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.