As stated in the documentation,

Note that potentially there are exponentially many paths between two vertices of a graph, especially if your graph is lattice-like.

In other words, it is entirely expected that as the size of the graph increases, you will hit a performance wall. A faster implementation is not likely to help much for such problems. “Brute-force” approaches to speedup, such as faster computers or parallelization definitely would not help. It would only make make *slightly* larger graphs feasible.

I am not familiar with the specific implementation used in igraph, and how much better one can get. Perhaps better implementations are possible. My point is that since the number of results is exponentially large, no algorithm will be better than exponential—all of them will hit a performance wall at some graph size.

The Python interface of igraph exposes the function implemented in the C core. You are already using it.