본 논문은 각 정점이 에이전트를 나타내고, 각 변이 과제를 나타내는 과제 그래프의 공정한 방향 설정을 찾는 문제를 다룬다. 과제는 해당 변이 에이전트에 인접하지 않은 경우 에이전트에 대한 한계 효용이 0이다. Zhou 등 (IJCAI, 2024)은 상품과 과제가 혼합된 그래프가 EFX 방향성을 갖는지 여부를 결정하는 복잡성을 분석하고, 과제만 포함하는 그래프가 EFX 방향성을 갖는지 여부를 결정하는 것은 NP-완전하다고 추측했다. 본 논문은 자체 루프가 있는 경우에도 과제만 포함하는 그래프의 EF1 및 EFX 방향성을 찾는 다항 시간 알고리즘을 제공함으로써 이 추측을 해결한다. 놀랍게도, 이는 상품과 과제의 경우 사이에 예상치 못한 분리를 보여준다 (상품만 포함하는 그래프가 EFX 방향성을 갖는지 여부를 결정하는 것은 Christodoulou 등 (EC, 2023)에 의해 NP-완전으로 밝혀졌다). 또한, 본 논문은 다중 그래프에 대한 EF1 및 EFX 방향 설정 문제가 NP-완전임을 보여준다.
