4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Marcus Ritt Feb 11 '11 at 3:07
  • $\begingroup$ Does this imply that the best we can hope for is an algorithm exponential in K? $\endgroup$ – dan_x Feb 11 '11 at 4:21
  • $\begingroup$ Under reasonable complexity assumptions. But still for constant K maybe an efficient algorithm exists. $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 11 '11 at 5:52
  • 1
    $\begingroup$ @Marcus, please make your comment an answer: it's a good one. $\endgroup$ – Suresh Venkat Feb 11 '11 at 7:37
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dan_x Feb 11 '11 at 20:33
  • $\begingroup$ 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? $\endgroup$ – Riko Jacob Feb 13 '11 at 8:52
  • $\begingroup$ 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. $\endgroup$ – dan_x Feb 14 '11 at 22:39
2
$\begingroup$

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

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