NP-complete problems related to Minimizing Variance I am interested in references to NP-complete problems that involve some non-linear terms (e.g. quadratic terms). So far I am aware of the "Quadratic Assignment problem" and "Quadratic Programming". The non-linear terms can be part of e.g. the constraints or the objective function. My motivation is to get some ideas for the following problem:

Let $k&gt;0$ be an integer and $G=(V,E)$ an undirected graph such that the degree of each vertex is at least $k$. Each node of $G$ picks $k$ of its neighbors as its mates. For each node $v$ let $m(v)$ be the number of neighbors that selected $v$ as a mate. Then $\sum_{v\in V} m(v) = |V|k$. Given a number $C&gt;0$. The mate-problem is to decide whether there exists a selection of mates such that the variance of this selection is less than $C$. In other words 
$\sum_{v\in V} (m(v) - \mu)^2 &lt; C$
where $\mu$ is the mean value, i.e. $\mu = \frac{1}{|V|}\sum_{v\in V}m(v)$.

Is this decision problem NP-complete? The case $C=0$ can be solved by a max-flow problem.
The problem should be solved in polynomial time since it can be reduced to the integral convex quadratic minimum-cost flow problem.

The essential part of the objective function is $\sum_{v \in V}m(v)^2$ since $\sum_{v \in V}m(v)$ does not change by a choice of mates.

Given a graph $G=(V,E)$ we construct the following network. The vertex set is $V_+ \cup V_- \cup \{s,t\}$, where $V_+ = \{v_+ \mid v \in V\}$ and $V_- = \{v_- \mid v \in V\}$ are copies of $V$, and $s,t \not\in V_+\cup V_-$.  The vertex $s$ is a source, and $t$ is a sink. The arcs are constructed as follows. 


There is an arc from $s$ to each vertex in $V_+$.  The capacity is $k$, and the cost is $0$.
There is an arc from each vertex in $V_-$ to $t$.  The capacity is $+\infty$, and the cost is the square of flow on the arc.
There is an arc from $u_+ \in V_+$ to $v_- \in V_-$ if and only if there is an edge $\{u,v\} \in E$ in $G$.  The capacity is $1$, and the cost is $0$.


Now, we inject the $k|V|$ unit of flow to the network from $s$ toward $t$.  Then, a feasible integral flow corresponds to a mate assignment, and the total cost is $\sum_{v \in V} m(v)^2$.