# Shortest path with affine updates and fixed dimension

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?

• 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? Commented Feb 15 at 15:30
• @NeilYoung, the path is not required to be simple and there is no assumption that the graph is a DAG. Commented Feb 15 at 15:58
• @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? Commented Feb 15 at 16:06
• 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... Commented Feb 15 at 16:43
• @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.
Commented Feb 15 at 22:47

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, 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 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, Eur. J. Oper. Res. 207, No. 2, 601-604 (2010). ZBL1205.68174.