given a matrix A I know I can perform A^n = path length from j to v for some entry [j,v] to find paths to v. As I perform this iteration for n = largest path in A times I find entries along the main diagonal which shows a path from a vertex to itself-- a cycle. I now need to attribute one or more of the connections to connections which form the cycle(s) for that vertex v such that when I remove those connections for all such vertices my graph is acyclic. The operation must be deterministic for a given graph A.
I want to remove no more than one connection per cycle. I choose one vertex in every cycle to break the cycle. (I do this deterministically by finding the closest vertex to some designated set of root vertices in the graph)
Currently I can see that if I iterate through removing connections from v I can rerun the cycle detection algorithm A^n from n = 1 and see if the cycle was broken but this becomes a factorial search when considering v is a member of multiple, independent cycles.
I suspect that if some vertex j is also part of a cycle, the connection [j,v] can be said to be the connection which makes a cycle with v but I worry this is true for some but not all [j,v].
Small Hint: If $[A^n]_{i,j} = [A]_{j,i} = 1$ for some $n$, then the connection $j,i$ is in a cicle.