<p>Here's a dynamic-programming algorithm that is fast enough to solve a given 18 x 18 grid in about 20 minutes.  The algorithm is a modification of the algorithm from <a href="https://scholar.google.com/scholar?cluster=17481083003090990241&amp;hl=en&amp;as_sdt=1,22" rel="nofollow noreferrer">this paper</a> for counting independent sets in a given <span class="math-container">$m\times n$</span> grid.</p>

<p>Fix the input: the grid dimension <span class="math-container">$n \times n$</span> and the values <span class="math-container">$\lambda_{ij}$</span> for <span class="math-container">$i,j\in\{1,\ldots,n\}$</span>.  Represent each independent set in the grid by its 0/1 incidence matrix <span class="math-container">$M$</span> where <span class="math-container">$M_{ij}$</span> is 1 if the grid vertex <span class="math-container">$(i,j)$</span> is in the independent set, and 0 otherwise.
Let <span class="math-container">$S_n$</span> denote the set of 0/1 vectors of dimension <span class="math-container">$n$</span> with no two consecutive 1's.  (I think the size of <span class="math-container">$S_n$</span> is the <span class="math-container">$n+2$</span>nd Fibonacci number, so <span class="math-container">$|S_{18}|=6765$</span>.)</p>

<p>An <span class="math-container">$n\times n$</span> 0/1 matrix <span class="math-container">$M$</span> represents an independent set if and only if the following two conditions hold:</p>

<ol>
<li>Each row <span class="math-container">$M_i$</span> of <span class="math-container">$M$</span> is in <span class="math-container">$S_n$</span>.</li>
<li>Every two consecutive rows <span class="math-container">$M_i$</span> and <span class="math-container">$M_{i+1}$</span> are <em>compatible</em>, meaning that there is no <span class="math-container">$j$</span> such that <span class="math-container">$M_{ij}$</span> and <span class="math-container">$M_{i+1,j}$</span> are both 1.</li>
</ol>

<p>Construct directed acyclic graph <span class="math-container">$G=(V,E)$</span> where <span class="math-container">$V$</span> and <span class="math-container">$E$</span> are defined as follows.  The vertex set <span class="math-container">$V$</span> contains source and sink vertices <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, and, for each row <span class="math-container">$i\in\{1,\ldots,n\}$</span> and <span class="math-container">$x\in S_n$</span>, a vertex <span class="math-container">$v(i, x)$</span>.  The edge set <span class="math-container">$E$</span> contains the following edges: for each <span class="math-container">$x\in S_n$</span>, an edge from <span class="math-container">$s$</span> to <span class="math-container">$v(1, x)$</span> and an edge from <span class="math-container">$v(n, x)$</span> to <span class="math-container">$t$</span>; for each <span class="math-container">$i\in\{1,\ldots,n-1\}$</span>, and each <span class="math-container">$x\in S_n$</span>, edges from <span class="math-container">$v(i, x)$</span> to <span class="math-container">$v(i+1, y)$</span> for every <span class="math-container">$y\in S_n$</span> that is compatible with <span class="math-container">$x$</span>.</p>

<p>The <span class="math-container">$s$</span>-<span class="math-container">$t$</span> paths in <span class="math-container">$G$</span> correspond bijectively to the independent sets in the grid.  Each <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path is of the form <span class="math-container">$(s, v(1, x_1), v(2, x_2), \ldots, v(n, x_n), t)$</span>, corresponding to the independent set whose incidence matrix <span class="math-container">$M$</span> has <span class="math-container">$M_i = x_i$</span> (that is, the <span class="math-container">$i$</span>th row of <span class="math-container">$M$</span> is <span class="math-container">$x_i$</span>).</p>

