1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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, 2013 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$
    – polar_bear_cheese
    Jun 15, 2013 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, 2013 at 22:44

0

Reset to default

Your Answer

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