2024/11/27 by Ramin Javadi, Javadi, Ramin, Hossein Shokouhi +1 · 1 citation
Economics, Econometrics and Finance · Mathematics · Decision Sciences · #Game Theory and Voting Systems #Advanced Causal Inference Techniques #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2411.18367
Given a bipartite graph G=(U∪ V,E), a left-perfect many-to-one matching is a subset M ⊆ E such that each vertex in U is incident with exactly one edge in M. If U is partitioned into some groups, the matching is called fair if for every v∈ V, the difference between the number of vertices matched with v in any two groups does not exceed a given threshold. In this paper, we investigate parameterized complexity of fair left-perfect many-to-one matching problem with respect to the structural parameters of the input graph. In particular, we prove that the problem is W[1]-hard with respect to the feedback vertex number, tree-depth and the maximum degree of U, combined. Also, it is W[1]-hard with respect to the path-width, the number of groups and the maximum degree of U, combined. In the positive side, we prove that the problem is FPT with respect to the treewidth and the maximum degree of V. Also, it is FPT with respect to the neighborhood diversity of the input graph (which implies being FPT with respect to vertex cover and modular-width). Finally, we prove that the problem is FPT with respect to the tree-depth and the number of groups.