Brand, Cornelius and Ganian, Robert and Kalyanasundaram, Subrahmanyam and Inerney, Fionn Mc (2025) The complexity of optimizing atomic congestion. ARTIFICIAL INTELLIGENCE, 338: 104241. ISSN 0004-3702, 1872-7921
Full text not available from this repository. (Request a copy)Abstract
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | PARAMETERIZED COMPLEXITY; Atomic congestion games; System optimum; Routing; Parameterized complexity; Slim treecut width |
| Subjects: | 000 Computer science, information & general works > 004 Computer science |
| Divisions: | Informatics and Data Science > General computer science > Chair of Algorithms and Complexity Theory (Prof. Dr. Radu Curticapean) |
| Depositing User: | Dr. Gernot Deinzer |
| Date Deposited: | 24 Mar 2026 07:24 |
| Last Modified: | 24 Mar 2026 07:24 |
| URI: | https://pred.uni-regensburg.de/id/eprint/64676 |
Actions (login required)
 |
View Item |
