Theorem I If F is regular,then holant(G,{fvvF) can be computed in time poly().2(treewidth(G)) tree-decomposition: B a tree of"bags"of vertices: I.Every vertex is in some bag. E 2.Every edge is in some bag. 3.If two bags have a same vertex, A B B then all bags in the path between them have that vertex. width:max bag size-1 treewidth:width of optimal H tree decompositiontree-decomposition: 1.Every vertex is in some bag. 2.Every edge is in some bag. 3.If two bags have a same vertex, then all bags in the path between them have that vertex. a tree of “bags” of vertices: width: max bag size -1 treewidth: width of optimal tree decomposition If F is regular, then PWTIV\(G, {fv}v￾V ￾ F) can be computed in time Theorem I XWTa(|V |) · 2O(\ZMM_QL\P(G))