`all_node_cuts()` performance degrades much faster than predicted by Kanevsky's minimum cut algorithm

[Cerebus]

NetworkX vs igraph. igraph implements Kanevsky's too.

import timeit

import igraph as ig
import networkx as nx


def bigO(g):
    return (2 ** nx.node_connectivity(g)) * (len(g) ** 3)


def runit(i):
    g = nx.grid_2d_graph(i, i)
    O = bigO(g)
    h = ig.Graph.from_networkx(g)
    t = timeit.timeit(lambda: list(nx.all_node_cuts(g)), number=1)
    t2 = timeit.timeit(lambda: ig.GraphBase.minimum_size_separators(h), number=1)
    return dict(i=i, k=nx.node_connectivity(g), n=len(g), O=O, nx_t=t, ig_t=t2)


if __name__ == "__main__":
    results = []
    for i in range(2, 12):
        r = runit(i)
        results.append(r)
        print(r)

Results dataframe w/ percent change calculated for nx_t and ig_t (* 100, b/c humans). Rate of growth is the interesting bit, b/c NetworkX is 100% Python, and igraph is C w/ a python binding. Raw data attached results.json.

    i  k    n        O        nx_t      ig_t  nx_t_pct_chg  ig_t_pct_chg
0   2  2    4      256    0.004447  0.000238           NaN           NaN
1   3  2    9     2916    0.033335  0.000569    649.551704    138.733327
2   4  2   16    16384    0.101915  0.001271    205.725524    123.537768
3   5  2   25    62500    0.143263  0.002748     40.571573    116.194569
4   6  2   36   186624    0.198543  0.006185     38.586098    125.084930
5   7  2   49   470596    0.431762  0.011818    117.465543     91.083902
6   8  2   64  1048576    1.275459  0.022733    195.407745     92.349527
7   9  2   81  2125764    6.076753  0.039182    376.436524     72.357797
8  10  2  100  4000000   32.342393  0.066873    432.231473     70.674632
9  11  2  121  7086244  180.278205  0.109162    457.405282     63.236688

Clearly these implementations are following different growth curves. Kanevsky's algorithm should be growing at $\mathcal{O}(2^{k} n^3)$. NetworkX's growth becomes geometric (or worse).

The cause seems to be for some graph sizes, the number of members of the antichains(L) set explodes---billions of members, in some case---but I have not yet figured out why that happens.

Originally posted by @Cerebus in https://github.com/networkx/networkx/discussions/7989#discussioncomment-12923983