Shortest paths with structured dependence on earlier path

Question

Perhaps this problem has been studied under a different guise. If so, I'd appreciate any pointers or terms that could help my search for related work.

Suppose we have an undirected simple graph $G=(V,E)$. Given as input, we associate with each vertex $i$ a binary vector $\boldsymbol m_i$, where $|\boldsymbol m_i| = K$. $\boldsymbol m_i[k]$ denotes the presence or absence of the $k$-th "marker" for $k \in \{1, ..., K\}$. Each edge $(i,j)$ is associated with a function $e_{ij} : \{0,1\}^K \to \{0,1\}^K$. $e_{ij}$ can be arbitrary, except that it must obey a sort of monotonicity property, where

• If $m_B[k] \ge m_A[k]$ for all $k$, then $e_{ij}(\boldsymbol m_B)[k] \ge e_{ij}(\boldsymbol m_A)[k]$ for all $k$.

($e_{ij}$ can be different from $e_{ji}$.)

Starting at any vertex, I am interested in efficiently finding a short (or even any) simple path that collects all possible markers (or reporting that one does not exist), where the rules for collecting markers are as follows. We maintain binary vector $\boldsymbol m$ denoting which markers that we hold (initially none, i.e. all 0), which is updated as we arrive at vertices and traverse edges.

• When arriving at vertex $i$, collect all markers present at $i$ that we don't currently hold, i.e. $\boldsymbol m[k] := \max(\boldsymbol m[k], \boldsymbol m_i[k])$ for all $k$.
• When traversing edge from $i$ to $j$, $\boldsymbol m := e_{ij}(\boldsymbol m)$.

For $K=1$, I believe this is a standard shortest paths problem. How efficiently can it be solved for larger $K$? (In practice, $K$ is around 2 to 100, $|V|$ is several hundred thousand, $|E|$ is 5 to 10 times $|V|$, and if paths exist, we expect them to be fairly short -- if it helps to fix a parameter $L$, which is the maximum path length, I'd be interested as well.)

Answer 1

You can model the situation as a "regular language constraint path problem" as investigated in Barret, Jacob, Marathe 2000. If you were interested in any shortest path (not just simple ones), this would solve your question: First, transform your graph into a directed one that additionally has an edge per node (every node is split into two, one for the incoming edges and one for the outgoing edges, these are connected by a new edge, the node edge). Now, you encode the markers and the functions as labels in an alphabet of size $2^K+2^{2K}$. The constraining language now has to accept such a word if following your rules leads to the vector of all ones. This is clearly a regular language because it can be accepted by an automaton with $2^K$ states.

For treewidth bounded graphs the above transformation and an algorithm for regular languages and simple paths (presented in the mentioned paper) allows to solve your question in polynomial time.

For more general graphs, finding a simple paths according to some fairly easy fixed regular language is NP-complete, which does not really imply anything for your question. In particular the complexity for constant $K$ (and limited path-length) sounds like an interesting question to me.

Answer 2

When you choose $K=|V|$, give each vertex a different marker, and let $e_{ij}(m)=m$ you are searching for a Hamiltonian path, which is NP-complete. Therefore it is unprobable that you find an efficient algorithm for arbitrary $K$. As observed by Hsien-Chih Chang there may still exist an efficient for small $K$.