Incrementalization of Graph Partitioning Algorithms
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
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.
