<p><strong>Lemma 1.</strong> <em>The problem is <s>strongly</s> NP-hard for <span class="math-container">$n=2$</span>, even in directed acyclic graphs (DAGs).</em></p>
<p><em>[EDIT: strong NP-hardness depends on the encoding.  See the comments at the end.]</em></p>
<p><em>Proof sketch.</em> The proof is by reduction from the <a href="https://en.wikipedia.org/wiki/Partition_problem#Variants_and_generalizations" rel="nofollow noreferrer">Product Partition problem</a>, which is strongly NP-hard [1]:</p>
<p>Product Partition<br />
<span class="math-container">$~~~$</span>  <strong>input:</strong> <em>integers <span class="math-container">$W=(w_1, w_2, \ldots, w_n)$</span></em><br />
<span class="math-container">$~$</span>  <strong>output:</strong> <em>is there a <strong>balanced</strong> subset <span class="math-container">$S\subseteq [n]$</span>, that is, one such that <span class="math-container">$\prod_{i\in S} w_i = \prod_{i\not\in S} w_i$</span>?</em></p>
<p>Fix a Product-Partition instance <span class="math-container">$W$</span>.</p>
<p><strong>Observation 1.</strong> <em>A given subset <span class="math-container">$S$</span> is balanced iff <span class="math-container">$\vec 1 \cdot \vec v(S) \le T$</span>,
where</em> <span class="math-container">$\vec v(S) = \left[
\begin{array}{c}
\prod_{i\in S} w_i\\
\prod_{i\not\in S} w_i
\end{array}\right]$</span>
and <span class="math-container">$T= 2\sqrt {\prod_{i=1}^n w_i}$</span>.</p>
<p>(The observation follows from the fact that, for <span class="math-container">$c$</span> fixed and <span class="math-container">$z\ge 0$</span>, the function <span class="math-container">$z\mapsto z + c/z$</span> is uniquely minimized at <span class="math-container">$z=\sqrt c$</span>, where it takes the value <span class="math-container">$2\sqrt c$</span>.)</p>
<p>Given <span class="math-container">$W=(w_1, \ldots, w_n)$</span>, the reduction constructs an instance <span class="math-container">$G=(V,E)$</span> of OP's problem as follows.</p>
<p>We describe <span class="math-container">$G$</span> as a multigraph (with multi-edges).  It can be converted into a regular graph by the standard technique of splitting each edge into a path of length 2 by adding a new intermediate vertex.</p>
<p>We take <span class="math-container">$G$</span> to have vertex set <span class="math-container">$V=[n+1]$</span>. For each vertex <span class="math-container">$i\in [n]$</span>, there are two directed 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>,
labeled, respectively, with the following two matrices:
<span class="math-container">$$\left[
\begin{array}{cc}
w_i &amp; 0\\
0 &amp; 1
\end{array}\right],
~~\text{and}~~
\left[
\begin{array}{cc}
1 &amp; 0\\
0 &amp; w_i
\end{array}\right].
$$</span>
We label the vertices <span class="math-container">$1$</span> and <span class="math-container">$n+1$</span> with the vector <span class="math-container">$\vec 1 \in \mathbb Z^2$</span>,
so that the starting value of <span class="math-container">$x$</span> (in OP's problem definition)
is <span class="math-container">$\vec 1$</span>.
(OP's problem allows each edge to have a vector associated with it.
For each edge the associated vector is <span class="math-container">$\vec 0$</span>.)
This completes the reduction.</p>
<p>To see that it is correct,
note that the <span class="math-container">$2^n$</span> paths from 1 to <span class="math-container">$n+1$</span> in this graph
correspond bijectively to the <span class="math-container">$2^n$</span> subsets <span class="math-container">$S\subseteq [n]$</span>.
A given <span class="math-container">$1\to n$</span> path <span class="math-container">$P$</span> (considered as a set of edges)
corresponds to the set
<span class="math-container">$S(P)=\{i\in [n] : (i, i+1)_1\}\in P\}$</span>.
Further, the objective value achieved by <span class="math-container">$P$</span> is
<span class="math-container">$$
\big(\textstyle\prod_{i\in S(P)} w_i\big)
+\big(\textstyle\prod_{i\not\in S(P)} w_i\big)
= \vec v(S(P))\cdot \vec 1.
$$</span>
Per Observation 1, this value is at most <span class="math-container">$T = 2\sqrt{\prod_{i} w_i}$</span>
iff <span class="math-container">$S(P)$</span> is balanced. <span class="math-container">$~~~\Box$</span></p>
<p>[EDIT: The reduction above doesn't show <em>strong</em> NP-hardness
with the obvious encoding of OP's problem as a decision problem,
which requires encoding the target <span class="math-container">$T$</span>,
whose value (in the standard encoding) is exponentially large.
However, the input can encode <span class="math-container">$T$</span> implicitly
by giving the <span class="math-container">$n$</span> <span class="math-container">$w_i$</span>'s (whose values are polynomially large).
With this encoding, the problem is strongly NP-hard.
See <a href="https://cstheory.stackexchange.com/questions/16902/subset-sum-vs-subset-product-strong-vs-weak-np-hardness#comment120024_16902">here</a>
for related discussion.]</p>
<hr />
<p>[1] <em>Ng, C. T.; Barketau, M. S.; Cheng, T. C. E.; Kovalyov, Mikhail Y.</em>, <a href="https://doi.org/10.1016/j.ejor.2010.05.034" rel="nofollow noreferrer"><strong>“Product partition” and related problems of scheduling and systems reliability: computational complexity and approximation</strong></a>, Eur. J. Oper. Res. 207, No. 2, 601-604 (2010). <a href="https://zbmath.org/?q=an:1205.68174" rel="nofollow noreferrer">ZBL1205.68174</a>.</p>

