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?


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.

  • $\begingroup$ 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. $\endgroup$ Commented Nov 1, 2015 at 14:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.