Near-optimal edge partitioning via intersecting families

We study the problem of edge partitioning, in which we search for edge partitions of graphs into several parts that are optimal w.r.t. the replication factor. The replication factor of vertex $v$ is the number of parts that contain edges incident to $v$. The goal is to minimize the average/maximum replication factor of vertices while keeping the size of parts almost equal. In particular, we study the case of graphs with $|V|=o(|E|)$ and where the number of parts is significantly lower than the size of the graph. We introduce a new class of edge partitioning algorithms based on our new combinatorial construction -- balanced intersecting systems (BIS). These algorithms guarantee an upper bound for the replication factor for all graphs. - For the case of a constant number of parts, we describe an algorithm that provides an optimal bound for both average and maximum replication factor. Moreover, this algorithm gives an asymptotically optimal partition for random graphs with high probability. - For the case of (slowly enough) growing number of parts $n$, it provides a bound $\sqrt{n}(1 + o(1))$ for the maximum replication factor. This bound improves previously known bounds. For some cases of balance requirements it asymptotically matches the lower bound of $\sqrt{n}$. We show that the algorithms are computationally efficient in terms of computation time, LOCAL and CONGEST models, and can be implemented as stateless streaming algorithms in graph processing frameworks. Our method generalizes a family of algorithms based on symmetric intersecting families (SIF). The abstract inside PDF also gives a brief description of our techniques.