EF(X) Orientations: A Parameterized Complexity Perspective
For researchers in fair division and parameterized complexity, this work fills a gap by analyzing EF orientations and improving understanding of EFX orientations, though results are incremental in nature.
This paper initiates the study of EF (envy-free) orientations in graphs, a fair division model where edges are allocated to adjacent agents. It provides tractability and hardness results under parameterized complexity, with many results transferring to EFX orientations, answering an open question on structural parameterized complexity for polynomially-bounded valuations.
The concept of fair orientations in graphs was introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa in 2023, naturally modeling fair division scenarios in which resources are only contested by neighbors. In this model, vertices represent agents and undirected edges represent goods; edges have to be oriented towards one of their endpoints, i.e., allocated to one of their adjacent agents. Although EFX orientations (envy-free up to any good) have been extensively studied in this setting, EF orientations (envy-free) remain unexplored. In this work, we initiate their study, mostly under the lens of parameterized complexity, presenting various tractable cases, hardness results, and parameterizations. Our results concern both simple graphs and multigraphs. Interestingly, many of our results transfer to EFX orientations, thus complementing and improving upon previous work; notably, we answer an open question regarding the structural parameterized complexity of the latter problem on graphs of polynomially-bounded valuations. We also show that EF orientations are tractable in cases in which EFX orientations are not, particularly for binary valuations. Lastly, we consider charity in the orientation setting, establishing algorithms for finding the minimum amount of edges that have to be removed from a graph in order for EF(X) orientations to exist.