



















In the problem ${\rm Mix}(H)$ one is given a graph $G$ and must decide if the Hom-graph ${\rm {\bf Hom}}(G,H)$ is connected. We show that if $H$ is a triangle-free reflexive graph with at least one cycle, ${\rm Mix}(H)$ is ${\rm coNP}$-complete. The main part of this is a reduction to the problem ${\rm NonFlat}({\rm{\bf H}})$ for a simplicial complex ${\rm{\bf H}}$, in which one is given a simplicial complex ${\rm{\bf G}}$ and must decide if there are any simplicial maps $φ$ from ${\rm{\bf G}}$ to ${\rm{\bf H}}$ under which some $1$-cycles of ${\rm{\bf G}}$ maps to homologically non-trivial cycle of ${\rm{\bf H}}$. We show that for any reflexive graph $H$, if the clique complex ${\rm{\bf H}}$ of $H$ has a free, non-trivial homology group $H_1({\rm{\bf H}})$, then ${\rm NonFlat}({\rm{\bf H}})$ is ${\rm NP}$-complete.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。