<p>The problem should be solved in polynomial time since it can be reduced to the integral convex quadratic minimum-cost flow problem.</p>

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

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

<ul>
<li>There is an arc from $s$ to each vertex in $V_+$.  The capacity is $k$, and the cost is $0$.</li>
<li>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.</li>
<li>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$.</li>
</ul>

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

CC BY-SA 3.0
2013-01-17T13:52:24.913Z
2013-01-17T13:52:24.913Z
Yoshio Okamoto
<p>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:</p>

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

<p>Is this decision problem NP-complete? The case $C=0$ can be solved by a max-flow problem.</p>

<cc.complexity-theory><graph-algorithms><optimization>
NP-complete problems related to Minimizing Variance
Volker Turau
# NP-complete problems related to Minimizing Variance

(Asked by: username_0 on 2013-01-14)

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

**Tags:** cc.complexity-theory, graph-algorithms, optimization

---

## 1 answers

### Answer by username_1 on 2013-01-17. Score: 0 | Accepted answer

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


---

