# Hardness of Happynet problem

I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic.

What's the reason for this? Are there any related problems, that get better attention?

The Happynet problem is related to minimizing the energy in a Hopfield net.

The problem is defined as follows: Given a graph $G = (V,E)$ and edge weights $w: E \to \mathbb{Z}$, find a function $s: V \to \{-1,1\}$ such that for all $v \in V$, the sum $$\sum_{u: \{v,u\} \in E} s(v)s(u)w(\{u,v\})$$ is non-negative.

Put otherwise, the task is to find a cut in an edge-weighted graph $G$ such that for each node $v$ the total weight of cut-edges incident to $v$ is at most as large as the total weight of non-cut-edges incident to $v$.

Curiously, a feasible solution always exists. However, it seems that no polynomial-time algorithm is known for solving the problem. For more information, see e.g. Giannakos and Pottie (2005).

• Are you talking about minimizing the energy function of Hopfield nets? en.wikipedia.org/wiki/Hopfield_net – Hartmut Klauck Mar 12 '11 at 14:12
• Yes, this question needs more detail/context – Suresh Venkat Mar 12 '11 at 16:49
• I don't really know that much about the field, but to me it seems like the Happynet problem ("stable configuration") and its variants have been studied a lot from the perspective of PLS-completeness. Googling for "max-cut" and "PLS" might be helpful; note that the local search variant of weighted max-cut (flip-neighbourhoods) is essentially the same problem as Happynet restricted to negative edge weights. – Jukka Suomela Mar 13 '11 at 13:27
• -1 What's the point of this question? – Oleksandr Bondarenko Mar 17 '11 at 15:50