为只有任务的图设计了公平定向的多项式时间算法，打破了一般认知。
Polynomial-Time Algorithms for Fair Orientations of Chores
- 针对仅含任务的图，提出求解EF1和EFX定向的多项式时间算法。
- 证明了仅含任务的图存在公平定向可高效判定，而仅有资源时则为NP难。
- 适用于研究公平分配、图论与机制设计的学者，尤其关注任务分配场景。
本文研究仅含任务的图的公平定向问题，其中每个顶点代表一个参与者，每条边代表一项任务，若任务对应的边不关联某参与者的顶点，则该任务对其边际效用为零。近期周等人（IJCAI, 2024）分析了混合资源与任务图是否存在EFX定向的复杂性，并猜想仅含任务的图是否存在EFX定向是NP完全问题。本文通过给出多项式时间算法，解决了该猜想：只要存在，即可高效找到满足EF1和EFX条件的定向，即使包含自环。这一结果揭示了一个令人惊讶的差异：仅含资源的图判断是否存在EFX定向是NP完全的（Christodoulou等，EC, 2023），而仅含任务的图却可在多项式时间内解决。此外，我们还证明了多图情形下的EF1和EFX定向问题是NP完全的。
原文摘要 · Abstract (English)
This paper addresses the problem of finding fair orientations of graphs of chores, in which each vertex corresponds to an agent, each edge corresponds to a chore, and a chore has zero marginal utility to an agent if its corresponding edge is not incident to the vertex corresponding to the agent. Recently, Zhou et al. (IJCAI, 2024) analyzed the complexity of deciding whether graphs containing a mixture of goods and chores have EFX orientations, and conjectured that deciding whether graphs containing only chores have EFX orientations is NP-complete. We resolve this conjecture by giving polynomial-time algorithms that find EF1 and EFX orientations of graphs containing only chores if they exist, even if there are self-loops. Remarkably, our result demonstrates a surprising separation between the case of goods and the case of chores, because deciding whether graphs containing only goods have EFX orientations was shown to be NP-complete by Christodoulou et al. (EC, 2023). In addition, we show the EF1 and EFX orientation problems for multigraphs to be NP-complete.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。