Theoretical Computer Science, Volume 931, 29 September 2022, Pages 1-16
Stable fractional solutions are PPAD-hard to find in HRC and Stable Family Problem.
The SMF remains hard with constant number of commodities and constant degree.
The stable fractional hypergraph matching problem is hard with many restrictions.
In this paper we study stable multicommodity flows, stable hypergraph matchings and some related problems, like the Hospital-Resident-Couple (hrc) problem. We give a simpler proof of the existence of a stable multicommodity flow by reducing it to scarf. We show that finding a stable fractional solution of a hrc or a 3-dimensional stable matching (stable family) instance is PPAD-complete. Then we derive from these results that the Fractional hypergraph matching problem is PPAD-complete even if all hyperedge sizes and vertex degrees are at most 3. Furthermore, we prove that computing stable multicommodity flows is PPAD-complete even if the number of commodities is 3, the sum of in and out degrees is at most 3 at each vertex and all terminals and sources are the same. We also show that deciding if there exists a stable integer multicommodity flow is NP-complete even with only two commodities and similar restrictions.