<p>Assign weights to the vertices of <span class="math-container">$G$</span> as follows.  Give <span class="math-container">$s$</span> and <span class="math-container">$t$</span> weight <span class="math-container">$w(s)=w(t)=1$</span>.  Give each vertex <span class="math-container">$v(i, x)$</span> weight <span class="math-container">$w(v(i,x)) = \prod_{j:x_j=1} \lambda_j$</span>.  Then, for any <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path in <span class="math-container">$G$</span>, the product of the weights of the vertices on that path is the product of the <span class="math-container">$\lambda_{ij}$</span>'s of the vertices in the corresponding independent set in the grid.</p>

<p>Now, for every vertex <span class="math-container">$v$</span> in <span class="math-container">$G$</span>, define <span class="math-container">$P(v)$</span> to be the sum, over all paths from <span class="math-container">$s$</span> to <span class="math-container">$v$</span>, of the product of the weights of the vertices on the path.  Define <span class="math-container">$P'(v)$</span> to be the sum, over all paths from <span class="math-container">$v$</span> to <span class="math-container">$t$</span>, of the product of the weights of the vertices on the path except for <span class="math-container">$v$</span>.  Compute these two quantities for every vertex in <span class="math-container">$G$</span>.  This can be done in time linear in the size of <span class="math-container">$G$</span> (assuming constant-time exact arithmetic) using a standard dynamic-programming approach.  E.g. use <span class="math-container">$P(s) = 1$</span> and, for <span class="math-container">$v\ne s$</span>, 
<span class="math-container">$$P(v) = w(v)\sum_{u: (u, v)\in E} P(u).$$</span></p>

<p>For each vertex <span class="math-container">$v$</span> in <span class="math-container">$G$</span>, define <span class="math-container">$Q(v) = P(v)P'(v)$</span>.  This is the sum, over all <span class="math-container">$s$</span>-<span class="math-container">$t$</span> paths in <span class="math-container">$G$</span> that go through <span class="math-container">$v$</span>, of the product of the weights of the edges on the path.  Then <span class="math-container">$Q(s)$</span> is the sum, over all independent sets in the grid, of the product of the <span class="math-container">$\lambda$</span>'s for the vertices in the independent set. For each vertex <span class="math-container">$v(i, x)$</span>, then, <span class="math-container">$Q(v(i,x))$</span> is the sum, over all independent sets <span class="math-container">$M$</span> in the grid whose <span class="math-container">$i$</span>th row <span class="math-container">$M_i$</span> is <span class="math-container">$x$</span>, of the product of the <span class="math-container">$\lambda$</span>'s for the vertices in the independent set.</p>

