# Path in a graph with durations

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?

• If zero-width durations are allowed, then the Partition Problem can be reduced to this: Order the input numbers $x_i$ arbitrarily. Make a path with a vertex for each number $x_i$, with zero-width interval $[x_i, x_i] = x_i$. Prepend $s$ to this path, and append $t$. Add edges directed from every lower-numbered vertex to every higher-numbered, and set $h = t/2$ where $t$ is the sum of all input numbers. – j_random_hacker Apr 14 '18 at 18:09
• OK, a bit outside my expertise I'm afraid. But I'm wondering: Does having the parameter $h$ add anything? Wouldn't just dividing all interval endpoints by $h$ and then effectively setting $h=1$ lead to an equivalent problem (with just a polynomial increase in size)? – j_random_hacker Apr 14 '18 at 19:27
• Cross-posted: cs.stackexchange.com/q/90665/755, cstheory.stackexchange.com/q/40599/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Apr 16 '18 at 1:22

## 1 Answer

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).

• Nice approach. Still interested to know if you think having a parameter $h$, as opposed to a fixed constant such as 1, adds anything to the problem. – j_random_hacker Apr 17 '18 at 13:34
• In this case it does not add anything. However, this is a sub-problem of a larger problem, where we need this explicit $h$. – Alberto M. Apr 18 '18 at 19:50