Path in a graph with durations

Question

I have the following problem:

given

• a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ the set of intervals, bounded or unbounded above, with non-negative rational bounds) is a function associating with each vertex $v\in V$ a "minimum/maximum duration" $d(v)=[a,b]$ for some $a\in \mathbb{Q}_0^+,b\in \mathbb{Q}_0^+\cup\{+\infty\}$ and $a\leq b$,
• two vertices $s,t\in V$ and
• an integer $h$ encoded in binary,

we have to decide whether or not there exist

• a path in $G$, possibly with repeated vertices and edges, $v_0 \cdot v_1 \cdots v_{n-1}\cdot v_n$, with $v_0=s$ and $v_n=t$ and
• a list of values $d_0,\ldots,d_n\in\mathbb{Q}_0^+$, such that $\sum_{i=0}^n d_i = h$ and for all $i=0,\ldots, n$, $d_i\in d(v_i)$.

Intuitively, we have to find a path in $G$, possibly where we get to the same vertices/edges also more than once, and where we remain in each vertex a non-negative rational amount of time allowed by the minimum/maximum duration function, such that the overall time of the path equals $h$.

This can be solved easily in PSPACE. We conjecture it to be in NP (we already know it is NP-hard!). This is not trivial to prove, as we may have $h\in\Theta(2^n)$, for instance. Thus the required path may have length exponential in both $|V|$ and in the binary encoding of $h$.

Is this problem in NP?

Answer 1

This solution is by Gerhard Woeginger.

In order to prove that this problem belongs to NP, we provide a polynomial-size certificate, and then we show how to check it in deterministic polynomial time.

The certificate is just the following: a set of integers $\{x_{u,v}\mid (u,v)\in E\}$. Intuitively, $x_{u,v}$ is the number of times the solution path traverses $(u,v)$.

We now describe the verification algorithm.

1. We consider the subset $E'$ of edges of $G$, $E':=\{(u,v)\in E\mid x_{u,v}>0\}$. We check whether $E'$ induces a strongly (undirected) connected subgraph of $G$.

2. We check whether

   • $\sum_{(u,v)\in E'} x_{u,v}=\sum_{(v,w)\in E'} x_{v,w}$, for all $v \in V\setminus\{s,t\}$;
   • $\sum_{(u,s)\in E'} x_{u,s}=\sum_{(s,w)\in E'} x_{s,w}-1$;
   • $\sum_{(u,t)\in E'} x_{u,t}=\sum_{(t,w)\in E'} x_{t,w}+1$.

3. For all $v \in V\setminus\{s\}$, we define $y_v:=\sum_{(u,v)\in E'} x_{u,v}$, i.e., the number of times the solution path gets into $v$. Moreover, $y_s := \sum_{(s,u)\in E'} x_{s,u}$.

4. We check whether there exist real values $z_v$, for every $v \in V$, such that

   • $d_{min}(v)\cdot y_v \leq z_v \leq d_{max}(v)\cdot y_v$ (here $d_{min}(v)$ and $d_{max}(v)$ denote resp. the lower and the upper bound of the rational interval $d(v)$), and
   • $\sum_{v \in V} z_v = h$.

We now sketch the correctness:

Steps 1. and 2. together check that the values $x_{u,v}$ for the arcs specify a directed Eulerian path from $s$ to $t$ (we refer to http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf)

Steps 3. and 4. calculate $z_v$, for all $v\in V$, which is the total waiting time of the path on the node $v$. We observe that the (in)equalities of step 4. form a linear program (LP), which can be solved in deterministic polynomial time (e.g., using the ellipsoid algorithm).