<p>Finally, for each vertex <span class="math-container">$g=(i,j)$</span> in the grid graph, compute <span class="math-container">$p_g$</span> as the sum, over all <span class="math-container">$x\in S_n$</span> such that <span class="math-container">$x_j = 1$</span>, of <span class="math-container">$Q(v(i, x))$</span>, divided by <span class="math-container">$Q(s)-1$</span>.  (Subtract 1 as the problem specification doesn't count the empty set in the denominator.)</p>

<hr>

<p>For the instance with <span class="math-container">$n=18$</span> and each <span class="math-container">$\lambda_{ij}=1$</span>, this <a href="https://repl.it/@nealyoung/OvercookedMadCarat" rel="nofollow noreferrer">Python script</a> computed the answer in about 17 minutes.  (The graph <span class="math-container">$G$</span> had about 122K vertices and 159M edges.)  For non-uniform lambdas, in the probability calculations, you'll need to take some care regarding arithmetic precision.  (If you want exact answers, you'll need to use rational arithmetic.  You could compute close approximations using floating-point arithmetic, but then you'll probably have to be careful about the order in which the sums are performed.)</p>

<p>Here's the output of the script for the instance with <span class="math-container">$n=7$</span> and each <span class="math-container">$\lambda_{ij}=1$</span>. Each entry of the 7 x 7 matrix below is the probability for the corresponding vertex of the grid, times the denominator (which for <span class="math-container">$\lambda_{ij}=1$</span> is the number of non-empty independent sets in the grid).</p>

<pre><code>N = 7

denominator = 1280128949

402968942 298303063 333041917 316303258 333041917 298303063 402968942
298303063 296843520 279776968 292351405 279776968 296843520 298303063
333041917 279776968 296033698 285917681 296033698 279776968 333041917
316303258 292351405 285917681 293815906 285917681 292351405 316303258
333041917 279776968 296033698 285917681 296033698 279776968 333041917
298303063 296843520 279776968 292351405 279776968 296843520 298303063
402968942 298303063 333041917 316303258 333041917 298303063 402968942
</code></pre>

CC BY-SA 4.0
2019-01-05T15:44:23.817Z
2019-01-08T23:43:13.697Z
2019-01-08T23:43:13.697Z
Neal Young
<p>Suppose I have a distribution over independent sets on an <span class="math-container">$n\times n$</span> grid where the probability of independent set occupying nodes <span class="math-container">$(i_1,j_1),\ldots,(i_k,j_k)$</span> is proportional to <span class="math-container">$\lambda_{i_1,j_1}\cdot \lambda_{i_2,j_2} \cdots\lambda_{i_k,j_k}$</span>. Let <span class="math-container">$p_v$</span> be the probability that vertex <span class="math-container">$v$</span> in this grid is occupied, how do I compute <span class="math-container">$p_v$</span> for every vertex <span class="math-container">$v$</span> in the grid?</p>

<p>For instance, when <span class="math-container">$n=2$</span>, the four probabilities are the ratios below
<img src="https://i.sstatic.net/LNffd.png"></p>

<p>Motivation: comparing accuracy of "correlation decay" based approximate counting with exact for some not-too-large graphs</p>

<p><b>Clarification 11/6</b>: This is the same <span class="math-container">$p_v$</span> as in the first formula of page 3 of [<a href="http://dimacs.rutgers.edu/~dror/pubs/ind_from_tree.pdf" rel="nofollow noreferrer">Weitz, 2006</a>]</p>

CC BY-SA 2.5
2010-11-05T12:12:39.557Z
Just checking: does this mean that if $k=n=2$ and $\lambda_{i,1}=\lambda_{i,2}$, then $\lambda_{1,1}^2 + 4\lambda_{1,1}\lambda_{2,1} + \lambda_{2,1}^2 = 1$?
András Salamon
CC BY-SA 2.5
2010-11-05T19:20:25.247Z
It's more convenient to divide by sum of all weights of independent sets to get probability rather than by restricting lambdas, added clarification
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-06T05:56:16.717Z
Not sure if this helps, but you take the compliment of the graph, you're looking at cliques. Does this have something to do with the Hammersley–Clifford?
gabgoh
CC BY-SA 2.5
2010-11-06T06:31:52.953Z
No relation with Hammersley-Clifford. Not sure I understand what the clique connection is, but there is connection with counting matchings since each matching on G corresponds to an independent set on line-graph of G
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-06T08:35:30.930Z
This will likely be of no help then, but the connection of IS to Clique is straightforward, if you subtract the edges current graph from a fully connected graph (take the compliment) the independent sets become cliques. However, seeing enumerating all Independent Sets is NP-Complete (in fact, just finding the largest IS is NP-Complete), calculating the normalizing constant exactly seems intractable? Am I missing something?
gabgoh
CC BY-SA 2.5
2010-11-06T09:18:09.657Z
Chromatic polynomial has been computed for 18x18 grids, so I'm hoping this problem can also be solved for this size grid
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-06T18:53:58.500Z
I found this while doing some googling. Is this what you're looking for? http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
gabgoh
CC BY-SA 2.5
2010-11-06T19:35:33.610Z
I don't see how maximal cliques help -- there are 6 independent sets in the example above while complement of the graph has 2 maximal cliques.
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-06T20:19:29.860Z
I think the algorithm actually calculates all cliques in the graph recursively. This includes the 2 maximal cliques of size to and the 4 cliques of size 1, which add up to 6.
gabgoh
<ds.algorithms><machine-learning>
Solving "all-marginals" problem for independent sets on grid
Yaroslav Bulatov
# Solving "all-marginals" problem for independent sets on grid

(Asked by: username_0 on 2010-11-05)

Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i\_1,j\_1),\ldots,(i\_k,j\_k)$ is proportional to $\lambda\_{i\_1,j\_1}\cdot \lambda\_{i\_2,j\_2} \cdots\lambda\_{i\_k,j\_k}$. Let $p\_v$ be the probability that vertex $v$ in this grid is occupied, how do I compute $p\_v$ for every vertex $v$ in the grid?

