Systematic Cross-System Optimization of Parallel Hypergraph K-Core Decomposition: An Empirical Study
Two independent families of parallel algorithms exist for hypergraph k-core decomposition—the HK codebase (OpenMP, vertex-centric) and HyperCD (ParlayLib, edge-centric with frontier scheduling). Yet work that systematically compares them at the level of individual optimization flags is surprisingly scarce. We constructed 10 new HK variants by toggling 7 compile-time preprocessor flags, benchmarked them alongside 5 HyperCD variants on 7 real-world datasets (489 timed runs at 32 threads), and probed which optimizations actually drive the performance gap. The first seven constructed variants improve on the official baseline by 21% through per-dataset routing, with three cross-pollinated variants adding another 7%. The strongest HK variants sit at an Amdahl’s Law ceiling—their parallel efficiency is lower than the naive baseline. A scalability analysis across 2–32 threads confirms that HK scales with thread count (3.1×–6.2×) while HyperCD does not (∼1.0×). Adding HyperCD through a size-based routing rule yields a combined 1.46× cumulative speedup, from 27.05 s down to 18.63 s, with all results verified byte-for-byte against golden baselines.