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

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.