Computational Complexity for Real Valued Graph Parameters

摘要

A real-valued graph parameter is a function/ which maps (possibly weighted) graphs into the real number R such that two isomorphic (weighted) graphs receive the same value. Typical examples are graph polynomials F{G;X) ∈ R[X] in k indeterminates, partition functions and Holant functions. The talk is based [1, 2]. We address the following issues: (i) How to choose the computational model? the complexity of evaluating F(G; a) The weighted graphs are best modeled as metafinite structures. In our discussion computations over the reals R are performed in unit cost in the computation model of Blum-Shub-Smale (BSS).