Counting with Bounded Treewidth Yitong Yin Nanjing University Joint work with Chihao Zhang (SJTU→)
Counting with Bounded Treewidth Yitong Yin Nanjing University Joint work with Chihao Zhang (SJTU ⟶ ?)
Spin Systems vertices are variables (domain [gl) graph G=(V,E) edge are constraints: A(u,v) Ve=(u,y)∈E Ae:[gl×[gl→C configuration o∈[g]'Y partition function: Z=∑ΠAe(ou,o) o∈[g]Ve=(u,v)eE
Spin Systems vertices are variables (domain [q]) edge are constraints: graph G=(V,E) configuration partition function: 2 [q] V A(u,v) Z = X 2[q]V Y e=(u,v)2E Ae(u, v) Ae : [q] ⇥ [q] ! C ∀e=(u,v) ∈ E
Holant Problem edges are variables (domain [gl) graph G=(V,E) vertices are constraints (signatures) nu∈V,fu:[]deg(w)C configuration o∈[glE holant=If(oE()） o∈[g]Ev∈V E(v)=(e1,.,ed) incident edges of v q"configurations where m=lEl
Holant Problem edges are variables (domain [q]) vertices are constraints (signatures) fv [q] E configuration holant = X 2[q]E Y v2V fv |E(v) 8v 2 V, fv : [q] deg(v) ! C E(v) = (e1, ... , ed) incident edges of v qm configurations where m=|E| graph G=(V,E)
incidence graph B(V,E,F) graph G=(V,E) 2 EQ 3 Ae E o∈[glV where w(o)=ΠAe(ou,0) e=(u,v)∈E B0z0= 1 c1=··=xd otherwise Z=∑w(a) holant=∑[f(alr) o∈[qV o∈[glFv∈VUE
1 2 3 4 5 a b c d e f incidence graph B(V,E,F) V E 8 2 [q] V w() = Y e=(u,v)2E Ae(u, v) F EQ Ae EQ(x1,...,xd) = ( 1 x1 = ··· = xd 0 otherwise where Z = X 2[q]V w() holant = X 2[q]F Y v2V [E fv |F (v) graph G=(V,E) 1 2 3 4 5 a b c d e f
9=2 graph G=(V,E) Boolean symmetric f:10,1dC f=[6,f,,jf闭 where fi=x)for∑xi=i counting matchings: at every vertex vev, =[1,1,0,0.,0] the at-most-one function holant ∑Π1,1,0，.…，0(oE@） o∈{0,1}Ev∈V
f = [f0, f1 ,..., fd] where fi = f(x) for Σjxj = i f : {0, 1} Boolean symmetric d ! C at every vertex v∈V, fv = [1, 1, 0, 0..., 0] counting matchings: the at-most-one function q=2 holant = X 2{0,1}E Y v2V [1, 1, 0,..., 0] |E(v) graph G=(V,E) fv
9=2 graph G=(V,E) Boolean symmetric f:10,1dC f=[6,f,,jf where fi=x)for∑xi=i counting perfect matchings: at every vertex veV, =[0,1,0,0,0] the exact-one function holant ∑I[0,1,0,0,,0(oE()） o∈{0,1}Ev∈V
f : {0, 1} Boolean symmetric d ! C at every vertex v∈V, fv = [0, 1, 0, 0..., 0] counting perfect matchings: the exact-one function q=2 holant = X 2{0,1}E Y v2V [0, 1, 0, 0,..., 0] |E(v) f = [f0, f1 ,..., fd] where fi = f(x) for Σjxj = i graph G=(V,E) fv
9=2 graph G=(V,E) Boolean symmetric f:10,1dC f=[6,f,,fl where fi=x)for∑xi=i counting edge covers: at every vertex vev, f=[0,1,1,1,1] the at-least-one function holant Π0,1,1,1，，1(gEo） o∈{0,1}Ev∈V
f : {0, 1} Boolean symmetric d ! C at every vertex v∈V, fv = [0, 1, 1, 1..., 1] counting edge covers: the at-least-one function q=2 f = [f0, f1 ,..., fd] where fi = f(x) for Σjxj = i graph G=(V,E) fv holant = X 2{0,1}E Y v2V [0, 1, 1, 1,..., 1] |E(v)
9=2 graph G=(V,E) Boolean symmetric f:10,1dC f=[fo,f......fal where fi=f代x)forw=i =[1,u,1,4,1,4,…] subgraphs world (Jerrum-Sinclair'90): Z=∑udd(x) XCE odd(X)=#odd-degree vertices in X holant ∑I[1,4,1,4(oE() o∈{0,1}Ev∈V
fv = [1, μ, 1, μ, 1, μ, ...] odd(X) = #odd-degree vertices in X subgraphs world ( Jerrum-Sinclair’90 ): graph G=(V,E) Z = X X✓E µodd(X) holant = X 2{0,1}E Y v2V [1, µ, 1, µ, . . .] |E(v) f : {0, 1} Boolean symmetric d ! C q=2 f = [f0, f1 ,..., fd] where fi = f(x) for Σjxj = i fv
incidence graph B(V,E,F) graph G=(V,E) 0o.1,09 [0,1,0] di12 d/2 counting Eulerian orientations: holant ∑ΠQ01,0,0(olro） o(e1)≠o(e2】 E10,1)F vEV deg(v)/2 deg(v)/2 e=(e1,e2)EE
incidence graph B(V,E,F) V E F [0, 1, 0] [0,...,0,1,0,...,0] counting Eulerian orientations: holant = X 2{0,1}F Y v2V [0,..., 0 | {z } deg(v)/2 , 1, 0,..., 0 | {z } deg(v)/2 ] |F (v) Y e=(e1,e2)2E [(e1) 6= (e2)] graph G=(V,E) n dv/2 n dv/2
Treewidth tw(G):treewidth of graph G measures how much a graph is like a tree: ●tw(tree)=l tw(kxk grid)=k ●tw(Kn)=n-1 g-state spin system on G with n vertices: ● Courcelle's Theorem:f(q,tw)poly(n)time [Courcelle'90] Junction-tree belief propagation:qo(poly(n)time Holant(tensor networks)on Gwith O(1)max-degree:qo(twpoly(n) [Markov,Shi'08][Arad,Landau'10]
Treewidth • tw(G): treewidth of graph G • measures how much a graph is like a tree: • tw(tree) = 1 • tw(k×k grid) = k • tw(Kn) = n-1 • q-state spin system on G with n vertices: • Courcelle’s Theorem: f(q, tw)poly(n) time [Courcelle’90] • Junction-tree belief propagation: qO(tw)poly(n) time • Holant (tensor networks) on G with O(1) max-degree: qO(tw)poly(n) [Markov, Shi’08] [Arad, Landau’10]