On the complexity of stable hypergraph matching, stable multicommodity flow and related problems

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.(c) 2022 Published by Elsevier B.V.