2
$\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.

$\endgroup$
2
  • 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$ Jun 15, 2013 at 22:12

1 Answer 1

1
$\begingroup$

This is NP-hard even for $d=1$ by reduction from the (strongly NP-hard) Product Partition problem.

Lemma 1. The problem (with either objective function) is NP-hard, even for $d=1$.

Proof sketch. Given an instance $W=(W_1, \ldots, W_n)\in \mathbb N^n$ of Product Partition, the reduction outputs the instance $(G, x)$ of OP's problem where $x=\sqrt {\prod_{i=1}^n W_i}$, and the multi-digraph $G$ is a path with $2n$ edges, specifically the vertex set is $V=[n+1]$, and, for each $i\in[n]$, there are two edges $(i, i+1)_1$ and $(i, i+1)_2$ from $i$ to $i+1$, the first with weight $W_i$, the second with weight 1.

(If a digraph without multi-edges is desired, just replace each second edge $(i, i+1)_2$ by two edges $(i, v_i)$ and $(v_i, i+1)$, each with weight 1, where $v_i$ is a new, artificial vertex.)

This completes the reduction.

Each rooted spanning tree $t$ rooted at vertex 1 in $G$ corresponds bijectively to the subset $S(t)\subseteq [n]$ such that $S(t) = \{i\in [n] : (i, i+1)_1 \in t\}$, and vice versa. (Note that if $(i, i+1)_1$ is not present in $t$ then $(i, i+1)_2$ must be, or, if the modification that removes multi-edges is used, then each edge $(i, v_i)$ is always present, and $(v_i, i+1)$ is present iff $(i, i+1)_1$ is not.)

The product of the "vectors" on the edges in a given $t$ is then $\prod_{i\in S(t)} W_i$. So the optimal cost for this instance of OP's problem is zero iff there is a subset with product $x$.

(Technically, OP's problem definition doesn't explicitly specify a graph, just edge weights, so presumably the graph is supposed to be complete, in which case give every edge not mentioned above weight, say, $x+1$. Then the same argument works, as any tree using such an edge has weight at least $x+1$.) $~~~\Box$

Note that this reduction "almost" shows strong NP-hardness. It doesn't quite, because $x$, which must be given as part of the input for the decision variant, is exponential in $n$. However, $x$ can be implicitly encoded by giving $W$ (even in unary) and with this encoding this (special case of) OP's problem is strongly NP-hard.

$\endgroup$
1
  • $\begingroup$ Note that essentially the same reduction would show that minimizing either objective function, even with $x=0$, is NP-hard. This is essentially the same as the solution here to a related question: cstheory.stackexchange.com/questions/53908/… . $\endgroup$
    – Neal Young
    Feb 20 at 17:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.