<p>Finding the most likely assignment in the Ising model is equivalent to maximum cut, so forget about minimum cut for a minute.</p>

<p>In the formulation you give for the Ising model, we are trying to maximize $\sum_{ij\in E}\lambda_{ij}x_{ij}$, where $x_{ij}=1$ if $x_i=x_j$ and $x_{ij}=-1$ otherwise.  In maximum cut, we take each edge weight $w$ and try to maximize $\sum_{ij\in E}w_{ij}(-x_{ij})$ -- this is equivalent to maximizing the weight of the cut because the total weight remaining is completely determined by the cut.  So we just want to set $w_{ij}=\lambda_{ij}$ to make an equivalent formulation.</p>

<p>For minimum cut, the problem doesn't make any sense unless you have fields in the Ising model, either local or global.</p>

CC BY-SA 3.0
2015-02-18T01:48:35.823Z
2015-02-18T01:57:00.960Z
2015-02-18T01:57:00.960Z
Andrew D. King
<p><strong>Ising Model</strong></p>

<p>$$
Pr(x; \lambda) = \frac{1}{Z(\lambda)} \exp \left( \sum_{ij \in E} \lambda_{ij} x_{ij} \right)  
$$</p>

<p>In which $\lambda_{ij} \in \mathbb{R}$, and<br>
$$
x_{ij} = 
\begin{cases}
1 &amp; x_i = x_j\\ 
-1 &amp; x_i \neq x_j
\end{cases}
$$</p>

<p>and we are looking for </p>

<p>$$
x^* = \arg\max_x Pr(x; \lambda)
$$</p>

<p>This is proven to be NP-Complete. </p>

<p><strong>Max Cut</strong></p>

<p>Given the graph $G(V,E)$ and non-negative weights $w_{ij} \in E $ the goal is to find the set of vertices $S$ such that we maximize the the weight of edges in the cut $(S, V \setminus S)$ (the edges with the start-point in $S$ and end-point in $V\setminus S$).
More formally, by assuming $w_{ij} = 0, \forall e_{ij} \notin E $, we dote the weight of the cut by $w(S, V \setminus S) = \sum_{i \in S, j \in V \setminus S} w_{i,j}$</p>

<p>This is proven to be NP-Complete. </p>

<p><strong>Min Cut</strong></p>

<p>Exactly like Max-Cut, but the goal is to minimize the weight of the cut. </p>

<p>The problem could be solved in polynomial time using its max-flow formulation. </p>

<p><strong>Problem Statement</strong></p>

<p>In [1] (Page 16, last paragraph) it is mentioned that "finding the most likely assignment in an Ising model is equivalent to a cut problem. For example, if  $\mu \leq 0$, then the MAP assignment for graph $G = (V; E)$ corresponds to the maximum cut of $G$ with edge weights $\lambda$."</p>

<p>I am looking for the direct conversion between the two problems. The 2nd sentences (Started by "For example") also doesn't make sense to me. </p>

<p>On the other hand in Page 20 of [1] (Second paragraph), it is mentioned that: </p>

<p>"In the positive side, MAP inference in Ising models with ferromagnetic potentials, or
positive edge weights, is equivalent to the minimum cut problem, which can be solved in
nearly linear time (Karger, 2000)"</p>

<p>I'd interpret this as, Min Cut (which is Poly-time) is <em>special case</em> of MAP inference. Again, this is a little vague. </p>

<p>[1] <a href="http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf" rel="nofollow">http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf</a></p>

<graph-theory><approximation>
Max-cut equivalence with most likely assignment to an Ising model
Daniel
# Max-cut equivalence with most likely assignment to an Ising model

(Asked by: username_0 on 2013-11-02)

**Ising Model**

$$
Pr(x; \lambda) = \frac{1}{Z(\lambda)} \exp \left( \sum\_{ij \in E} \lambda\_{ij} x\_{ij} \right)
$$

In which $\lambda\_{ij} \in \mathbb{R}$, and  
$$
x\_{ij} =
\begin{cases}
1 & x\_i = x\_j\\
-1 & x\_i \neq x\_j
\end{cases}
$$

and we are looking for

$$
x^\* = \arg\max\_x Pr(x; \lambda)
$$

This is proven to be NP-Complete.

**Max Cut**

Given the graph $G(V,E)$ and non-negative weights $w\_{ij} \in E $ the goal is to find the set of vertices $S$ such that we maximize the the weight of edges in the cut $(S, V \setminus S)$ (the edges with the start-point in $S$ and end-point in $V\setminus S$).
More formally, by assuming $w\_{ij} = 0, \forall e\_{ij} \notin E $, we dote the weight of the cut by $w(S, V \setminus S) = \sum\_{i \in S, j \in V \setminus S} w\_{i,j}$

This is proven to be NP-Complete.

**Min Cut**

Exactly like Max-Cut, but the goal is to minimize the weight of the cut.

The problem could be solved in polynomial time using its max-flow formulation.

**Problem Statement**

In [1] (Page 16, last paragraph) it is mentioned that "finding the most likely assignment in an Ising model is equivalent to a cut problem. For example, if $\mu \leq 0$, then the MAP assignment for graph $G = (V; E)$ corresponds to the maximum cut of $G$ with edge weights $\lambda$."

I am looking for the direct conversion between the two problems. The 2nd sentences (Started by "For example") also doesn't make sense to me.

On the other hand in Page 20 of [1] (Second paragraph), it is mentioned that:

"In the positive side, MAP inference in Ising models with ferromagnetic potentials, or
positive edge weights, is equivalent to the minimum cut problem, which can be solved in
nearly linear time (Karger, 2000)"

I'd interpret this as, Min Cut (which is Poly-time) is *special case* of MAP inference. Again, this is a little vague.

[1] <http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf>

**Tags:** graph-theory, approximation

---

## 1 answers

### Answer by username_1 on 2015-02-18. Score: 4 | Accepted answer

Finding the most likely assignment in the Ising model is equivalent to maximum cut, so forget about minimum cut for a minute.

In the formulation you give for the Ising model, we are trying to maximize $\sum\_{ij\in E}\lambda\_{ij}x\_{ij}$, where $x\_{ij}=1$ if $x\_i=x\_j$ and $x\_{ij}=-1$ otherwise. In maximum cut, we take each edge weight $w$ and try to maximize $\sum\_{ij\in E}w\_{ij}(-x\_{ij})$ -- this is equivalent to maximizing the weight of the cut because the total weight remaining is completely determined by the cut. So we just want to set $w\_{ij}=\lambda\_{ij}$ to make an equivalent formulation.

For minimum cut, the problem doesn't make any sense unless you have fields in the Ising model, either local or global.


---

