Testing List H-Homomorphisms

Abstract

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)$, that is, $f(v)\in L(v)$ for every $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 \textit{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.