# A non-trivial combinatorial optimization

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.

• 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. Jun 15, 2013 at 17:28
• 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. Jun 15, 2013 at 22:12

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.

• 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/… . Feb 20 at 17:30