7
$\begingroup$

Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some alphabet $\Sigma$. We are also given a description of an NFA $M$ (or DFA, or regular expression) accepting some regular language $L(M) \subseteq \Sigma^*$, and two vertices $s, t \in V$.

The problem is to find the shortest path in $G$ from $s$ to $t$ whose edge labels form a string that is a member of $L(M)$. That is, we only consider paths $e_1, e_2, \dots, e_k$ where $\ell(e_1) \ell(e_2) \dots \ell(e_k) \in L(M)$.

Can this problem be solved in time polynomial in $|V|$, $|E|$, and $|M|$?

This question was inspired by these other questions about special cases of this problem.

$\endgroup$
  • 2
    $\begingroup$ Nice. Related is the concept of "Multi-State Mazes", where the direction in which you are allowed to exit a spot depends on the way you entered it. $\endgroup$ – Hendrik Jan Dec 29 '19 at 1:25
  • $\begingroup$ @HendrikJan Yep, and those can of course be solved by the same sort of product construction. When in doubt, just spam more vertices! $\endgroup$ – Aaron Rotenberg Dec 30 '19 at 0:43
  • $\begingroup$ @AaronRotenberg, thanks for the reminder! Yes, I wanted to send a thank-you to your outstanding answer. Awarded. $\endgroup$ – D.W. Jan 23 at 16:56
4
+50
$\begingroup$

This problem can be solved in polynomial time by a product construction. Construct the graph $G^\prime$ as follows:

  • The vertices of $G^\prime$ are $(V \times M) \cup \{\#\}$, i.e. all pairs of a vertex of $G$ and a state of $M$, together with an extra vertex identified by the arbitrary symbol $\#$.
  • For each edge in $e \in E$ from $v_1$ to $v_2$, add an edge in $G^\prime$ from $(v_1, m_1)$ to $(v_2, m_2)$ with weight $w(e)$ if and only if there is an edge in $M$ from $m_1$ to $m_2$ that is labeled $\ell(e)$.
  • For each accepting state $m$ in $M$, add an edge in $G^\prime$ from $(t, m)$ to $\#$ with weight 0.

Then the shortest path in $G^\prime$ from $(s, m_0)$ to $\#$ (where $m_0$ is the initial state of $M$) gives the shortest path in $G$ from $s$ to $t$ matching $L(M)$. There cannot be a negative cycle in $G^\prime$, since dropping the $m$ states from the vertex labels would give a negative cycle in $G$, which we are assuming does not exist.

This also answers the question if $M$ is a DFA or regular expression instead of an NFA, since these can be converted to an equivalent NFA in polynomial time. We can also directly handle NFAs with $\varepsilon$-transitions: if $M$ contains an $\varepsilon$-transition from $m_1$ to $m_2$, add an edge in $G^\prime$ with weight 0 from $(v, m_1)$ to $(v, m_2)$ for each $v \in V$.

For fixed $M$, the product graph $G^\prime$ has only linearly more vertices and edges than the original graph $G$. This means that any fixed problem of the form "find the shortest path that visits edges in such-and-such order", such as the problems linked in the question, can be solved just as fast as the ordinary shortest path problem asymptotically.

As an implementation detail, note that there is no need to actually write down the whole product graph in memory. The vertices and edges can be generated dynamically while running the shortest path algorithm, which allows unused vertices to be skipped entirely.

$\endgroup$

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.