CC BY-SA 4.0
2024-02-20T17:33:38.400Z
Closely related: https://cstheory.stackexchange.com/a/53932/8237 .
Neal Young
CC BY-SA 4.0
2024-02-15T16:41:53.290Z
2024-02-20T14:01:09.097Z
2024-02-20T14:01:09.097Z
Neal Young
<p>One may look at the shortest path problem on a weighted directed graph with weights on <span class="math-container">$\mathbb{Q}$</span> as the problem of minimizing a rational value <span class="math-container">$x$</span> which is updated at each edge of the graph with the label <span class="math-container">$v$</span> of the edge. So essentially, we can rewrite the labels of a weighted graph and write updates <span class="math-container">$x := x + v$</span>. The shortest path problem then becomes the problem of minimising the value of <span class="math-container">$x$</span>. This is known to be solvable in polynomial time.</p>
<p>Now suppose we generalise this to a constant number of variables <span class="math-container">$x$</span>. Now we consider at each step an update of a vector <span class="math-container">$\vec{x} = A \vec{x} + \vec{b}$</span> where <span class="math-container">$A \in \mathbb{Q}^{n \times n}, \vec{b} \in \mathbb{Q}^{n \times 1}$</span>. The matrix <span class="math-container">$A$</span> and the vector <span class="math-container">$b$</span> may be different at each edge. At the target node one computes an affine function <span class="math-container">$o = \vec{c} \vec{x} + d$</span> where <span class="math-container">$\vec{c} \in \mathbb{Q}^{n \times 1}$</span> and <span class="math-container">$d \in \mathbb{Q}$</span>. This target function may be different for each final node. The optimisation problem is to determine the minimal value of <span class="math-container">$o$</span>.</p>
<p>Is it known whether this problem for fixed <span class="math-container">$n$</span> is solvable in polynomial time?</p>

CC BY-SA 4.0
2024-02-15T15:30:48.700Z
Is the path required to be simple?  If so the problem is NP-hard even for $n=1$ by reduction from Longest Path (i.e. min-weight simple path where each edge has weight -1).  Or to simplify do you want to assume the graph is a DAG?
Neal Young
CC BY-SA 4.0
2024-02-15T15:58:48.510Z
@NeilYoung, the path is not required to be simple and there is no assumption that the graph is a DAG.
user1868607
CC BY-SA 4.0
2024-02-15T16:06:38.490Z
@NeilYoung isn't it that if the case of the graph being a DAG is NP-hard then that implies the general case is NP-hard?
user1868607
CC BY-SA 4.0
2024-02-15T16:43:21.327Z
Yes.  Also, note that if the graph is not a DAG it may contain infinitely long paths, which one has to take some care about in the problem definition...
Neal Young
CC BY-SA 4.0
2024-02-15T22:47:58.470Z
@NealYoung, I think replacing max/min with sup/inf in the optimization takes care of that concern.  (This is the standard way of formulating an optimization problem when optimizing over infinitely many possibilities.)
D.W.
<ds.algorithms><np-hardness><shortest-path>
Shortest path with affine updates and fixed dimension
user1868607
# Shortest path with affine updates and fixed dimension

(Asked by: username_0 on 2024-02-13)

One may look at the shortest path problem on a weighted directed graph with weights on $\mathbb{Q}$ as the problem of minimizing a rational value $x$ which is updated at each edge of the graph with the label $v$ of the edge. So essentially, we can rewrite the labels of a weighted graph and write updates $x := x + v$. The shortest path problem then becomes the problem of minimising the value of $x$. This is known to be solvable in polynomial time.

Now suppose we generalise this to a constant number of variables $x$. Now we consider at each step an update of a vector $\vec{x} = A \vec{x} + \vec{b}$ where $A \in \mathbb{Q}^{n \times n}, \vec{b} \in \mathbb{Q}^{n \times 1}$. The matrix $A$ and the vector $b$ may be different at each edge. At the target node one computes an affine function $o = \vec{c} \vec{x} + d$ where $\vec{c} \in \mathbb{Q}^{n \times 1}$ and $d \in \mathbb{Q}$. This target function may be different for each final node. The optimisation problem is to determine the minimal value of $o$.

Is it known whether this problem for fixed $n$ is solvable in polynomial time?

