hu / en

Csáji Gergely párosításelméleti cikke megjelent a Theoretical Computer Science szakfolyóiratban


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

Gergely Csáji
    • 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.
Theoretical Computer ScienceAbstract

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.


Keywords: PPAD, Stable matching, Hospitals/Residents problem, Stable hypergraph matching, Stable flow