<p>This solution is by Gerhard Woeginger.</p>

<p>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.</p>

<p>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)$.</p>

<p>We now describe the
verification algorithm.</p>

<ol>
<li><p>We consider the subset $E'$ of edges of $G$, $E':=\{(u,v)\in E\mid x_{u,v}&gt;0\}$. We check whether $E'$ induces a strongly (undirected)
connected subgraph of $G$.</p></li>
<li><p>We check whether </p>

<ul>
<li>$\sum_{(u,v)\in E'} x_{u,v}=\sum_{(v,w)\in E'} x_{v,w}$, for all $v \in V\setminus\{s,t\}$;</li>
<li>$\sum_{(u,s)\in E'} x_{u,s}=\sum_{(s,w)\in E'} x_{s,w}-1$;</li>
<li>$\sum_{(u,t)\in E'} x_{u,t}=\sum_{(t,w)\in E'} x_{t,w}+1$.</li>
</ul></li>
<li><p>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}$.</p></li>
<li><p>We check whether there exist real values $z_v$, for every $v \in V$, such that</p>

<ul>
<li>$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</li>
<li>$\sum_{v \in V} z_v = h$.</li>
</ul></li>
</ol>

<p>We now sketch the correctness:</p>

<p>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 <a href="http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf" rel="nofollow noreferrer">http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf</a>)</p>

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

CC BY-SA 3.0
2018-04-16T18:06:30.077Z
2018-04-17T12:27:58.987Z
2018-04-17T12:27:58.987Z
Alberto M.
<p>I have the following problem:</p>

<p>given </p>

<ul>
<li>a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ <em>(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)</em> 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$,</li>
<li>two vertices $s,t\in V$ and</li>
<li>an integer $h$ <em>encoded in binary</em>,</li>
</ul>

<p>we have to decide whether or not there exist</p>

<ul>
<li>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 </li>
<li>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)$.</li>
</ul>

<p>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$.</p>

<p>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$.</p>

<p>Have you ever seen a similar problem? Can you come up with an NP algorithm? Or do you know some connected literature?</p>

CC BY-SA 3.0
2018-04-16T01:22:16.523Z
Cross-posted: https://cs.stackexchange.com/q/90665/755, https://cstheory.stackexchange.com/q/40599/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.
D.W.
<cc.complexity-theory><graph-theory><np>
Path in a graph with durations
Alberto M.
# Path in a graph with durations

(Asked by: username_0 on 2018-04-15)

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

Have you ever seen a similar problem? Can you come up with an NP algorithm? Or do you know some connected literature?

**Tags:** cc.complexity-theory, graph-theory, np

> **Comments:**
> **username_1**: Cross-posted: https://cs.stackexchange.com/q/90665/755, https://cstheory.stackexchange.com/q/40599/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.  

---

## 1 answers

### Answer by username_0 on 2018-04-16. Score: 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).


---

