Existence of completely stable flow

From Egres Open
Jump to: navigation, search

Is there a polynomial algorithm that decides whether a network with preferences has a completely stable flow?


Remarks

The notion of stable flow was introduced by Fleiner [1] who proved that every network with preferences has a stable flow. This generalizes the result of Baïou and Balinski [2] 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. It is open whether the existence of a completely stable flow can be decided in polynomial time.

References

  1. T. Fleiner, On stable matchings and flows, DOI link, preliminary EGRES report.
  2. M. Baïou, M. Balinski, The stable allocation (or ordinal transportation) problem, Math. Oper. Res. 27 (2002), 485-503. DOI link.