3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Apr 14 '18 at 18:09
  • $\begingroup$ 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)? $\endgroup$ – j_random_hacker Apr 14 '18 at 19:27
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 16 '18 at 1:22
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Apr 17 '18 at 13:34
  • $\begingroup$ In this case it does not add anything. However, this is a sub-problem of a larger problem, where we need this explicit $h$. $\endgroup$ – Alberto M. Apr 18 '18 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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