Add parallel implementation of Combinatorial Algorithms

[pnijhara]

NetworkX currently implements many core combinatorial graph primitives in a strictly sequential manner. A clear example is maximal_independent_set, whose current implementation is a randomized serial greedy algorithm. This approach is inherently non-parallelizable and does not reflect the state of the art in parallel/distributed graph processing.

Since nx-parallel aims to provide scalable, concurrency-friendly variants of NetworkX algorithms, it makes sense to introduce parallel implementations of classical combinatorial routines. A foundational starting point is a proper parallel MIS algorithm.

The existing NetworkX MIS is sequential

The current implementation -> https://networkx.org/documentation/stable/_modules/networkx/algorithms/mis.html#maximal_independent_set:

available = V \ (MIS ∪ N(MIS))
while available:
    v = random choice from available
    add v to MIS
    remove v and N(v) from available

Key issues:

1. Exactly one vertex is added per iteration.
   The algorithm performs a strictly serial “pick-one-and-delete-its-neighbors” loop. There is no mechanism for selecting a batch of independent vertices simultaneously.

2. Algorithmic structure = greedy MIS under a random vertex ordering.
   Conceptually, this corresponds to traversing one random permutation π of V and inserting a vertex whenever none of its previously visited neighbors are in MIS. This inherently imposes a total order.

3. Neighborhood checks are performed on the updated graph state.
   After each vertex is added, all its neighbors are removed before the next selection. This makes the next step depend on the results of previous steps, preventing any parallel independence checks.

4. No use of random priorities.
   Parallel MIS algorithms (Luby, Blelloch-Halperin, Bader-Cong, ECL-MIS, etc.) rely on random priority assignments to allow many vertices to compare themselves with neighbors simultaneously.
   The existing implementation does not expose any priority vector that can be evaluated in parallel.

As a result, the current MIS is inherently sequential both in logic and data dependencies.

Parallelize MIS (Luby-style approach)

A standard parallel MIS algorithm assigns a random priority to every vertex once per round, then selects all locally maximal vertices at the same time:

while graph not empty:
    generate random priority for each vertex
    S = { u | priority(u) > priority(v) for all v in N(u) }
    add S to MIS
    remove S ∪ N(S) from graph

Why this is parallel:

• Priority comparisons for all vertices are independent operations.
• Set S can be selected in one parallel pass.
• All vertices in S are guaranteed independent.
• Removing S ∪ N(S) can also be done in parallel.

This matches the PRAM formulation and is widely used in CPU and GPU environments.

PS I am new to nx-parallel, however, I have implemented parallel variants of various combinatorial algorithms such as MIS, Graph Coloring, Matching etc earlier. I think adding this will be a valuable addition to nx-parallel.

Let me know your thoughts.

[dschult]

This is very nicely described. And it seems like it could work.
I have not done something like this so I'm no expert. But it seems good to try this out.
Start with a single function (like mis) and make a PR to implement it.
:)

[pnijhara]

I am starting on it.
Will try to submit a PR on it soon.

[pnijhara]

@dschult, I need a small help. I am stuck after implementing parallel-mis. What I have done till now:

1. Added parallel implementation of MIS at nx_parallel/algorithms/mis.py
2. Added tests for 1 at nx_parallel/tests/test_mis.py
3. Added a benchmark file at benchmarks/benchmarks/bench_mis.py

I am not able to run the benchmarks for this. Is there any other file or change I need to add to run the benchmark and generate a heatmap before submitting a PR?

[dschult]

From that info I can suggest that the test module should be moved to nx_parallel/algorithms/tests/test_mis.py.

I don't see any problem with the file name for the benchmark. But I vaguely recall that asv only works with files that have been added to the repo with a commit. So you might need to commit them locally before doing any timing.

And I would say: go ahead and open the PR -- you can mark it as a "draft" if you prefer that. And then we can look at the contents and even try it ourselves if needed. Then in a comment of that PR you can show the commands you used to try the benchmarking. Hopefully it is just a matter of making a commit.