Incrementalization of Graph Partitioning Algorithms

This paper studies incremental graph partitioning. Given a (vertex-cut or edge-cut) partition C(G) of a graph G and updates ΔG to G, it is to compute changes ΔO to C(G), yielding a partition of the updated graph such that (a) the new partition is load-balanced, (b) its cut size is minimum, and (c) the changes ΔO are also minimum. We show that this tri-criteria optimization problem is NP-complete, even when ΔG has a constant size. Worse yet, it is unbounded, i.e., there exists no algorithm that computes such ΔO with a cost that is determined only by the changes ΔG and ΔO. We approach this by proposing to incrementalize widely-used graph partitioners A into heuristically-bounded incremental algorithms AΔ. Given graph G, updates ΔG to G and a partition A(G) of G by A, AΔ computes changes ΔO to A(G) such that (1) applying ΔO to A(G) produces a new partition of the updated graph although it may not be exactly the one derived by A, (2) it retains the same bounds on balance and cut sizes as A, and (3) ΔO is decided by ΔG alone. We show that we can deduce AΔ from both vertex-cut and edge-cut partitioners A, retaining their bounds. Using real-life and synthetic data, we verify the efficiency and partition quality of our incremental partitioners.