Testing List H-Homomorphisms

Let $H$ be an undirected graph. In the List $H$-Homomorphism Problem, given an undirected graph $G$ with a list constraint $L(v)\subseteq V(H)$ for each variable $v\in V(G)$, the objective is to find a list $H$-homomorphism $f:V(G) \to V(H)$,thatis,$f(v) \in L(v)$forevery$v \in V(G)$and$(f(u),f(v)) \in E(H)$whenever$(u,v) \in E(G)$. We consider the following problem: given a map $f:V(G)\to V(H)$ as an oracle access, the objective is to decide with high probability whether $f$ is a list $H$-homomorphism or $\mathit{\text{far}}$ from any list $H$-homomorphisms. The efficiency of an algorithm is measured by the number of accesses to $f$. In this paper, we classify graphs $H$ with respect to the query complexity for testing list $H$-homomorphisms and show the following trichotomy holds: (i) List $H$-homomorphisms are testable with a constant number of queries if and only if $H$ is a reflexive complete graph or an irreflexive complete bipartite graph. (ii) List $H$-homomorphisms are testable with a sublinear number of queries if and only if $H$ is a bi-arc graph. (iii) Testing list $H$-homomorphisms requires a linear number of queries if $H$ is not a bi-arc graph.