Scarf's Algorithm on Arborescence Hypergraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915048124841984 |
|---|---|
| author | Chandrasekaran, Karthekeyan Faenza, Yuri He, Chengyue Sethuraman, Jay |
| author_facet | Chandrasekaran, Karthekeyan Faenza, Yuri He, Chengyue Sethuraman, Jay |
| contents | Scarf's algorithm--a pivoting procedure that finds a dominating extreme point in a down-monotone polytope--can be used to show the existence of a fractional stable matching in hypergraphs. The problem of finding a fractional stable matching in a hypergraph, however, is PPAD-complete. In this work, we study the behavior of Scarf's algorithm on arborescence hypergraphs, the family of hypergraphs in which hyperedges correspond to the paths of an arborescence. For arborescence hypergraphs, we prove that Scarf's algorithm can be implemented to find an integral stable matching in polynomial time. En route to our result, we uncover novel structural properties of bases and pivots for the more general family of network hypergraphs. Our work provides the first proof of polynomial-time convergence of Scarf's algorithm on hypergraphic stable matching problems, giving hope to the possibility of polynomial-time convergence of Scarf's algorithm for other families of polytope. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03397 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Scarf's Algorithm on Arborescence Hypergraphs Chandrasekaran, Karthekeyan Faenza, Yuri He, Chengyue Sethuraman, Jay Discrete Mathematics Combinatorics 90C49 F.2.2 Scarf's algorithm--a pivoting procedure that finds a dominating extreme point in a down-monotone polytope--can be used to show the existence of a fractional stable matching in hypergraphs. The problem of finding a fractional stable matching in a hypergraph, however, is PPAD-complete. In this work, we study the behavior of Scarf's algorithm on arborescence hypergraphs, the family of hypergraphs in which hyperedges correspond to the paths of an arborescence. For arborescence hypergraphs, we prove that Scarf's algorithm can be implemented to find an integral stable matching in polynomial time. En route to our result, we uncover novel structural properties of bases and pivots for the more general family of network hypergraphs. Our work provides the first proof of polynomial-time convergence of Scarf's algorithm on hypergraphic stable matching problems, giving hope to the possibility of polynomial-time convergence of Scarf's algorithm for other families of polytope. |
| title | Scarf's Algorithm on Arborescence Hypergraphs |
| topic | Discrete Mathematics Combinatorics 90C49 F.2.2 |
| url | https://arxiv.org/abs/2412.03397 |