Abstract
We analyze the (parameterized) computational complexity of "fair" variants of bipartite manytoone matching, where each vertex from the "left" side is matched to exactly one vertex and each vertex from the "right" side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices. Assuming that each vertex from the left side has one color modeling its attribute, we study two fairness criteria. In one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is relevant when finding manytoone matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively.
We show that finding a fair manytoone matching is NPhard even for three colors and maximum degree five. Our main contribution is the design of fixedparameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. To establish the correctness of our integer programs, we prove a new separation result, inspired by Frank’s separation theorem [Frank, Discrete Math. 1982], which may also be of independent interest. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side.
BibTeX  Entry
@InProceedings{boehmer_et_al:LIPIcs.ICALP.2022.27,
author = {Boehmer, Niclas and Koana, Tomohiro},
title = {{The Complexity of Finding Fair ManyToOne Matchings}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {27:127:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16368},
URN = {urn:nbn:de:0030drops163680},
doi = {10.4230/LIPIcs.ICALP.2022.27},
annote = {Keywords: Graph theory, polynomialtime algorithms, NPhardness, FPT, ILP, color coding, submodular and supermodular functions, algorithmic fairness}
}
Keywords: 

Graph theory, polynomialtime algorithms, NPhardness, FPT, ILP, color coding, submodular and supermodular functions, algorithmic fairness 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 