License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.11
URN: urn:nbn:de:0030-drops-99590
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9959/
Go to the corresponding LIPIcs Volume Portal

Ishizuka, Takashi ; Kamiyama, Naoyuki

On the Complexity of Stable Fractional Hypergraph Matching

pdf-format:
LIPIcs-ISAAC-2018-11.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{ishizuka_et_al:LIPIcs:2018:9959,
  author =	{Takashi Ishizuka and Naoyuki Kamiyama},
  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 =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9959},
  URN =		{urn:nbn:de:0030-drops-99590},
  doi =		{10.4230/LIPIcs.ISAAC.2018.11},
  annote =	{Keywords: fractional hypergraph matching, stable matching, PPAD-completeness}
}

Keywords: fractional hypergraph matching, stable matching, PPAD-completeness
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI