# Return list of k-paths in a network

Consider a network $G(V,E)$ with vertex set $V$ and number of edges $E$ being formed by a pre-defined formation process, with one edge being placed in each step. Now, a k-path is defined as

$(i,j) \in {G \quad s.t \quad x_{ij} = 0 \quad and\quad (x_{im_1} = x_{jm_1} = 1) , .... , (x_{im_k} = x_{jm_k} = 1)}$

$x_{ij} = 1$ if an edge exists between nodes i and j and is 0 otherwise

I'm trying to come up with an efficient algorithm to update the set of k-paths ($k \in {1,2,3}$) with each step in the network formation process.

So far, what I've been doing is pretty inefficient, in that I loop through all the edges to return the list of k-paths at every stage. But I imagine that I will be able to start with an empty network (having all edges belonging to the set of 0-paths) and then developing some scheme to update the elements in the sets (all the sets of higher order k-paths will be Null sets in the beginning).

## 1 Answer

I'm assuming this is a simple graph. Paths of length $1$ are easy. You have that with the adjacency matrix. Paths of length $2$ are equally easy, assuming a simple graph. You simply take the sum of the non-diagonal entries in the upper (or lower) triangular half of $A^{2}$, for $A$ being the adjacency matrix of your graph. $A^{2}$ counts the number of two-walks. Since $G$ is simple, the only two-walks are $P_{2}$, a path of length $2$ (which are counted by the non-diagonal entries); or walking twice along the same edge (in which case, the diagonal entries count the edges). You only consider one half of the matrix, as $A^{n}$ for $n \in \mathbb{N}$ is skew-symmetric. I'll have to think more on $k = 3$.

If you don't mind my asking, could you expand perhaps on your rationale for trying to cache all the paths of $G$, partitioning them by length? I'm wondering if there might be a better way to obtain the same result without the caching.