Approximate Counting via correlation Decay on Planar Graphs Yitong Yin Nanjing University Chihao Zhang Shanghai Jiaotong University
Approximate Counting via Correlation Decay on Planar Graphs Yitong Yin Nanjing University Chihao Zhang Shanghai Jiaotong University
Holant Problems (Valiant 2004) instance: =(G(V,E),fuvEv) graph G=(V,目 edges:variables (domain [q]) vertices:constraints(arity=degree) symmetric f:[g]deg()C configuration (solution,coloring,..):[ holant(counting): holant(2)=>II fu (lE()) o∈[g]Ev∈V #matchings: q-2 E{0,1f=AT-MOST-ONE
Holant Problems edges: variables (domain [q]) vertices: constraints (arity=degree) graph G=(V,E) holant (counting): PWTIV\() = [q]E vV fv |E(v) = (G(V,E), {fv}vV ) fv (Valiant 2004) configuration (solution, coloring, ...): instance: fv : [q] LMO(v) C #matchings: q=2 {0, 1} fv At-Most-One E [q] E symmetric
Holant problem:Holant(9,F) graph family function family mptR-G,e）wm{食 output:holant()=>f(()) o∈[g]Ev∈V spin system /graph homomorphism(G.H.): F={f:[ga→C,d≤2}U{=} ●S,#VC .#q-colorings,#H-colorings .hardcore/lsing/Potts models,MRF G=(V,目 spin model holant
Holant problem: PWTIV\() = [q]E vV fv |E(v) = (G(V,E), {fv}vV ) 0WTIV\(G, F) graph family function family input: output: G G fv F with F = {f : [q] d C, d 2} {=} spin system / graph homomorphism (G.H.): • #IS, #VC • #q-colorings, #H-colorings • hardcore/Ising/Potts models, MRF f G=(V,E) V E = = = = f f f f f spin model holant
Holant Problems Holant problem:Holant(G,F) graph family function family characterize the tractability of Holant(g,F)by g and F Bad news:for general/planar G,almost all nontrivial F:#P-hard (Dyer-Greenhill'00,Bulatov-Grohe'05,Dyer-Goldberg'07,Bulatov'08,Goldberg-Grohe-Jerrum'10,Cai-Chen'10, Cai-Chen-Lu'10,Cai-Lu-Xia'10,Dyer-Richerby'10,Dyer-Richerby'11,Cai-Chen'12,Cai-Lu-Xia'13) Good news:tractable if g is tree,F is Spin or Matching (arity≤2'and=）(At-Most-One) Our result: g is planar (locally like a tree) F is regular li/nEPFAS) correlation decay local info is enough)
Holant Problems Holant problem: 0WTIV\(G, F) graph family function family Bad news: for general/planar , almost all nontrivial : #P-hard (Dyer-Greenhill’00, Bulatov-Grohe’05, Dyer-Goldberg’07, Bulatov’08, Goldberg-Grohe-Jerrum’10, Cai-Chen’10, Cai-Chen-Lu’10, Cai-Lu-Xia’10, Dyer-Richerby’10, Dyer-Richerby’11, Cai-Chen’12, Cai-Lu-Xia’13) G F Good news: tractable if is G tree, is F Spin or Matching (arity≤2 and =) (At-Most-One) Our result: correlation decay G is planar F is regular (local info is enough) (locally like a tree) (like spin/matching) FPTAS characterize the tractability of by and 0WTIV\(G, F) G F
Gibbs measure =(G(V;E),{fu}vEv) f:[g]ego）→R≥o holant(()=Πf,(oE() o∈[glEv∈V Gibbs measure:Pr()= Πevf(oE(w) holant marginal probability:E[a)4 ACE Pr(a(e)=cA) self compute reduction FPTAS for Pr(o(e)=c|TA)±是 holant(S) in time poly(n)
Gibbs Measure PWTIV\() = [q]E vV fv |E(v) = (G(V,E), {fv}vV ) Gibbs measure: marginal probability: fv : [q] LMO(v) R0 8Z() = vV fv(|E(v)) PWTIV\ A E FPTAS for PWTIV\() selfreduction 8Z((e) = c | A) A [q] A compute in time 8Z((e) = c | A) ± 1 n XWTa (n)