Testing List H-Homomorphisms

Details Testing List H-Homomorphisms Testing List H-Homomorphisms

2011-06-16

arxiv.org/abs/1106.3126v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Testing List H-Homomorphisms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing List H-Homomorphisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing List H-Homomorphisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-189350