<p>This is NP-hard even for <span class="math-container">$d=1$</span> by reduction from the (strongly NP-hard) Product Partition problem.</p>
<p><strong>Lemma 1.</strong> <em>The problem (with either objective function) is NP-hard, even for <span class="math-container">$d=1$</span>.</em></p>
<p><em>Proof sketch.</em> Given an instance <span class="math-container">$W=(W_1, \ldots, W_n)\in \mathbb N^n$</span> of Product Partition, the reduction outputs the instance <span class="math-container">$(G, x)$</span> of OP's problem where <span class="math-container">$x=\sqrt {\prod_{i=1}^n W_i}$</span>,
and the multi-digraph <span class="math-container">$G$</span> is a path with <span class="math-container">$2n$</span> edges,
specifically the vertex set is <span class="math-container">$V=[n+1]$</span>,
and, for each <span class="math-container">$i\in[n]$</span>,
there are two edges <span class="math-container">$(i, i+1)_1$</span> and <span class="math-container">$(i, i+1)_2$</span> from <span class="math-container">$i$</span> to <span class="math-container">$i+1$</span>,
the first with weight <span class="math-container">$W_i$</span>, the second with weight 1.</p>
<p>(If a digraph without multi-edges is desired,
just replace each second edge <span class="math-container">$(i, i+1)_2$</span>
by two edges  <span class="math-container">$(i, v_i)$</span> and <span class="math-container">$(v_i, i+1)$</span>,
each with weight 1, where <span class="math-container">$v_i$</span> is a new, artificial vertex.)</p>
<p>This completes the reduction.</p>
<p>Each rooted spanning tree <span class="math-container">$t$</span> rooted at vertex 1 in <span class="math-container">$G$</span>
corresponds bijectively to the subset <span class="math-container">$S(t)\subseteq [n]$</span>
such that <span class="math-container">$S(t) = \{i\in [n] : (i, i+1)_1 \in t\}$</span>,
and vice versa. (Note that if <span class="math-container">$(i, i+1)_1$</span> is not present in <span class="math-container">$t$</span>
then <span class="math-container">$(i, i+1)_2$</span> must be, or, if the modification that removes
multi-edges is used, then each edge <span class="math-container">$(i, v_i)$</span> is
always present, and <span class="math-container">$(v_i, i+1)$</span> is present iff <span class="math-container">$(i, i+1)_1$</span> is not.)</p>
<p>The product of the &quot;vectors&quot; on the edges in a given <span class="math-container">$t$</span>
is then <span class="math-container">$\prod_{i\in S(t)} W_i$</span>.
So the optimal cost for this instance of OP's problem is zero
iff there is a subset with product <span class="math-container">$x$</span>.</p>
<p>(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, <span class="math-container">$x+1$</span>.  Then the same argument works,
as any tree using such an edge has weight at least <span class="math-container">$x+1$</span>.)
<span class="math-container">$~~~\Box$</span></p>
<p>Note that this reduction &quot;almost&quot; shows <em>strong</em> NP-hardness.
It doesn't quite, because <span class="math-container">$x$</span>, which must be given as part of the input
for the decision variant, is exponential in <span class="math-container">$n$</span>.
However, <span class="math-container">$x$</span> can be implicitly encoded by giving <span class="math-container">$W$</span> (even in unary)
and with this encoding this (special case of) OP's problem is strongly NP-hard.</p>

CC BY-SA 4.0
2024-02-20T17:30:20.977Z
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: https://cstheory.stackexchange.com/questions/53908/shortest-path-with-affine-updates-and-fixed-dimension/53920#53920 .
Neal Young
CC BY-SA 4.0
2024-02-20T17:28:09.443Z
2024-02-20T17:37:32.727Z
2024-02-20T17:37:32.727Z
Neal Young
<p>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.</p>

<p>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]$.</p>

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

<p>$\| 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,</p>

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

CC BY-SA 3.0
2013-06-15T17:28:41.547Z
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.
Neal Young
CC BY-SA 3.0
2013-06-15T22:12:42.733Z
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.
polar_bear_cheese
<graph-theory><approximation-algorithms><tree><combinatorics>
A non-trivial combinatorial optimization
polar_bear_cheese
# A non-trivial combinatorial optimization

(Asked by: username_0 on 2013-06-14)

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.

**Tags:** graph-theory, approximation-algorithms, tree, combinatorics

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2024-02-20. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_1**: 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: https://cstheory.stackexchange.com/questions/53908/shortest-path-with-affine-updates-and-fixed-dimension/53920#53920 .  

---

