Computing the partition function for graph homomorphisms (Q681595): Difference between revisions

Counting graph homomorphisms is a well-known and difficult problem that simultaneously generalises other important combinatorial problems such as counting graph colourings or independent sets. Edge-coloured graph homomorphisms generalise the notion even further, by insisting that homomorphisms preserve edge colours (the original case arises when all edges have the same colour). The authors define the edge-coloured graph homomorphism partition function by \[ Q_G(B)=\sum_{\phi:V\rightarrow\{1,\dots,k\}}\prod_{\{u,v\}\in E}b^{uv}_{\phi(u)\phi(v)} \] where the sum is over all maps \(\phi\) from the vertex set of \(G\) to \(\{1,\dots,k\}\) and the product is over all edges of \(G\). Their main result is a deterministic algorithm that (under certain conditions) approximates \(Q_G(B)\) within a small relative error in quasi-polynomial time. For a closely related paper by the same authors, see [J. Comb. Theory, Ser. A 137, 1--26 (2016; Zbl 1325.05114)].