Timeline for Karp hardness of testing for homomorphisms to a fixed non-bipartite graph
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2018 at 9:20 | vote | accept | Thinh D. Nguyen | ||
| Oct 11, 2018 at 0:00 | history | tweeted | twitter.com/StackCompSci/status/1050174315868684288 | ||
| Oct 2, 2018 at 14:13 | comment | added | David Richerby | @kne It's just "Add a loop to every vertex of $H$ -- is there a surjective homomorphism?" I don't think it has much in common with graph minors. | |
| Oct 2, 2018 at 14:11 | answer | added | David Richerby | timeline score: 2 | |
| Oct 2, 2018 at 8:31 | comment | added | Thinh D. Nguyen | That is kind of what I was afraid of. | |
| Oct 2, 2018 at 8:25 | comment | added | user53923 | By your current definition, if $H$ is a clique, any graph $G$ with at least as many vertices as $H$ is "loopless surjectively homomorphic" to $H$. Is this desirable? Interesting question what the complexity would be for other choices of $H$ (I suspect this is not known) | |
| Oct 2, 2018 at 7:54 | history | edited | Thinh D. Nguyen | CC BY-SA 4.0 |
added 277 characters in body
|
| Oct 2, 2018 at 7:46 | comment | added | Thinh D. Nguyen | $H$ is fixed. $G$ is the input. So for large enough $G$, it is necessarily to have $\varphi(u)=\varphi(v)$ for some distinct $u,v\in V(G)$. And we don't want any loops in $H$. Admittedly, this is not algebraic. | |
| Oct 2, 2018 at 7:39 | comment | added | user53923 | Well I cannot say for sure whether it has unwanted features (because I do not know what you want to define exactly), but I think at least the problem is now non-trivial, which is good. Can you explain why you want to allow $\varphi(u) = \varphi(v)$? | |
| Oct 2, 2018 at 2:14 | comment | added | Thinh D. Nguyen | If the current version still has some unwanted feature, please comment to let me know. | |
| Oct 1, 2018 at 14:28 | history | edited | Thinh D. Nguyen | CC BY-SA 4.0 |
added 109 characters in body
|
| Oct 1, 2018 at 14:17 | history | edited | Thinh D. Nguyen | CC BY-SA 4.0 |
added 128 characters in body
|
| Oct 1, 2018 at 13:38 | answer | added | kne | timeline score: 2 | |
| Oct 1, 2018 at 12:46 | comment | added | user53923 | If I read your current definition correctly, any graph $G$ is homomorphic to $H$. (Pick an arbitrary vertex $h \in V(H)$ and let $\varphi(v) = h$ for all $v\in V(G)$)? | |
| Oct 1, 2018 at 12:28 | history | edited | Thinh D. Nguyen | CC BY-SA 4.0 |
added 33 characters in body
|
| Oct 1, 2018 at 10:50 | comment | added | user53923 | Normally, the requirement would be $uv \in E(G) \Rightarrow \varphi(u)\varphi(v) \in E(H)$. Are you sure your definition of homomorphism is correct? (see also en.wikipedia.org/wiki/Graph_homomorphism) | |
| Oct 1, 2018 at 10:42 | comment | added | user53923 | Do you want to know whether there exists a (non-bipartite) graph for which the problem is NP-complete, or do you want to know the exact complexity for each choice for H? | |
| Oct 1, 2018 at 6:44 | history | asked | Thinh D. Nguyen | CC BY-SA 4.0 |