2026-07-22T02:01:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25110 2026-02-09T08:06:17Z ddc:004 open_access

Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division E S, Ajaykrishnan Lokshtanov, Daniel Envy-Free Incomplete Connected Fair Division Efficient Parameterized Approximation Scheme W[1]-hardness We study the problem of Envy-Free Incomplete Connected Fair Division, where exactly p vertices of an undirected graph must be allocated to agents such that each agent receives a connected share and does not envy another agent’s share. Focusing on agents with additive valuations, we show that the problem remains computationally hard when parameterized by p and the number of agents. This result holds even for star graphs and with the input numbers given in unary representation, thereby resolving an open problem posed by Gahlawat and Zehavi (FSTTCS 2023). In stark contrast, we show that if one is willing to tolerate even the slightest amount of envy, then the problem becomes efficient with respect to the natural parameters. Specifically, we design an Efficient Parameterized Approximation Scheme parameterized by p and the number of agent types. Our algorithm works on general graphs and remains efficient even when the input numbers are provided in binary representation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ajaykrishnan E S and Daniel Lokshtanov 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.29 urn:nbn:de:0030-drops-251101 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.29 eng https://creativecommons.org/licenses/by/4.0/legalcode