Near-linear time expander decomposition in practice

Sammanfattning: An expander decomposition is a partitioning of vertices such that each partition is an induced expander. Recently Saranurak and Wang [SW19] gave a randomized algorithm for computing expander decompositions in O(Ø-1m log4m) time. This was the first near linear time algorithm with respect to the number of edges m. We present the first complete implementation of this algorithm. We suggest, implement, and evaluate modifications to the algorithm which improve performance in practice. On synthetic graphs the implementation successfully finds the intended partitionings. Graphs from a number of real world applications are used to measure execution time and partition quality. We find that the implementation behaves correctly but that the time and quality guarantees are associated with large constant factors.