图公平定向的参数化复杂度

本文研究了在图中寻找公平定向的计算复杂度，这个问题与公平分配场景相关。它侧重于EF（无嫉妒）定向，这比EFX定向研究得更少。本文的重要性在于其参数化复杂度分析，确定了简单图和多重图的可处理情况、硬度结果和参数化。它还提供了关于EF和EFX定向之间关系的见解，回答了一个悬而未决的问题并改进了现有工作。在定向设置中对慈善事业的研究进一步扩展了本文的贡献。

• •介绍了图中的EF定向研究。
• •应用参数化复杂度分析来识别可处理和不可处理的情况。
• •为简单图和多重图提供了结果。
• •回答了关于EFX定向的结构化参数化复杂度的未解决问题。
• •考虑了定向设置中的慈善事业，建立了用于找到EF(X)定向存在的需要移除的边的最小量的算法。