Parameterized complexity of incomplete connected fair division

Abstract Fair division of resources among competing agents is a fundamental problem in computational social choice and game theory. It has been intensively studied for various types of items ( divisible and indivisible ) and under various notions of fairness . We focus on Connected Fair Division ( $$\textsf{CFD}$$ ), the variant of fair division on graphs, where the resources are modeled as an item graph . Here, each agent has to be assigned a connected subgraph of the item graph, and each item has to be assigned to some agent. We introduce a generalization of $$\textsf{CFD}$$ , termed Incomplete $$\textsf{CFD}$$ ( $$\textsf{ICFD}$$ ), where exactly p vertices of the item graph should be assigned to the agents. This might be useful, in particular when the allocations are intended to be “economical” as well as fair. We consider four well-known notions of fairness: $$\textsf{PROP}$$ , $$\textsf{EF}$$ , $$\textsf{EF1}$$ , $$\textsf{EFX}$$ . First, we prove that $$\textsf{EF}$$ - $$\textsf{ICFD}$$ , $$\textsf{EF1}$$ - $$\textsf{ICFD}$$ , and $$\textsf{EFX}$$ - $$\textsf{ICFD}$$ are W[1]-hard parameterized by p plus the number of agents, even for graphs having constant vertex cover number ( $$\textsf{vcn}$$ ). In contrast, we present a randomized $$\textsf{FPT}$$ algorithm for $$\textsf{PROP}$$ - $$\textsf{ICFD}$$ parameterized only by p . Additionally, we prove both positive and negative results concerning the kernelization complexity of $$\textsf{ICFD}$$ under all four fairness notions, parameterized by p , $$\textsf{vcn}$$ , and the total number of different valuations in the item graph ( $$\textsf{val}$$ ).