A Graph Decomposition motivated by the Geometry of Randomized Rounding

Abstract

We introduce a graph decomposition which exists for all simple, connected graphs $G=(V,E)$. The decomposition $V=A\cup B\cup C$ is such that each vertex in $A$ has more neighbors in $B$ than in $A$ and vice versa. $C$ is `balanced': each $v\in C$ has the same number of neighbours in $A$ and $B$. These decompositions arise naturally from the behavior of an associated dynamical system (`Randomized Rounding') on $({\mathbb{S}}^1{)}^{|V|}$. Connections to judicious partitions and the \textsc{MaxCut} problem (in particular the Burer-Monteiro-Zhang heuristic) are being discussed.