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.
