This paper addresses the problem of finding fair orientations for a task graph, where each vertex represents an agent and each task represents a mutation. A task has a marginal utility of 0 for an agent if the agent is not adjacent to the corresponding mutation. Zhou et al. (IJCAI, 2024) analyzed the complexity of determining whether a mixed graph of goods and tasks has EFX directionality and conjectured that determining whether a graph containing only tasks has EFX directionality is NP-complete. This paper addresses this conjecture by providing a polynomial-time algorithm for finding EF1 and EFX directionality for a graph containing only tasks, even in the presence of self-loops. Surprisingly, this algorithm reveals an unexpected separation between the cases of goods and tasks (determining whether a graph containing only goods has EFX directionality was shown to be NP-complete by Christodoulou et al. (EC, 2023)). Furthermore, this paper shows that the problem of EF1 and EFX directionality for multigraphs is NP-complete.
