# The Complexity of Optimizing Atomic Congestion

arXiv: https://arxiv.org/abs/2312.10219 · HTML: https://mlsanity.com/paper/2312.10219/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 69 references that are in the map.
- First posted on arXiv 15 Dec 2023.

## Builds on (most cited first, 23 of 23)

- [Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis](https://mlsanity.com/paper/2004.14724/) (2020)
- [Parameterized Complexity Results for Exact Bayesian Network Structure Learning](https://mlsanity.com/paper/1402.0558/) (2014)
- [Coordinating Followers to Reach Better Equilibria: End-to-End Gradient Descent for Stackelberg Games](https://mlsanity.com/paper/2106.03278/) (2021)
- [Parameterized Algorithms for the Matrix Completion Problem](https://mlsanity.com/paper/1804.03423/) (2018)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [Individual-Based Stability in Hedonic Diversity Games](https://mlsanity.com/paper/1911.08669/) (2019)
- [Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment](https://mlsanity.com/paper/2104.00098/) (2021)
- [The Complexity Landscape of Decompositional Parameters for ILP](https://mlsanity.com/paper/1809.00585/) (2018)
- [Hedonic Diversity Games: A Complexity Picture with More than Two Colors](https://mlsanity.com/paper/2202.09210/) (2022)
- [Traffic Optimization For a Mixture of Self-interested and Compliant Agents](https://mlsanity.com/paper/1709.09569/) (2017)
- [On Structural Parameterizations of the Edge Disjoint Paths Problem](https://mlsanity.com/paper/1711.02076/) (2017)
- [Leadership in Congestion Games: Multiple User Classes and Non-Singleton Actions (Extended Version)](https://mlsanity.com/paper/1905.13108/) (2019)
- [The Power of Cut-Based Parameters for Computing Edge Disjoint Paths](https://mlsanity.com/paper/1808.03496/) (2018)
- [The Complexity of Binary Matrix Completion Under Diameter Constraints](https://mlsanity.com/paper/2002.05068/) (2020)
- [Stable Roommate Problem with Diversity Preferences](https://mlsanity.com/paper/2004.14640/) (2020)
- [Algorithmic Applications of Tree-Cut Width](https://mlsanity.com/paper/2206.00752/) (2022)
- [New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness](https://mlsanity.com/paper/1603.01740/) (2016)
- [Parameterized complexity of the MINCCA problem on graphs of bounded decomposability](https://mlsanity.com/paper/1605.00532/) (2016)
- [Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments](https://mlsanity.com/paper/1806.09683/) (2018)
- [Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming](https://mlsanity.com/paper/1907.06688/) (2019)
- [Multi-Leader Congestion Games with an Adversary](https://mlsanity.com/paper/2112.07435/) (2021)
- [Delay-Robust Routes in Temporal Graphs](https://mlsanity.com/paper/2201.05390/) (2022)
- [Slim Tree-Cut Width](https://mlsanity.com/paper/2206.15091/) (2022)

## Abstract (arXiv)

Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies -- that is, a centrally planned routing that minimizes the average cost of agents -- is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.