Question 1. Yes, efficient algorithm for Cor exists for graphs of low tree-width
Cast this in the framework of probabilistic graphical models and then use the junction tree algorithm, which scales exponentially in tree-width of the graph.
In particular, let $G$ be a graph over $n$ vertices with edges $E$. Let $x in [1,2,ldots, k]^n$. Define probability distribution over $x$ as follows
$$p(x)=exp{(sum_{(ij)in E} mathbf{I}(x_ine x_j))}/Z$$
Where $Z$ is a constant chosen to make this a valid probability distribution.
Then
$$text{Cor}(G,k,u,v)=sum_{c=1}^k p(x_u=c,x_v=c)$$
Computing p in the formula above in graphs that are not trees is not trivial, but can be done efficiently if the tree-width is low, look at page 370 of Koller's "Probabilistic Graphical Models" for details on that particular form of query.
Question 2. Yes, for graphs with low degree or large number of colors. For instance, here the authors conjecture that colorings on graphs with degree at most k and at least k+1 number of colors exhibits "strong spatial mixing", which would imply that the algorithm they give to approximate the marginals could also give a guaranteed approximation to your problem in polynomial time
No comments:
Post a Comment