DocumentCode :
2653224
Title :
Testing List H-homomorphisms
Author :
Yoshida, Yuichi
Author_Institution :
Sch. of Inf., Kyoto Univ., Kyoto, Japan
fYear :
2012
fDate :
26-29 June 2012
Firstpage :
85
Lastpage :
95
Abstract :
Let H be an undirected graph. In the List H-Homomorphism Problem, given an undirected graph G with a list constraint L(v) ⊆ V(H) for each variable v ∈ V(G), the objective is to find a list H-homomorphism f:V(G) → V(H), that is, f(v) ∈ L(v) for every v ∈ V(G) and (f(u), f(v)) ∈ E(H) whenever (u, v) ∈ E(G). We consider testing list H-homomorphism: given a map f:V(G) → V(H) as an oracle, the objective is to decide with high probability whether f is a list H-homomorphism or 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. Specifically, we show that (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, and (ii) list H-homomorphisms are testable with a sub linear number of queries if and only if H is a bi-arc graph. Thus, we give equivalent conditions of graphs H such that list H-homomorphisms are testable in constant / sub linear but not constant / linear number of queries.
Keywords :
constraint satisfaction problems; graph theory; probability; biarc graph; equivalent conditions; irreflexive complete bipartite graph; list H-homomorphism problem; list H-homomorphism testing; list constraint; probability; query complexity; reflexive complete graph; undirected graph; Algebra; Bipartite graph; Computational complexity; Educational institutions; Testing; Vocabulary; Property testing; constraint satisfaction problems; list H-homomorphism; universal algebra;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on
Conference_Location :
Porto
ISSN :
1093-0159
Print_ISBN :
978-1-4673-1663-7
Type :
conf
DOI :
10.1109/CCC.2012.9
Filename :
6243384
Link To Document :
بازگشت