So I stumble over this problem in which I couldn't find anything similar in the literature. I am not even sure if it is NP-hard or solvable in polynomial time. Any thought or suggestion would be greatly appreciated.

Suppose I give you a $d$ dimensional vector $x$, with rational entries in the range $[0,1]$. Similarly, I also give you $d$ dimensional $n^2$ vectors $y_{i,j}$ for $i,j \in \{1,...,n\}$ with entries in the range $[0,1]$.

I want to find a directed spanning tree with each vertex has exactly one parent (except the root) $T$ of $n$ vertices such that:

$\| x - \circ_{(i,j) \in edges(T) }y_{i,j}\|_1$ is minimized, where $\circ$ denotes the Hadamard product (entry-wise product) between the vectors. I'm also fine with $l_2$ norm. I.e,

$\| x - \circ_{(i,j) \in edges(T) }y_{i,j}\|_2$ is minimized.

  • 1
    $\begingroup$ If I understand the problem correctly, then surely it is NP-hard, even with d=1. First, note that the problem "given an edge-weighted graph and a target $T$, is there a spanning tree of total weight exactly $T$" is NP-complete. (By reduction from subset-sum: given $x_1, x_2, \ldots, x_n$ and a target $T$, construct multigraph $G=(V,E)$ with $V=\{0,\ldots,n\}$, where $E$ has two copies of each edge $(i,i+1)$ ($0 \le i < n$), one with weight $x_i$, the other with weight 0.) Next, note that for $d=1$ your problem (with the Hadamard product replaced by a sum) generalizes that problem. $\endgroup$ – Neal Young Jun 15 '13 at 17:28
  • $\begingroup$ Your solution sounds just right. I suppose when you say my problem generalizes that problem, it means replacing x by log(x) and the product of y's by sum of log(y)'s? I really appreciate your simple explanation. $\endgroup$ – HTV Jun 15 '13 at 22:12
  • $\begingroup$ Yes, there is a gap: because of the sums vs. products issue, the problems are not the same. But I assume that if the problem is hard with sums, it will be hard with products. Using the log to close the gap is a natural idea, except that your problem stipulates that the numbers should be rational, which prevents using the log. I recall previous posts here on cstheory.stackexchange.com which discussed the "product" variant of subset-sum.. If I recall that variant is still NP-hard. cstheory.stackexchange.com/questions/16902/… $\endgroup$ – Neal Young Jun 16 '13 at 22:44

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.