Timeline for Colored cliques complexity
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 26, 2017 at 15:56 | vote | accept | rus9384 | ||
| May 26, 2017 at 15:44 | comment | added | D.W.♦ | @rus9384, yes, $k$ can be any number; it's part of the input. I'm not sure what you're getting at. | |
| May 26, 2017 at 15:09 | comment | added | rus9384 | And what if $k$ can be any number? | |
| May 26, 2017 at 15:08 | comment | added | D.W.♦ | @rus9384, you only need one $k$-clique per edge, so the certificate has polynomial length. | |
| May 26, 2017 at 15:08 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 7 characters in body
|
| May 26, 2017 at 15:05 | comment | added | rus9384 | I know that $k$-clique is a subcase of my problem when only one $\epsilon$ color is given, as well as SAT is a subcase of TQBF when all quantifiers are $\exists$-quantifiers. Also, number of cliques is exponential, so, I'm not sure that certificate has polynomial length. | |
| May 26, 2017 at 14:50 | history | answered | D.W.♦ | CC BY-SA 3.0 |