Timeline for Karp hardness of testing for homomorphisms to a fixed non-bipartite graph
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 2, 2018 at 13:34 | history | edited | kne | CC BY-SA 4.0 |
Undid a previous edit which had incorrect contents.
|
| Oct 2, 2018 at 11:55 | history | edited | kne | CC BY-SA 4.0 |
added 232 characters in body
|
| Oct 2, 2018 at 11:47 | comment | added | kne | Yes, my memory of the strong homomorphism case was faulty. Now corrected. | |
| Oct 2, 2018 at 11:41 | history | edited | kne | CC BY-SA 4.0 |
Fixed a mistake with respect to strong homomorphisms.
|
| Oct 2, 2018 at 8:29 | comment | added | Thinh D. Nguyen | Anyway, I have to admit that breaking the algebraic nature of these kinds of problems seems to push us into an unknown universe. | |
| Oct 2, 2018 at 2:13 | comment | added | Thinh D. Nguyen | If you allow the fixed graph $H$ to have loops (which are not allowed in our problem here), then instead of $3$ independent sets, you may have something like $1$ independent set and $2$ cliques, each two of them form a biclique. | |
| Oct 2, 2018 at 2:11 | comment | added | Thinh D. Nguyen | That would be a surprise if testing for being strongly homomorphic to a graph $H$ with only $3$ vertices is $NP$ complete. Note that that is testing if $G$ can be partitioned into $3$ independent sets each two of which form a biclique. | |
| Oct 1, 2018 at 13:38 | history | answered | kne | CC BY-SA 4.0 |