5
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Commented Feb 15 at 15:30
  • $\begingroup$ @NeilYoung, the path is not required to be simple and there is no assumption that the graph is a DAG. $\endgroup$ Commented Feb 15 at 15:58
  • $\begingroup$ @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? $\endgroup$ Commented Feb 15 at 16:06
  • $\begingroup$ 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... $\endgroup$
    – Neal Young
    Commented Feb 15 at 16:43
  • $\begingroup$ @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.) $\endgroup$
    – D.W.
    Commented Feb 15 at 22:47

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.