TY - GEN
T1 - On the complexity of stable fractional hypergraph matching
AU - Ishizuka, Takashi
AU - Kamiyama, Naoyuki
N1 - Funding Information:
1 This research was supported by JST PRESTO Grant Number JPMJPR1753, Japan.
Funding Information:
This research was supported by JST PRESTO Grant Number JPMJPR1753, Japan.
Publisher Copyright:
© Takashi Ishizuka and Naoyuki Kamiyama;
PY - 2018/12/1
Y1 - 2018/12/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85063689090&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85063689090&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2018.11
DO - 10.4230/LIPIcs.ISAAC.2018.11
M3 - Conference contribution
AN - SCOPUS:85063689090
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 11:1-11:12
BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018
A2 - Liao, Chung-Shou
A2 - Lee, Der-Tsai
A2 - Hsu, Wen-Lian
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th International Symposium on Algorithms and Computation, ISAAC 2018
Y2 - 16 December 2018 through 19 December 2018
ER -