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

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

<hr>

<p>The Happynet problem is related to minimizing the energy in a <a href="http://en.wikipedia.org/wiki/Hopfield_net" rel="nofollow">Hopfield net</a>.</p>

<p>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.</p>

<p>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$.</p>

<p>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. <a href="http://www.lamsade.dauphine.fr/sites/default/IMG/pdf/cahierLamsade226.pdf" rel="nofollow">Giannakos and Pottie (2005)</a>.</p>

CC BY-SA 2.5
2011-03-17T15:50:08.017Z
-1 What's the point of this question?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-03-12T14:12:34.753Z
Are you talking about minimizing the energy function of Hopfield nets? http://en.wikipedia.org/wiki/Hopfield_net
Hartmut Klauck
CC BY-SA 2.5
2011-03-12T16:49:44.090Z
Yes, this question needs more detail/context
Suresh Venkat
CC BY-SA 2.5
2011-03-13T13:27:49.290Z
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](http://en.wikipedia.org/wiki/PLS_%28complexity%29). 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
<cc.complexity-theory><ds.algorithms><soft-question><approximation-algorithms>
Hardness of Happynet problem
anacrusis
# Hardness of Happynet problem

(Asked by: username_0 on 2011-03-12)

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](http://en.wikipedia.org/wiki/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)](http://www.lamsade.dauphine.fr/sites/default/IMG/pdf/cahierLamsade226.pdf).

**Tags:** cc.complexity-theory, ds.algorithms, soft-question, approximation-algorithms

> **Comments:**
> **username_2**: Are you talking about minimizing the energy function of Hopfield nets? http://en.wikipedia.org/wiki/Hopfield_net  
> **username_3**: Yes, this question needs more detail/context  
> **username_4**: 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](http://en.wikipedia.org/wiki/PLS_%28complexity%29). 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.  
> **username_1**: -1 What's the point of this question?  

---

## 0 answers

