# NP-completeness of maximum-sum subtree with quadratic constraint

Intuitively, given:

• a graph
• a root node
• a reward mapping from node to real number
• a cost mapping from node to real number

We want to find the tree that maximizes the reward while keeping a quadratic cost function under some threshold.

Formally, given:

• a graph $G=(V, E, w, c)$ where $w: V \rightarrow \mathbb{R}$ and $c: V \rightarrow \mathbb{R}$
• threshold $A \in \mathbb{R}$
• root node $r \in V$

Find a tree $T=(W, D), W \subseteq V, D \subseteq E$ rooted at $r$ that maximizes

$\sum\limits_{v \in W} w(v)$

s.t. $\sum\limits_{v \in W} (c(v) - \frac{1}{|W|} \sum\limits_{v \in W} c(v))^2 \le A$

Is this maximum-sum subtree with quadratic constraint NP-complete? Why?

PS:

A related problem is finding length-constrained maximum-sum subtree, which is NP-hard for general graph. Edged have length cost and vertices have reward value. The goal is to find a subtree that maximizes sum of vertex rewards while sum of edge lengths are below some given bound.

This can be seen as maximum-sum subtree with linear constraint, instead of a quadratic one.

• Sorry for the unclarity. I improved the question. $D$ imposes the constraint that it must form a tree with $W$ rooted at $r$. The constraint about $c(v)$ is indeed about variance. Nov 1, 2015 at 14:04