Advances in Distributed Graph Algorithms and Network Sovereignty

The field of distributed graph algorithms is moving towards a deeper understanding of the role of randomness and network structure in solving locally checkable labeling problems. Recent research has made significant progress in characterizing the complexity of degree splitting problems, such as edge coloring and orientation, and has identified precise boundaries between tractable and intractable subproblems. Additionally, there is a growing interest in network sovereignty, with novel metrics and algorithms being proposed to measure and maximize network sovereignty. Noteworthy papers in this area include: Shift Bribery over Social Networks, which studies the problem of shift bribery in social networks and provides a detailed complexity landscape. On the Complexity of Distributed Edge Coloring and Orientation Problems, which makes a step towards answering the question of which problems can be solved exponentially faster using randomization. Distributed (Δ+1)-Coloring in Graphs of Bounded Neighborhood Independence, which significantly improves the result for (Δ+1)-coloring in graphs of neighborhood independence θ=O(1). How to build a sovereign network, which proposes a novel metric to measure network sovereignty, the Cut Set Coloring (CSC) score. On Robust Popular Matchings with Tie-Bounded Preferences and Stable Matchings with Two-Sided Ties, which analyses the cases when a robust popular matching exists in the one-sided model and proposes a polynomial-time algorithm to decide if there exists a robust popular matching.

Sources

Shift Bribery over Social Networks

On the Complexity of Distributed Edge Coloring and Orientation Problems

Distributed $(\Delta+1)$-Coloring in Graphs of Bounded Neighborhood Independence

NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework

How to build a sovereign network? - A proposal to measure network sovereignty

How to build a sovereign network? -- A proposal to measure network sovereignty

On Robust Popular Matchings with Tie-Bounded Preferences and Stable Matchings with Two-Sided Ties

Why Districting Becomes NP-hard

Built with on top of