Some Improved Results on Fair and Balanced Graph Partitions
New bounds for envy-free and core-stable partitions in social networks...
Vignesh Viswanathan’s new paper, posted on arXiv on May 5, 2026, tackles the long‑standing problem of partitioning an undirected graph (representing a social network) into k equally sized parts. Each node (agent) gains utility from the number of neighbors assigned to the same part. The goal is to produce a partition that is both balanced and fair under two rigorous definitions: envy‑freeness (no node wants to move to another part) and core stability (no subset of n/k nodes can form a new part where everyone gains).
Viswanathan proves that for any graph with n nodes and maximum degree Δ, a balanced partition exists that is simultaneously O(max{√Δ, k²} ln n)-approximately envy‑free and in the (k+o(k))-approximate core. These guarantees match or improve the best known separate bounds. When k=2, he shows a (1.618+o(1))-core exists and a (2+ε)-core can be computed in polynomial time, directly answering two open questions from Li et al. (AAAI 2023). The paper also notes that if we slightly relax the balancedness constraint, the desirable partitions can be computed efficiently.
- Proves existence of balanced partitions that are O(max{√Δ, k²} ln n)-approximately envy-free and (k+o(k))-approximate core for any graph.
- For k=2, achieves a (1.618+o(1))-core existence and polynomial-time (2+ε)-core computation, resolving open problems from Li et al. 2023.
- Efficient computation is possible if balancedness constraint is slightly relaxed, bridging theory and practice for large social network partitioning.
Why It Matters
Fair and stable allocation of agents to groups in social networks has direct applications in community detection, recommendation systems, and resource allocation.