**Tags:** ds.algorithms, np-hardness, shortest-path
> **Comments:**
> **username_1**: Is the path required to be simple?  If so the problem is NP-hard even for $n=1$ by reduction from Longest Path (i.e. min-weight simple path where each edge has weight -1).  Or to simplify do you want to assume the graph is a DAG?  
> **username_0**: @NeilYoung, the path is not required to be simple and there is no assumption that the graph is a DAG.  
> **username_0**: @NeilYoung isn't it that if the case of the graph being a DAG is NP-hard then that implies the general case is NP-hard?  
> **username_1**: Yes.  Also, note that if the graph is not a DAG it may contain infinitely long paths, which one has to take some care about in the problem definition...  
> **username_2**: @NealYoung, I think replacing max/min with sup/inf in the optimization takes care of that concern.  (This is the standard way of formulating an optimization problem when optimizing over infinitely many possibilities.)  

---

## 1 answers

### Answer by username_1 on 2024-02-15. Score: 3 | Accepted answer

**Lemma 1.** *The problem is ~~strongly~~ NP-hard for $n=2$, even in directed acyclic graphs (DAGs).*

*[EDIT: strong NP-hardness depends on the encoding. See the comments at the end.]*

*Proof sketch.* The proof is by reduction from the [Product Partition problem](https://en.wikipedia.org/wiki/Partition_problem#Variants_and_generalizations), which is strongly NP-hard [1]:

Product Partition  
$~~~$ **input:** *integers $W=(w\_1, w\_2, \ldots, w\_n)$*  
$~$ **output:** *is there a **balanced** subset $S\subseteq [n]$, that is, one such that $\prod\_{i\in S} w\_i = \prod\_{i\not\in S} w\_i$?*

Fix a Product-Partition instance $W$.

**Observation 1.** *A given subset $S$ is balanced iff $\vec 1 \cdot \vec v(S) \le T$,
where* $\vec v(S) = \left[
\begin{array}{c}
\prod\_{i\in S} w\_i\\
\prod\_{i\not\in S} w\_i
\end{array}\right]$
and $T= 2\sqrt {\prod\_{i=1}^n w\_i}$.

(The observation follows from the fact that, for $c$ fixed and $z\ge 0$, the function $z\mapsto z + c/z$ is uniquely minimized at $z=\sqrt c$, where it takes the value $2\sqrt c$.)

Given $W=(w\_1, \ldots, w\_n)$, the reduction constructs an instance $G=(V,E)$ of OP's problem as follows.

We describe $G$ as a multigraph (with multi-edges). It can be converted into a regular graph by the standard technique of splitting each edge into a path of length 2 by adding a new intermediate vertex.

We take $G$ to have vertex set $V=[n+1]$. For each vertex $i\in [n]$, there are two directed edges $(i, i+1)\_1$ and $(i, i+1)\_2$ from $i$ to $i+1$,
labeled, respectively, with the following two matrices:
$$\left[
\begin{array}{cc}
w\_i & 0\\
0 & 1
\end{array}\right],
~~\text{and}~~
\left[
\begin{array}{cc}
1 & 0\\
0 & w\_i
\end{array}\right].
$$
We label the vertices $1$ and $n+1$ with the vector $\vec 1 \in \mathbb Z^2$,
so that the starting value of $x$ (in OP's problem definition)
is $\vec 1$.
(OP's problem allows each edge to have a vector associated with it.
For each edge the associated vector is $\vec 0$.)
This completes the reduction.

To see that it is correct,
note that the $2^n$ paths from 1 to $n+1$ in this graph
correspond bijectively to the $2^n$ subsets $S\subseteq [n]$.
A given $1\to n$ path $P$ (considered as a set of edges)
corresponds to the set
$S(P)=\{i\in [n] : (i, i+1)\_1\}\in P\}$.
Further, the objective value achieved by $P$ is
$$
\big(\textstyle\prod\_{i\in S(P)} w\_i\big)
+\big(\textstyle\prod\_{i\not\in S(P)} w\_i\big)
= \vec v(S(P))\cdot \vec 1.
$$
Per Observation 1, this value is at most $T = 2\sqrt{\prod\_{i} w\_i}$
iff $S(P)$ is balanced. $~~~\Box$

[EDIT: The reduction above doesn't show *strong* NP-hardness
with the obvious encoding of OP's problem as a decision problem,
which requires encoding the target $T$,
whose value (in the standard encoding) is exponentially large.
However, the input can encode $T$ implicitly
by giving the $n$ $w\_i$'s (whose values are polynomially large).
With this encoding, the problem is strongly NP-hard.
See [here](https://cstheory.stackexchange.com/questions/16902/subset-sum-vs-subset-product-strong-vs-weak-np-hardness#comment120024_16902)
for related discussion.]

---

[1] *Ng, C. T.; Barketau, M. S.; Cheng, T. C. E.; Kovalyov, Mikhail Y.*, [**“Product partition” and related problems of scheduling and systems reliability: computational complexity and approximation**](https://doi.org/10.1016/j.ejor.2010.05.034), Eur. J. Oper. Res. 207, No. 2, 601-604 (2010). [ZBL1205.68174](https://zbmath.org/?q=an:1205.68174).

> **Comments:**
> **username_1**: Closely related: https://cstheory.stackexchange.com/a/53932/8237 .  

---

