3
$\begingroup$

I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) from a node i to a node j of length p. For instance, i->j is of length 2 if the edge i->j exists, i->k->j is of length 3, etc...). The graph is either given as an adjacency matrix or adjacency lists. In my very special case, I'm searching for cycles 0->...->0 of given length, but I'm pretty sure I'm gonna need the more general case i->...->j.

Right now, I'm dynamically storing paths from k to j of length q in a matrix Z[k][q], and since I need Z[i][p], I first compute all the Z[j][p-1] for i->j, then append i to them.

The problem is that this approach uses an awful lot of memory and doesn't scale very nicely for large graphs. Any advice on this ?

$\endgroup$
  • 1
    $\begingroup$ Note that the length of a path is usually defined to be the number of edges in the path, not the number of vertices. Thus, if there is an edge from $i$ to $j$, then those vertices are normally said to be at distance 1, not 2. $\endgroup$ – David Richerby May 25 '15 at 8:04
  • 1
    $\begingroup$ What do you mean by "efficiently enumerating"? There can be exponentially many paths of a given length in a graph (consider the complete graph) so any algorithm must take at least exponential time in total, in the worst case. For enumeration algorithms, we normally talk about working with polynomial delay, i.e., the algorithm does at most a polynomial amount of work between each output in the enumeration. $\endgroup$ – David Richerby May 25 '15 at 8:05
  • $\begingroup$ Thanks for the remark. That's of course what I meant and I was wondering how to implement an algorithm that wouldn't consume as much memory as mine while being as efficient (since I do not seem to be doing any unnecessary computations). $\endgroup$ – Mrktn May 25 '15 at 10:21
  • 1
    $\begingroup$ The "Related" column to the right contains several closely related questions. $\endgroup$ – Raphael May 25 '15 at 10:35
3
$\begingroup$

It's not possible to solve this problem "efficiently". There can be exponentially many paths of a given length, so enumerating all of them is not feasible in large graphs.

Your dynamic programming approach is a pretty good one, though you might be able to improve it by not storing the paths explicitly but instead storing the paths as linked lists or using pointers, so that you only use $O(1)$ storage per path, letting paths share their common suffixes (if you do not do this already).

$\endgroup$
  • $\begingroup$ While your answer is good, I would like to comment that you can enumerate them efficiently in the output size, e.g., enumerate with polynomial delay. $\endgroup$ – Pål GD May 25 '15 at 9:50
  • $\begingroup$ Thank you Tom for these guidelines. However I do not quite get how to implement this trick without losing the dynamical part of my algorithm ; that is, when a Z[k][q] has been computed, I can access it in constant time. Is there a way to achieve the "polynomial in output size" time Pål is hinting at without consuming as much memory as I would earlier ? $\endgroup$ – Mrktn May 25 '15 at 10:15
  • 1
    $\begingroup$ @Mrktn What I am hinting at is that instead of storing each path explicitly as a list of vertices (requiring $O(n)$ space) you store just a single vertex with a pointer to the next, like in a linked list. Since in the DP you obtain each path as the extension of another path, you can let all paths that are obtained by extending a given path share the same tail section. $\endgroup$ – Tom van der Zanden May 25 '15 at 11:18

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.