found by α**-pass. We have:**

F(v**ˆ) = max**
$$\operatorname*{max}_{1\leq\alpha\leq|\mathcal{R}^{\prime}p|,1\leq k\leq n}F({\hat{\mathbf{v}}}^{\alpha k})$$
$\frac{7}{4}$ . 
$$\begin{array}{l}{{\mathrm{C}({\hat{\mathbf{v}}}^{\beta\ell})}}\\ {{f_{\beta}(\ell)}}\end{array}$$

| ≥   | F(vˆ βℓ)            |
|-----|---------------------|
| =   | ψ(vˆ βℓ) + C(vˆ βℓ) |
| ≥   | ψ(vˆ βℓ) + fβ(ℓ)    |
| =   | ψ(vˆ βℓ) + C(v ∗ )  |
| ≥   | ψ(v ∗ ) + C(v ∗ )   |
| =   | F(v ∗ )             |

The second and third inequalities follows from Claims 6.2 and 6.1 respectively.

Thus, α**-pass finds the optimal assignment for the** max family of potentials in O(Rn log n**) time. We now**
move on to sum **potentials.**

## 6.2 Clique Inference For Sum **Potentials**

We will mainly focus on the Potts potential, which is arguably the most popular member of the sum **family.**
Potts potential is given by C(v) = λPv n 2v.

When λ < 0, the clique edges prefer the two end points to take different values. With negative λ**, our objective**
function F(v) becomes concave and its maximum can be easily found using a relaxed **quadratic program followed**
by an optimal rounding step as suggested in [21]. We therefore do not discuss this case further. The more interesting case is when λ is positive. We show that finding v∗ **now becomes NP-hard.**
Theorem 6.2. *When C*(v) = λPv n 2v**, λ >** 0, finding the MAP assignment is NP-hard.

Proof. Let R , |R′p|**. We prove hardness by reducing from the NP-complete** *exact cover by 3-sets* **problem [19]**
of deciding if exactly n 3 of R subsets S1, . . . , SR of 3 elements each from U = {e1, . . . en} can cover U**. We let**
elements correspond to vertices and sets to values. Assign ψiv = 2nλ if ei ∈ Sv **and 0 otherwise. MAP score will**
be (2n 2 + 32 n 3
)λ **iff we can find an exact cover.**
The above proof establishes that there cannot be an algorithm that is polynomial in both n and R**. But we**
have not ruled out algorithms with complexity that is polynomial in n but exponential in R**, say of the form**
O(2Rn c**) for a constant** c.

We next propose approximation schemes. Unlike for general graphs where the Potts model is approximable only within a factor of 12
[5, 12], we show that for cliques the Potts model can be approximated to within a factor of 13 15 ≈ 0.86 using the α**-pass algorithm. We first present an easy proof for a weaker bound of** 45 and then move on to a more detailed proof for the 13 15 bound. Recall that the optimal assignment is v∗ **and the assignment**
output by α**-pass is** vˆ.

## Theorem 6.3. F(Vˆ) ≥ 45 F(V∗).

Proof. Without loss of generality assume that the counts in v∗ are n1 ≥ n2 ≥ . . . ≥ nR**, where** R = |R′
P
p|**. Then**
v n 2v ≤ n1Pv nv = nn1.

F(vˆ) ≥ F(vˆ
1n1
) = ψ(vˆ
1n1
**) + C(**vˆ
1n1
)

$\mathrm{m}$ Claim 6.1). 
 #### Tom  $\text{Claim}$. 
≥ ψ(v
∗**) + C(**vˆ
1n1
**) (from Claim 6.1)**

≥ ψ(v
$$\begin{array}{l l}{{\psi(\mathbf{v}^{*})+\mathrm{C}(\mathbf{v}^{*\times1})}}&{{\mathrm{(from~Claim)}}}\\ {{\psi(\mathbf{v}^{*})+\lambda n_{1}^{2}}}&{{\mathrm{(since~}\lambda>0)}}\\ {{\psi(\mathbf{v}^{*})+\mathrm{C}(\mathbf{v}^{*})-\lambda n_{1}n+\lambda n_{1}^{2}}}\\ {{F(\mathbf{v}^{*})-\lambda n^{2}/4}}\end{array}$$
≥ ψ(v ≥ F(v Now consider the two cases where F(v∗) ≥
5 4 λn2 and F(v∗) <
5 4 λn2**. For the first case we get from above that**
F(vˆ) ≥ F(v∗) − λn2/4 ≥ 45 F(v∗). For the second case, we know that the score F(vˆmn**) where we assign all**
vertices the last value is at least λn2 **and thus** F(vˆ) ≥
4 5 F(v∗).