Leírás
EGERVÁRY SZEMINÁRIUM
Abstract: We study stable multicommodity flows, stable hypergraph
matchings and some related problems, like the Hospital-Resident-Couple
(hrc) problem. We give another 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 are 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. Finally, we give polynomial-time
algorithms that can find stable integral matchings in some special
classes of hypergraphs.