For instance, when $n=2$, the four probabilities are the ratios below
![](https://i.sstatic.net/LNffd.png)

Motivation: comparing accuracy of "correlation decay" based approximate counting with exact for some not-too-large graphs

**Clarification 11/6**: This is the same $p\_v$ as in the first formula of page 3 of [[Weitz, 2006](http://dimacs.rutgers.edu/~dror/pubs/ind_from_tree.pdf)]

**Tags:** ds.algorithms, machine-learning

> **Comments:**
> **username_1**: Just checking: does this mean that if $k=n=2$ and $\lambda_{i,1}=\lambda_{i,2}$, then $\lambda_{1,1}^2 + 4\lambda_{1,1}\lambda_{2,1} + \lambda_{2,1}^2 = 1$?  
> **username_0**: It's more convenient to divide by sum of all weights of independent sets to get probability rather than by restricting lambdas, added clarification  
> **username_2**: Not sure if this helps, but you take the compliment of the graph, you're looking at cliques. Does this have something to do with the Hammersley–Clifford?  
> **username_0**: No relation with Hammersley-Clifford. Not sure I understand what the clique connection is, but there is connection with counting matchings since each matching on G corresponds to an independent set on line-graph of G  
> **username_2**: This will likely be of no help then, but the connection of IS to Clique is straightforward, if you subtract the edges current graph from a fully connected graph (take the compliment) the independent sets become cliques. However, seeing enumerating all Independent Sets is NP-Complete (in fact, just finding the largest IS is NP-Complete), calculating the normalizing constant exactly seems intractable? Am I missing something?  
> **username_0**: Chromatic polynomial has been computed for 18x18 grids, so I'm hoping this problem can also be solved for this size grid  
> **username_2**: I found this while doing some googling. Is this what you're looking for? http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm  
> **username_0**: I don't see how maximal cliques help -- there are 6 independent sets in the example above while complement of the graph has 2 maximal cliques.  
> **username_2**: I think the algorithm actually calculates all cliques in the graph recursively. This includes the 2 maximal cliques of size to and the 4 cliques of size 1, which add up to 6.  

---

## 1 answers

### Answer by username_3 on 2019-01-05. Score: 1

Here's a dynamic-programming algorithm that is fast enough to solve a given 18 x 18 grid in about 20 minutes.  The algorithm is a modification of the algorithm from this paper for counting independent sets in a given $m\times n$ grid.
Fix the input: the grid dimension $n \times n$ and the values $\lambda_{ij}$ for $i,j\in\{1,\ldots,n\}$.  Represent each independent set in the grid by its 0/1 incidence matrix $M$ where $M_{ij}$ is 1 if the grid vertex $(i,j)$ is in the independent set, and 0 otherwise.
Let $S_n$ denote the set of 0/1 vectors of dimension $n$ with no two consecutive 1's.  (I think the size of $S_n$ is the $n+2$nd Fibonacci number, so $|S_{18}|=6765$.)
An $n\times n$ 0/1 matrix $M$ represents an independent set if and only if the following two conditions hold:

Each row $M_i$ of $M$ is in $S_n$.
Every two consecutive rows $M_i$ and $M_{i+1}$ are compatible, meaning that there is no $j$ such that $M_{ij}$ and $M_{i+1,j}$ are both 1.

Construct directed acyclic graph $G=(V,E)$ where $V$ and $E$ are defined as follows.  The vertex set $V$ contains source and sink vertices $s$ and $t$, and, for each row $i\in\{1,\ldots,n\}$ and $x\in S_n$, a vertex $v(i, x)$.  The edge set $E$ contains the following edges: for each $x\in S_n$, an edge from $s$ to $v(1, x)$ and an edge from $v(n, x)$ to $t$; for each $i\in\{1,\ldots,n-1\}$, and each $x\in S_n$, edges from $v(i, x)$ to $v(i+1, y)$ for every $y\in S_n$ that is compatible with $x$.
The $s$-$t$ paths in $G$ correspond bijectively to the independent sets in the grid.  Each $s$-$t$ path is of the form $(s, v(1, x_1), v(2, x_2), \ldots, v(n, x_n), t)$, corresponding to the independent set whose incidence matrix $M$ has $M_i = x_i$ (that is, the $i$th row of $M$ is $x_i$).
Assign weights to the vertices of $G$ as follows.  Give $s$ and $t$ weight $w(s)=w(t)=1$.  Give each vertex $v(i, x)$ weight $w(v(i,x)) = \prod_{j:x_j=1} \lambda_j$.  Then, for any $s$-$t$ path in $G$, the product of the weights of the vertices on that path is the product of the $\lambda_{ij}$'s of the vertices in the corresponding independent set in the grid.
Now, for every vertex $v$ in $G$, define $P(v)$ to be the sum, over all paths from $s$ to $v$, of the product of the weights of the vertices on the path.  Define $P'(v)$ to be the sum, over all paths from $v$ to $t$, of the product of the weights of the vertices on the path except for $v$.  Compute these two quantities for every vertex in $G$.  This can be done in time linear in the size of $G$ (assuming constant-time exact arithmetic) using a standard dynamic-programming approach.  E.g. use $P(s) = 1$ and, for $v\ne s$, 
$$P(v) = w(v)\sum_{u: (u, v)\in E} P(u).$$
For each vertex $v$ in $G$, define $Q(v) = P(v)P'(v)$.  This is the sum, over all $s$-$t$ paths in $G$ that go through $v$, of the product of the weights of the edges on the path.  Then $Q(s)$ is the sum, over all independent sets in the grid, of the product of the $\lambda$'s for the vertices in the independent set. For each vertex $v(i, x)$, then, $Q(v(i,x))$ is the sum, over all independent sets $M$ in the grid whose $i$th row $M_i$ is $x$, of the product of the $\lambda$'s for the vertices in the independent set.
Finally, for each vertex $g=(i,j)$ in the grid graph, compute $p_g$ as the sum, over all $x\in S_n$ such that $x_j = 1$, of $Q(v(i, x))$, divided by $Q(s)-1$.  (Subtract 1 as the problem specification doesn't count the empty set in the denominator.)

For the instance with $n=18$ and each $\lambda_{ij}=1$, this Python script computed the answer in about 17 minutes.  (The graph $G$ had about 122K vertices and 159M edges.)  For non-uniform lambdas, in the probability calculations, you'll need to take some care regarding arithmetic precision.  (If you want exact answers, you'll need to use rational arithmetic.  You could compute close approximations using floating-point arithmetic, but then you'll probably have to be careful about the order in which the sums are performed.)
Here's the output of the script for the instance with $n=7$ and each $\lambda_{ij}=1$. Each entry of the 7 x 7 matrix below is the probability for the corresponding vertex of the grid, times the denominator (which for $\lambda_{ij}=1$ is the number of non-empty independent sets in the grid).
N = 7

denominator = 1280128949

402968942 298303063 333041917 316303258 333041917 298303063 402968942
298303063 296843520 279776968 292351405 279776968 296843520 298303063
333041917 279776968 296033698 285917681 296033698 279776968 333041917
316303258 292351405 285917681 293815906 285917681 292351405 316303258
333041917 279776968 296033698 285917681 296033698 279776968 333041917
298303063 296843520 279776968 292351405 279776968 296843520 298303063
402968942 298303063 333041917 316303258 333041917 298303063 402968942


---

