How to calculate the length of cycles in a graph using parallel algorithms in C?

Question

I am getting desprite, because I can't solve this problem. I hope this is the right place to ask for help in this context. The Problem is, that I have a graph that is the union of disjoint directed cycles. Additionally, there are 𝑘 nodes 𝑋(1), ..., 𝑋(𝑘) whose indices are stored in an array 𝑋 of length 𝑘 ≤ 𝑛. The graph is represented by an array 𝑆 of length 𝑛, where 𝑆(𝑖) is the successor node of 𝑖.

I need to calculate the length of the cycle containing each node in 𝑋. The result should be an array 𝑌 of length 𝑘, such that 𝑌(1), ..., 𝑌(𝑘) contains the length of the respective cycle.

Can anyone suggest an algorithm/pseudocode (in C) with a runtime of 𝑂(𝑘 + log 𝑛) and work 𝑂(𝑛) to compute 𝑌?

Any help or pointers would be greatly appreciated!

I could only create this Pseudocode:

for i in {1,...,k} par do

    while S[i] != i

        S[i] = S[ S[i] ]
        Y[i]++

with a runtime of 𝑂(𝑘*log 𝑛) and work 𝑂(𝑘𝑛)

Answer 1

In order to meet your time constraint, you need to start a process for each node, and those processes must be able to collectively process each node's cycle in O(log n) time.

By "processing a cycle", I specifically mean collecting the minimum or maximum of some function over all nodes in the cycle, and broadcasting it to all nodes in the cycle. If you can do that, then your problem can be solved with this constant-length sequence of steps:

1. Find the node with the smallest index in every node's cycle. This node will be the "representative" of each cycle;
2. Find the minimum number of steps from any node in each to the cycle representative.
3. Find the maximum of these minimums. This will be the length of the cycle, which is the number of steps from the representative to itself.

Then you can just look up the cycle length for each of your k target nodes.

To process all the cycles in O(log n) time:

1. For each node i, let T[i] = S[i], let d = 1, and let V[i] be the target statistic for each node. We will maintain invariants that:
   1. T[i] = S^d[i]
   2. V[i] = the min or max of the target statistic over d nodes starting at i. For the "distance to representative" statistic, use n+1 if the representative is unreachable in d steps, and initialize V[i] = 1 for the predecessor of the representative.
2. Then we double d while maintaining the above invariants. While d < n:
   1. V[i] = minOrMax(V[i], V[T[i]]). For distance to representative, use V'[i] = min(V[i],V[T[i]] + d).
   2. T[i] = T[T[i]]
   3. d *= 2

Note that each iteration of the loop in (2) needs to be done effectively synchronously for all nodes. There are local O(1) ways to accomplish this. Basically step d=2n cannot be processed for any node until its predecessors and successors in T are finished reading the results for d=n.

Once d>=n for all nodes, V[i] holds the same min or max value for all nodes in each cycle.