摘要
公平定向的概念由 Christodoulou, Fiat, Koutsoupias 和 Sgouritsa 于 2023 年提出，旨在自然建模资源仅由邻居争用的公平分配场景。在这一模型中，顶点代表代理，未定向边代表商品；边必须定向到其一个端点，即分配给其相邻的代理。
虽然 EFX 定向（对任何商品的无嫉妒）在这一背景下得到了广泛研究，但 EF 定向（无嫉妒）仍未被探索。本研究初步探讨了 EF 定向，主要从参数化复杂性的角度出发，提出了多种可处理情况、困难结果和参数化。我们的结果涉及简单图和多重图。
有趣的是，我们的许多结果可以转移到 EFX 定向上，从而补充和改进了之前的工作；特别是，我们回答了关于多项式界值图中该问题的结构参数化复杂性的一个开放问题。我们还展示了在 EFX 定向不适用的情况下，EF 定向是可处理的，尤其是在二元值情况下。
最后，我们考虑了定向设置中的慈善问题，建立了算法以找到从图中移除的最小边数，以便存在 EF(X) 定向。
博主点评： 本文在公平定向的研究中，首次引入参数化复杂性视角，探索了 EF 定向的多种情况及其与 EFX 定向的关系，为图论中的公平分配问题提供了新的思路和解决方案，具有重要的理论价值和实践意义。