List H-Homomorphisms: Query Complexity & Graph Classes
Explore the concept of List H-Homomorphisms and their query complexity in testing, including reflexive and irreflexive complete graph classes. Learn why List H-Homomorphisms are important in graph theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Testing List H-Homomorphisms Yuichi Yoshida (? ) National Institute of Informatics & Preferred Infrastructure
H-homomorphism f : V(G) V(H) is a homomorphism from G to H if (u, v) E(G) (f(u), f(v)) E(H) H: might have self-loops G K3iff G is 3-colorable / C4 G iff G has 4-cycle /
List H-homomorphism f is a list homomorphism w.r.t. a list constraint L:V(G) 2V(H)if f is a homomorphism and f(v) L(v) for every v V(G) G H { , } / { } LHOM(H) = problem of finding list H-homomorphisms
Property testing Given f: D R and a property P of functions. Want to test whether f satisfies P very efficiently . all functions P need to read f completely can we distinguish by reading a few of f(x) s? not P far
Property testing dist(f, g) = Prx D[f(x) g(x)] f is -far from a property P if g:satisfyingPdist(f,g) e min An -tester for P: all functions accept w.p. 2/3 P -far reject w.p. 2/3
Testing list H-homomorphism Graphs G, H and a list constraint L are known. Given f : V(G) V(H) as an oracle. For any v, we can get f(v) by one query. query! G H ? { , } { } query! How many queries do we need to test LHOM(H)?
Main result Completely classify H w.r.t. the query complexity to test LHOM(H) : H Query complexity (1) O( n), (log n / log log n) (n) but not not reflexive complete or irreflexive complete bipartite bi-arc
Graph classes Reflexive complete Irreflexive complete bipartite Bi-arc: too messy to define here. A reflexive graph is bi-arc iff it is interval
Why do we care about list H-homomorphisms?
Constraint satisfaction problems (CSPs) V: variables over a domain D. C: constraints over variables V. f: V D is called a solution if f(v) satisfies all the constraints in C. CSPs contain a lot of problems: SAT, 3COL, 3LIN2, etc. LHOM(H) Unary and binary constraints only. Every binary constraint is given by H.
Testing assignments of CSPs A CSP instance ? = (V, C) is known. Given an assignment f: V D as an oracle Want to test f is a solution. CSP 2COL 2SAT 3LIN2 3SAT Query complexity (1) [folklore] O( n), (log n / log log n) [FLNRRS02] (n) [BHR06] (n) [BHR06]
Testing assignments of CSPs Implicitly related to testing function properties. Function f assignment. Property a CSP instance. Monotonicity [FLNRRS02] Lipschitz [JR11] Submodularity [SV11] f:{0,1}n {0,1} Deep theory of CSPs might be useful to analyze them.
Query complexity to test CSPs Seems some connection to computational complexity. 1. O(1) NL easy to count? 2. o(n) NL? 3. (n) NPC? all CSPs 3SAT easy to count NL 2SAT 3LIN2 2COL
Query complexity to test LHOM(H) It s indeed the case for LHOM(H)! 1. O(1) NL & easy to count 2. o(n) NL 3. (n) non NPC all CSPs 3SAT easy to count NL reflexive complete or irreflexive complete bipartite bi-arc 2SAT 3LIN2 2COL
Main Result Completely classify the query complexity for testing list H-homomorphism: H Query complexity (1) O( n), (log n / log log n) (n) but not not reflexive complete or irreflexive complete bipartite bi-arc
O(n) algorithm for bi-arc H (part 1) Run a propagation algorithm (called Datalog) and get Su, v V(H)2for each u, v V(G). u v u u v v Su,v= {{ , }, { , }} u u v v
O(n) algorithm for bi-arc H (part 2) Pick a set Y of O( (n/ )) vertices u.a.r. if (u, v) Y2with (f(u), f(v)) Su,vthen reject. else accept. (And check list constraints also.) u v Reject! Su,v= {{ , }, { , }}
Polymorphism : V(H)k V(H) is a polymorphism for LHOM(H) if, for any G, ( ) = ( ) = f1= (v1,1, , v1,n): hom. from G to H f2= (v2,1, , v2,n): hom. from G to H fk= (vk,1, , vk,n): hom. from G to H f = (v 1, , v n) H-hom. from G to H
Bi-arc Graphs admit Majority [FHH03] Let H be a bi-arc graph. Then, LHOM(H) admits majority (of any arity) as its polymorphism. H G majority
When f is -far U V : a maximal set such that f|V \ Uis extendable to a list H-homomorphism |U| n f|(V \ U) + uis not extendable for any u U. Majority implies (f(u), f(v)) Su,vfor some v V \ U. n violating pairs O( (n/ )) vertices is enough to find a violating pair. G v u |U| n f|V \ U
Other results 1. O(1) upper bound for : Give a concrete algorithm. 2. (log n / log log n) lower bound for non- Testing 2SAT requires (log n / loglog n) queries. [FLNRRS02] If H is non- , then we can simulate OR constraint somehow The only place we use list constraints in our proof. reflexive complete or irreflexive complete bipartite bi-arc
Other results 3. (n) lower bound for non- Testing assignments of 3SAT requires (n) queries [BHR06] 3SAT has a gadget-reduction to LHOM(H). Universal algebra is useful to give the reduction. reflexive complete or irreflexive complete bipartite bi-arc
Open Problems Is the picture indeed the case for general CSPs? On-going work: for Boolean CSPs, yes! all CSPs Any useful insight for function property testing? 3SAT easy to count NL 2SAT 3LIN2 2COL
Types vs. computational complexity In universal algebra, CSPs are classified into 5 types. Studied to classify CSPs w.r.t. computational complexity type 3: 2COL L-complete? type 4: 2SAT NL-complete? type 2: 3LIN2 type 5: Horn SAT modpL-complete? P-complete? type 1: 3SAT NP-complete?
