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 ?

Improve this question
$\endgroup$
4
  • 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, 2015 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, 2015 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, 2015 at 10:21
  • 1
    $\begingroup$ The "Related" column to the right contains several closely related questions. $\endgroup$
    – Raphael ♦
    May 25, 2015 at 10:35

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
3
  • $\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, 2015 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, 2015 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, 2015 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.