Existence of completely stable flow
Is there a polynomial algorithm that decides whether a network with preferences has a completely stable flow?
Tamás Fleiner, Zsuzsanna Jankó, Ildikó Schlotter, and Alexander Teytelboym [1] proved that the problem is NP-complete.
Remarks
The notion of stable flow was introduced by Fleiner [2] who proved that every network with preferences has a stable flow. This generalizes the result of Baïou and Balinski [3] on the existence of a stable allocation in vertex- and edge-capacitated bipartite graphs.
A completely stable flow is a stable flow where there is no unsaturated cycle. Given a stable flow, we may increase the flow along an unsaturated cycle, but this operation may destroy the stability. In fact, Fleiner showed that there exist networks with preferences that do not have a completely stable flow.
References
- ↑ T. Fleiner, Zs. Jankó, I. Schlotter, A. Teytelboym, Complexity of stability in trading networks, arXiv:1805.08758, 2019
- ↑ T. Fleiner, On stable matchings and flows, DOI link, preliminary EGRES report.
- ↑ M. Baïou, M. Balinski, The stable allocation (or ordinal transportation) problem, Math. Oper. Res. 27 (2002), 485-503. DOI link.
