Problem

Degree splitting

Undirected degree splitting colors the edges of a graph $G = (V, E)$ red and blue so that every node has about as many red as blue edges; directed degree splitting orients the edges so that every node has about as many outgoing as incoming edges. The discrepancy at a node is the difference between the two numbers, and the problem is parametrized by the largest discrepancy allowed.

Runtimes are given in rounds, in terms of the number of nodes $n$ and the maximum degree $\Delta$; $\varepsilon$ is a fixed constant. A discrepancy of $\varepsilon \deg(v) + \mathcal{O}(1)$ at every node is compared as $\varepsilon\Delta$.

An undirected degree splitting A wheel with six outer nodes, its edges colored red and blue: the center has three edges of each color, and every outer node has two edges of one color and one of the other.
The center has three edges of each color; the outer nodes have odd degree, so discrepancy $1$ is the best possible there.