グラフにおける公平な向き付けのパラメータ化された複雑さ

この論文は、公平な分割シナリオに関連する問題である、グラフにおける公平な向き付けを見つけることの計算複雑性を調査しています。 EFX（羨望フリー）配向よりも研究が少ないEF（羨望フリー）配向に焦点を当てています。この論文の重要性は、パラメータ化された複雑さの分析にあり、単純グラフとマルチグラフの両方について、扱いやすいケース、困難な結果、およびパラメータ化を特定しています。また、EFとEFXの配向の関係に関する洞察を提供し、未解決の質問に答え、既存の研究を改善しています。配向設定における慈善の研究は、論文の貢献をさらに拡張しています。