Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.