2 Search Results for "Ishizuka, Takashi"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.45

Scarf’s Algorithm on Arborescence Hypergraphs

Authors: Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He, and Jay Sethuraman

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

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 hypergraphs, 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 polytopes.

Cite as

Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He, and Jay Sethuraman. Scarf’s Algorithm on Arborescence Hypergraphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.ICALP.2025.45,
  author =	{Chandrasekaran, Karthekeyan and Faenza, Yuri and He, Chengyue and Sethuraman, Jay},
  title =	{{Scarf’s Algorithm on Arborescence Hypergraphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{45:1--45:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.45},
  URN =		{urn:nbn:de:0030-drops-234220},
  doi =		{10.4230/LIPIcs.ICALP.2025.45},
  annote =	{Keywords: Scarf’s algorithm, Arborescence Hypergraphs, Stable Matchings}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.11

On the Complexity of Stable Fractional Hypergraph Matching

Authors: Takashi Ishizuka and Naoyuki Kamiyama

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system. Aharoni and Fleiner proved that there exists a stable fractional matching in every hypergraphic preference system. Furthermore, Kintali, Poplawski, Rajaraman, Sundaram, and Teng proved that the problem of finding a stable fractional matching in a hypergraphic preference system is PPAD-complete. In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is bounded by some constant. The proof by Kintali, Poplawski, Rajaraman, Sundaram, and Teng implies the PPAD-completeness of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is 5. In this paper, we prove that (i) this problem is PPAD-complete even if the maximum degree is 3, and (ii) if the maximum degree is 2, then this problem can be solved in polynomial time. Furthermore, we prove that the problem of finding an approximate stable fractional matching in a hypergraphic preference system is PPAD-complete.

Cite as

Takashi Ishizuka and Naoyuki Kamiyama. On the Complexity of Stable Fractional Hypergraph Matching. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ishizuka_et_al:LIPIcs.ISAAC.2018.11,
  author =	{Ishizuka, Takashi and Kamiyama, Naoyuki},
  title =	{{On the Complexity of Stable Fractional Hypergraph Matching}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.11},
  URN =		{urn:nbn:de:0030-drops-99590},
  doi =		{10.4230/LIPIcs.ISAAC.2018.11},
  annote =	{Keywords: fractional hypergraph matching, stable matching, PPAD-completeness}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2018

Refine by Author
1 Chandrasekaran, Karthekeyan
1 Faenza, Yuri
1 He, Chengyue
1 Ishizuka, Takashi
1 Kamiyama, Naoyuki
Show More...

Refine by Series/Journal
2 LIPIcs

Refine by Classification
2 Theory of computation → Design and analysis of algorithms

Refine by Keyword
1 Arborescence Hypergraphs
1 PPAD-completeness
1 Scarf’s algorithm
1 Stable Matchings
1 fractional hypergraph matching
Show More...

2 Search Results for "Ishizuka, Takashi"

Scarf’s Algorithm on Arborescence Hypergraphs

Abstract

Cite as

On the Complexity of Stable Fractional Hypergraph Matching

Abstract

Cite as

Thanks for your feedback!

Could not send message