5

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?

user1868607
  • 1,017
  • 5
  • 15
  • 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 Feb 15 '24 at 15:30
  • @NeilYoung, the path is not required to be simple and there is no assumption that the graph is a DAG. – user1868607 Feb 15 '24 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? – user1868607 Feb 15 '24 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... – Neal Young Feb 15 '24 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. Feb 15 '24 at 22:47

1 Answers1

3

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.

Neal Young
  • 10,546
  • 33
  • 60