A non-trivial combinatorial optimization

Question

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.

Answer 1

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.