1
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Nov 1 '15 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.