<p>You can model the situation as a "regular language constraint path problem" as investigated in <a href="http://dx.doi.org/10.1137/S0097539798337716" rel="nofollow">Barret, Jacob, Marathe 2000</a>.
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.   </p>

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

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

CC BY-SA 2.5
2011-02-11T20:33:25.913Z
Interesting, thanks for the pointer.  About non-simple paths: would it still work if upon revisiting a vertex, you would not collect the markers that it held again?  That is, "collecting" markers at a vertex the first time removes them.
dan_x
CC BY-SA 2.5
2011-02-13T08:52:58.053Z
In general, this depends on the necessity to "remember" the already visited vertices.
If you need them, this spoils the independence of the complexity from the path length (graph size).
In your concrete setting, it occurs to me that this would not make a difference: Once a marker is set, it will not go away, so it does not matter if you set it again or not.
Or do I miss something?
Riko Jacob
CC BY-SA 2.5
2011-02-14T22:39:11.870Z
Ok.  It occurs to me that the underlying problem could be formulated either with removing or not removing markers (though removing would be preferred).  And maybe the use of the term "monotonicity" was misleading in the problem statement.  It is certainly possible that say m[0] = 1 but e(m)[0] = 0 for some edge function.  Traversing an edge can remove a marker.
dan_x
CC BY-SA 2.5
2011-02-11T16:03:01.763Z
2011-02-11T16:03:01.763Z
Riko Jacob
<p>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$.</p>

CC BY-SA 2.5
2011-02-11T12:00:19.123Z
2011-02-11T12:00:19.123Z
Marcus Ritt
<p>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.</p>

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

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

<p>($e_{ij}$ can be different from $e_{ji}$.)</p>

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

<ul>
<li>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$. </li>
<li>When traversing edge from $i$ to $j$, $\boldsymbol m := e_{ij}(\boldsymbol m)$.</li>
</ul>

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

CC BY-SA 2.5
2011-02-11T03:07:43.880Z
When you choose $K=|V|$, give each vertex a different marker, and set let $e_{ij}(m)=m$ you are searching an Hamiltonian path, which is NP-complete.
Marcus Ritt
CC BY-SA 2.5
2011-02-11T04:21:04.443Z
Does this imply that the best we can hope for is an algorithm exponential in K?
dan_x
CC BY-SA 2.5
2011-02-11T05:52:21.133Z
Under reasonable complexity assumptions. But still for constant K maybe an efficient algorithm exists.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-11T07:37:04.160Z
@Marcus, please make your comment an answer: it's a good one.
Suresh Venkat
<ds.algorithms><graph-algorithms>
Shortest paths with structured dependence on earlier path
dan_x
# Shortest paths with structured dependence on earlier path

(Asked by: username_0 on 2011-02-11)

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

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: When you choose $K=|V|$, give each vertex a different marker, and set let $e_{ij}(m)=m$ you are searching an Hamiltonian path, which is NP-complete.  
> **username_0**: Does this imply that the best we can hope for is an algorithm exponential in K?  
> **username_2**: Under reasonable complexity assumptions. But still for constant K maybe an efficient algorithm exists.  
> **username_3**: @Marcus, please make your comment an answer: it's a good one.  

---

## 2 answers

### Answer by username_4 on 2011-02-11. Score: 4 | Accepted answer

You can model the situation as a "regular language constraint path problem" as investigated in [Barret, Jacob, Marathe 2000](http://dx.doi.org/10.1137/S0097539798337716).
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.

> **Comments:**
> **username_0**: Interesting, thanks for the pointer.  About non-simple paths: would it still work if upon revisiting a vertex, you would not collect the markers that it held again?  That is, "collecting" markers at a vertex the first time removes them.  
> **username_4**: In general, this depends on the necessity to "remember" the already visited vertices. If you need them, this spoils the independence of the complexity from the path length (graph size). In your concrete setting, it occurs to me that this would not make a difference: Once a marker is set, it will not go away, so it does not matter if you set it again or not. Or do I miss something?  
> **username_0**: Ok.  It occurs to me that the underlying problem could be formulated either with removing or not removing markers (though removing would be preferred).  And maybe the use of the term "monotonicity" was misleading in the problem statement.  It is certainly possible that say m[0] = 1 but e(m)[0] = 0 for some edge function.  Traversing an edge can remove a marker.  

---

### Answer by username_1 on 2011-02-11. Score: 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$.


---

