First of all, sorry for this long and maybe not very informative title...


Let $G=(V,E)$ be a directed graph, let $v_0 \in V$ be the initial node of paths that I will consider in the graph.

Let $\Sigma$ an alphabet and let $T$ (for target) a set of words built from $\Sigma$ (e.g. $T \subset \Sigma^*$). Nodes of $G$ are tagged with letters from $\Sigma$. Each node is tagged with only one letter, and most nodes are tagged with the empty letter.

The general question is: how to find (algorithm, complexity) the set of paths starting at $v_0$ that contains all words from $T$ and whose cumulated length is minimum.

This problem is not that hard to solve (I am not speaking from the complexity point of view): this can be solved using classical optimization methods. For instance we take all paths of a sufficient length that cover elements of $T$, then we choose a subset of these paths that cover all elements of $T$ and whose length is minimum. Before that we off course checked (reachability analysis) if all elements of $T$ can be found in the graph.

My problem:

Imagine now that we don't have access to the graph explicitly (not enough memory for instance).

Instead we are given a function $f : V \rightarrow subgraph_k(G) $ that gives us, for a node $v$, the subgraph of diameter $2k$ centered around $v$ ($k \in \mathbb{N}$ fixed a priori). Moreover we have only a very limited memory (let's say we cannot store more than a few paths of reasonable length).

With this very restricted access to the graph, how to solve the problem? All solutions that I can imagine are based on sampling and are clearly not effective. Does any of you have an idea?

  • $\begingroup$ What the role of v0 here ? Is it the first node you will check, i.e. f(v0) is the first subset ? Just for clarity, is this a centralized setting or a distributed setting where each node has its own process and takes actions of its own ? $\endgroup$ Oct 31 '10 at 0:31
  • $\begingroup$ $v_0$ is the starting point of every paths I want in my solution set. $f(v_0)$ is indeed the first subgraph I will access. We are in a centralized setting. $\endgroup$ Oct 31 '10 at 0:34
  • $\begingroup$ Is “effective” the same as “efficient”? If so, although you write that you are not speaking from the complexity point of view, the question is about complexity. In that case, we cannot hope for an efficient algorithm with restricted memory unless there is an efficient algorithm with arbitrary memory. $\endgroup$ Oct 31 '10 at 12:22
  • $\begingroup$ The time complexity is not really what annoys me. A direct application of a solution to this problem can be find in test cases generation, where an exponential solution is still better than a polynomial one on a structure too large to be stored in memory. However, I want an algorithm whose quality is controlled (a FPRAS is OK for instance). $\endgroup$ Oct 31 '10 at 15:32

Your Answer

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

Browse other questions tagged or ask your own question.