Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.18367 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915037326606336 |
|---|---|
| author | Javadi, Ramin Shokouhi, Hossein |
| author_facet | Javadi, Ramin Shokouhi, Hossein |
| contents | Given a bipartite graph $G=(U\cup V,E)$, a left-perfect many-to-one matching is a subset $M \subseteq 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\in 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18367 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Complexity of Fair Many-to-One Matchings Javadi, Ramin Shokouhi, Hossein Computational Complexity Given a bipartite graph $G=(U\cup V,E)$, a left-perfect many-to-one matching is a subset $M \subseteq 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\in 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. |
| title | Parameterized Complexity of Fair Many-to-One Matchings |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2411.18367 |