The Parameterized Complexity of Connected Fair Division

1 Introduction

The task of allocating a set of indivisible resources among participating agents under a suitably defined notion of "fairness" represents a core research topic in the area of computational social choice [Bouveret and Lang, 2008; Bouveret et al., 2016; Brams and Taylor, 1996]. The classical fair resource allocation problem that arises from this task, FAIR DIVISION, has been extensively studied in the literature, and we now have a fairly good understanding of the problem's complexity under a variety of notions of fairness [Bouveret and Lang, 2008; Budish, 2011; Caragiannis et al., 2019; Plaut and Roughgarden, 2020]. However, in many settings it is desirable to ensure that the allocation respects a certain connectivity restriction on the items allocated to each individual agent-this is easy to substantiate when the items represent immovable assets (e.g., when allocating rooms in a new building to university departments, or in case of corporate split-ups), but can also arise when the items are intangible (e.g., when allocating duties organized in a mind map).

Motivated by these considerations, in 2017 Bouveret et al. (2017) developed a natural framework designed to capture this additional aspect of fair resource allocation: given (1) a set of items represented as vertices of an input graph G, (2) a set A of agents, and (3) a set U of valuation functions specifying the utility of each item for each agent, determine if there exists an allocation of items to agents which is (I) fair (under a suitable notion of fairness), and (II) maintains the connectivity of items assigned to each individual agent. They called this the ϕ-CONNECTED FAIR DIVISION PROBLEM (ϕ-CFD), where ϕ specifies the desired notion of fairness. Their initial results inspired a body of followup work on the model involving, e.g., the incorporation of chores [Aziz et al., 2019], computing so-called maximin share allocations [Greco and Scarcello, 2020], Pareto-optimal allocations [Igarashi and Peters, 2019] and conditions guaranteeing the existence of fair allocations [Bil`o et al., 2019].

In spite of these developments, our understanding of the precise boundaries of computational tractability of ϕ-CFD remains somewhat limited to date. On one hand, the problem is a generalization of the classical ϕ-FAIR DIVISION problem [Bouveret and Lang, 2008; Bouveret et al., 2016], since the problems coincide if G is restricted to the class of complete graphs. But G will not be complete in the typical use case of the model-on the contrary, one may often expect it to be rather sparse, and that is why already the original work introducing the model [Bouveret et al., 2017] initiated the investigation of the problem under various restrictions of the structure of G. Unfortunately, the algorithmic and lower-bound results provided in the original paper as well as in follow-up works [Aziz et al., 2019; Bil`o et al., 2019; Igarashi and Peters, 2019] leave a wide gap between the known boundaries of tractability and the easiest intractable cases. This provides a rather unsatisfactory contrast between ϕ-CFD and other variants of the resource allocation problem, for which we often already have complete complexity landscapes [Bliem et al., 2016a; Bredereck et al., 2018; Eiben et al., 2020].

1.1 Contribution

We perform a comprehensive and in-depth study of the complexity of ϕ-CFD with the aim of identifying the precise cut-off between tractable and intractable classes of instances. In line with previous work on complexity-theoretic aspects of computational social choice [Chen et al., 2017; Chen et al., 2018; Eiben et al., 2018b] and especially fair allocation [Bliem et al., 2016a; Eiben et al., 2020], we employ the parameterized complexity paradigm to obtain a more fine-grained understanding of the (in-)tractability of ϕ-CFD under various restrictions. We focus our analysis on combinations of restrictions on two core components of ϕ-CFD: the structure of the item graph (G) and the set of agents (A). Moreover, all of our results are designed to take into account several perspectives on fairness: proportionality, envyfreeness, and also two prominent relaxations of envy-freeness called EF1 and EFX [Bil`o et al., 2019; Budish, 2011; Caragiannis et al., 2019; Plaut and Roughgarden, 2020].

We begin by observing that the problem remains hopelessly intractable even under extreme restrictions to all other aspects of the input if the valuation function U is allowed to use binary encodings (Proposition 1). That is why we proceed-in line with several previous works in the field [Eiben et al., 2020; Greco and Scarcello, 2020]-under the reasonable assumption that U is encoded in unary.

But even under this assumption, we show that the problem remains surprisingly difficult when one does not apply at least some restriction to the set A of agents. Indeed, while it was already known that proportional CFD is polynomial-time tractable on graphs which are stars [Bouveret et al., 2017], we prove that for all other considered notions of fairness CFD remains NP-hard even on stars (Theorem 2). Moreover, proportional CFD remains NP-hard on paths [Bouveret et al., 2017]. On the other hand, restricting the set of agents alone does not lead to tractability either-even if we only consider instances with just two agents (Proposition 3). So in order to achieve tractability, one needs to assume restrictions on G as well as on A; a single-dimensional approach is not viable.

With the above considerations in mind, we can now proceed to our main algorithmic contributions. First, if we parameterize by the number of agents, then we can solve ϕCFD for all considered fairness notions on an extremely broad range of graphs-not only on trees and more generally graphs of bounded treewidth, but also on dense graph classes such as complete graphs, complete bipartite graphs, cographs, distance-hereditary graphs, and many others. We formalize this by showing that ϕ-CFD is XP-tractable 1 when parameterized by |A| plus the clique-width of G (Theorem 4). Clique-width is among the most general structural parameters of graphs and has found widespread algorithmic applications [Bliem et al., 2016b; Eiben et al., 2018a].

Second, we consider a less severe restriction on A: instead of parameterizing by the number of agents, we parameterize only by the number of agent types, which are maximal sets of agents with identical preferences. Agent types have been considered as a middle-ground between unrestricted agents and a bounded number of agents in various contexts [Eiben et al., 2020; Nguyen and Rothe, 2020], and also in the original work that introduced ϕ-CFD [Bouveret et al., 2017]. As our second algorithmic contribution, we show that ϕ-CFD is XP-tractable when parameterized by the number of agent types plus the treewidth of G (Theorem 6). We justify the use of treewidth instead of clique-width when parameterizing by the number of agent types by providing a corresponding lower bound (Theorem 9). Furthermore, Theorem 6 directly generalizes the results of Bouveret et al. (2017), who gave XP-algorithms for proportional and envy-free CFD on paths parameterized by the number of agent types.

1 A problem is XP-tractable when parameterized by k if it can be solved in polynomial time for every fixed, constant value of k.

Both Theorem 4 and Theorem 6 are obtained by dynamic programming along the respective decompositions, an approach that is often used for these structural parameters. While handling proportional and envy-free allocations in this way is not too difficult, dealing with connectivity in the definitions of EF1 and EFX requires a more careful treatment. In particular, our algorithms for these two variants require ideas that are not needed for, e.g., solving maximin CFD parameterized by treewidth [Greco and Scarcello, 2020].

While both of these algorithmic results are "tight" in the sense that it is not reasonable to hope for a relaxation of the requirements on A and or G, the notion of tractability used here-XP-tractability-is weaker than the one which is typically hoped for in the parameterized setting, notably fixedparameter tractability. As our next result (Theorem 7), we not only rule out the fixed-parameter tractability of the problem in both considered settings, but even for much more restricted cases: in particular, even when parameterizing by the number of agents plus the vertex cover number of G. This essentially rules out the fixed-parameter tractability of the problem under any even remotely reasonable restriction on A and G, for unary valuation functions U; surprisingly, the problem exhibits the same complexity-theoretic behavior under extreme restrictions (|A| plus vertex cover number) as when using parameterizations that are very relaxed (|A| plus clique-width, or the number of agent types plus treewidth).

But is it really impossible to obtain non-degenerate fixedparameter algorithms for ϕ-CFD? The final part of our paper focuses on this question and provides a more positive outlook on the problem's complexity. First of all, one may observe that Theorem 4 provides fixed-parameter algorithms for envyfree and proportional CFD in the case where |A| is bounded by a fixed constant. But what happens if-instead of imposing extreme restrictions on the number of agents-we also parameterize by the maximum valuation in U? In Theorem 8 we establish the fixed-parameter tractability of ϕ-CFD parameterized by the maximum valuation in U, the number of agent types, and the vertex cover number of G. As our last contribution, Theorem 9, we show that this final algorithmic result cannot be strengthened to more general graph parameters such as treewidth (or even deletion distance to stars).

Overall, our results provide a comprehensive understanding of the precise boundaries of tractability of ϕ-CFD, introduce three novel algorithms for the problem, and show that the problem exhibits a rather diverse complexity-theoretic behavior. An overview is provided in Figure 1.

2 Preliminaries

For an integer i, we let [i] = {1, 2, . . . , i}. We refer to the handbook by Diestel [2012] for standard graph terminology. We also refer to the standard books for a basic overview of parameterized complexity theory [Cygan et al., 2015], and assume that readers are aware of the complexity classes FPT, XP and W[1]. Readers interested in the full details of Theorem 6 are also expected to have a basic understanding of treewidth and nice tree-decompositions [Cygan et al., 2015].

Clique-width. Let k be a positive integer. A k-graph is a graph whose vertices are labeled by [k]. We denote by γ(v) the label of the vertex v. We call the k-graph consisting of exactly one vertex v (say, labeled by α) an initial k-graph and denote it by α(v). The clique-width of a graph G is the smallest integer k such that G can be constructed from initial k-graphs by means of repeated application of the following three operations.

1. Disjoint union (denoted ⊕).
2. Relabeling: changing all labels α to β (denoted pα→β).
3. Edge insertion: adding an edge between each vertex labeled α and each vertex labeled β (α ̸= β; denoted ηα,β).

A k-expression tree [Courcelle et al., 2000] is a rooted tree representation of how the three operations are used to construct a given graph; specifically, the k-expression tree represents each α(v) as a leaf, each ⊕ operator as an ⊕ node with two children, and each pα→β or ηβ,α operator by a corresponding node with a single child. It is known that an approximately optimal k-expression tree can be computed in fixedparameter time [Oum and Seymour, 2006], and that every graph class of bounded treewidth has bounded clique-width.

3 The Connected Fair Division Problem

An instance of the CONNECTED FAIR DIVISION problem (CFD) [Bil`o et al., 2019; Bouveret et al., 2017] consists of an undirected graph G = (V,E), a set A of n agents, and a valuation function ui : V → N for every agent i ∈ A. In this setting, every vertex v ∈ V corresponds to an item. We follow the standard assumption in the literature, and we assume that the agents have additive valuations; hence for every X ⊆ V and every i ∈ A we have ui(X) = ∑v∈X ui(v). Agents i and j have the same type if for every v ∈ V it holds ui(v) = uj(v). We denote the set of all agent types by A. The type of an agent i is then the agent type a ∈ A such that i ∈ a. Hence for an agent type a ∈ A we denote by ua the valuation function such that ua = ui for all i ∈ a.

An allocation of items is a tuple π = (πi)i∈A such that (1) for all i ∈ A the set πi ⊆ V and the subgraph G[πi] of G induced by πi is connected, (2) ⋃i∈A πi = V , and (3) for all i, j ∈ A such that i ̸= j we have πi ∩ πj = ∅. We also define a partial allocation for a subset A′ of A as a tuple π = (πi)i∈A′ satisfying (3). We say that the bundle πi is assigned to agent i. We will focus on fair allocations, under several different fairness notions [Bouveret et al., 2017; Bil`o et al., 2019]. Given a bundle πi, let τi = {v ∈ πi | G[πi \ {v}] is connected }. An allocation π1, π2, . . . , πn is:

• proportional (PROP) if ui(πi) ≥ ui(V ) n , for every i ∈ A;
• envy-free (EF) if ui(πi) ≥ ui(πj), for every i, j ∈ A;
• envy-free up to one item (EF1) if ui(πi) ≥ ui(πj) - maxv∈τj ui(v), for every i, j ∈ A;
• envy-free up to any item (EFX) if ui(πi) ≥ ui(πj) - minv∈τj ui(v), for every i, j ∈ A;

For a fairness criterion ϕ ∈ F = {PROP, EF, EF1, EFX}, ϕ-CFD asks whether there exists an allocation satisfying ϕ. We remark that here we consider the decision version of the problem for formal reasons only; each of our algorithms can also output a suitable allocation if one exists.

As our first course of action, we show that even extremely restricted instances of ϕ-CFD remain intractable if the valuation functions ui are encoded in binary.

Proposition 1. For all ϕ ∈ F, ϕ-CFD is NP-hard when valuation functions are encoded in binary even when restricted to instances having treewidth at most 2 and where |A| = 2, and u1 = u2.

In view of Proposition 1, from now on we assume every valuation to be encoded in unary (which also implies that all numbers are upper-bounded by the size of the instance).

4 The Futility of Singular Restrictions

Since our aim is to determine when exactly ϕ-CFD can be solved efficiently, the most natural thing to do is consider whether the problem becomes tractable if either the graph or the set of agents is restricted. In this section, we show that such a single-dimensional approach does not lead to tractability even on highly restricted classes of instances. Note that NP-hardness of EF-CFD on stars was already shown in [Bouveret et al., 2017] using a similar idea, albeit without the restriction on the valuations.

Theorem 2. For all ϕ ∈ F \ {PROP}, ϕ-CFD is NP-hard even when restricted to instances in which G is a star, with binary valuations.

Proof Sketch. For each of the three fairness notions, we give a reduction from INDEPENDENT SET on 4-regular graphs. Let (H, k) be a 4-regular instance of INDEPENDENT SET, where H has n vertices and accordingly m = 2n edges, the vertices of H are indexed as {v1, . . . , vn}, and the edges of H are indexed as {e1, . . . , em}. We construct an instance of CFD

as follows. Define G to be a star with m + k leaves. We denote the center of the star as c, and call the first n leaves of the star vertex leaves, X = {x1, . . . , xn}, and the remaining leaves of the star dummy leaves, D = {d1, . . . , dm-n+k}. Let A = [m+ 1]. To complete the reduction, it suffices to define the valuation functions; in this exposition we present only the function for ϕ = EF. Let um+1(y) = 1 if y = c and 0 otherwise, and for each other i ∈ [m] let ui(y) = 1 if y ∈ D ∪ {vj | vj ∈ ei} and 0 otherwise.

Finally, we provide some intuition to help verify the reduction. Consider an independent set W of size k in H. For an arbitrary rooted spanning tree of H, denote for each v ∈ V (H) the unique edge e ∈ E(H) which corresponds to an arc toward v in the rooted spanning tree by ev. Let {f1, . . . , fm-n+1+k} be an enumeration of all edges in E(H) \ {ev | v ∈ W}. This gives rise to a connected resource allocation π1, . . . , πm+1 for the constructed instance by letting πm+1 = {c} ∪ {xi | vi ∈ W}, and for i ∈ [m]

Our second hardness result is considerably easier, and is obtained by a reduction from a problem called EQUITABLE CONNECTED PARTITION (ECP) [Enciso et al., 2009].

Proposition 3. For every ϕ ∈ F, ϕ-CFD is NP-hard when restricted to instances where |A| = 2, and u1 = u2 = 1.

5 Solving Instances with FewAgents

While Proposition 3 rules out the existence of efficient algorithms for all instances with bounded n, here we show that the situation changes as long as we parameterize by n plus the clique-width of G, denoted cw(G).

Theorem 4. For every ϕ ∈ F, ϕ-CFD is in XP parameterized by the clique-width and the number of agents.

Proof Sketch. It is known that an approximate k-expression tree with at most k2 |V (G)| nodes can be computed in fixedparameter time [Kant´e and Rao, 2013; Oum and Seymour, 2006], so it suffices to decide ϕ-CFD when such a kexpression tree T with k = f(cw(G)) for G is provided.

Let I = (G,A, (ui)i∈A) be an instance of ϕ-CFD for ϕ ∈ F. Let t be a node of T, and recall that t is one of the following four types of nodes: α(v), ⊕, ηα,β or pα→β. Let Tt be the subtree of T rooted at t, and let Gt be the kgraph, which is a subgraph of G, defined by the k-expression tree Tt. For instance, if r is the root of T then Gr = G, and for each leaf t in T it holds that Gt is a graph with a single labeled vertex.

The high-level idea of the algorithm is to compute a set of records for every node t ∈ V (T) and to compute these records in a leaf-to-root fashion. Each record will represent one way an allocation of G can intersect with the vertices of Gt, and the information contained in the records at the root of T is sufficient to determine which of the allocations are connected and satisfy the considered fairness notion.

Formally for each node t of T we define a record ((ρi )i∈A, (µi )i∈A, (ν i )i∈A) consisting for each i ∈ A of the following components.

1. ρi ∈ 22[k] × {0, 1}, such that for each partial allocation ˜π corresponding to ((ρi )i∈A, (µi )i∈A, (ν i )i∈A) the set ρi [0] contains L ⊆ [k] if and only if Gt[˜πi] contains a connected component labeled precisely by labels in L. Formally, ρi [0] = {⋃w∈C {λ(w)} | C is a connected component of ˜πi}. The number ρi [1] = 1 if and only if ˜πi is connected.

(2) µi ∈ Zn is a vector of n integers, in which µij describes the additive valuation under uj of all items assigned to i by any partial allocation corresponding to ((ρi )i∈A, (µi )i∈A, (ν i )i∈A).

(3) ν i is only included when ϕ ∈ {EF1, EFX}. It then for each agent j ̸= i describes the valuation under uj of an item v which would be omitted from the bundle of agent i in order to determine whether j envies i in any partial allocation ˜π corresponding to ((ρi )i∈A, (µi )i∈A, (ν i )i∈A). This is necessary to ensure that connectedness is maintained when removing v from the bundle of i in the root of T. For this purpose ν i : A× 22[k] × {0, 1} → Z is a partial function for which ν i (j, K, x) describes the valuation under uj of an item v ∈ ˜πi that j would remove from ˜πi such that K = {⋃w∈C {λ(w)} | C is a connected component of ˜πi \{v}} and ˜πi \{v} is connected if and only if x = 1, where ˜π is any partial allocation ˜π corresponding to ((ρi )i∈A, (µi )i∈A, (ν i )i∈A). For a technical reason, if ˜πi = {v}, then ν i (j, {∅}, 1) = uj(v).

Note that the number of records at each node is easily bounded by 2(2k+1)n · |I|n(1+n22k +1 ) for ϕ ∈ {EF1, EFX} and even 2(2k+1)n · |I|n for ϕ ∈ {PROP, EF}, which is XP parameterized by cw(G) and n. To unify the dealing with EF1 and EFX, we let obj = min if ϕ = EFX and obj = max if ϕ = EF1. We say a record ((ρi )i∈A, (µi )i∈A, (ν i )i∈A) is valid whenever there is an allocation π of V (Gt) to A such that for every i ∈ A, all of the following hold.

• (R1) ρi [0] = {⋃w∈C {λ(w)} | C is a connected component of πi} and ρi [1] = 1 if and only if πi is connected.
• (R2) For all j ∈ [n], µij = ∑v∈πi uj(v).
• (R3) For all j ∈ A and all K ⊆ 2[k] , it holds that ν i (j, K, 0) = obj({uj(v) | v ∈ πi ∧ K = {⋃w∈C {λ(w)} | C ̸= πi \ {v} is a connected component of πi \ {v}}}). Furthermore, for all j ∈ A and all Λ ⊆ 2[k] , it holds that ν i (j, {Λ}, 1) = obj({uj(v) | v ∈ πi ∧ (πi \ {v} is a connected) ∧ Λ = ⋃w∈πi\{v} {λ(w)}}) and ν i (j, K, 1) = undefined otherwise.

For a node t ∈ V (T) we denote by R(t) the set of all valid records for t. With this setup there is a ϕ-CFD for (G = (V,G),A, (ui)i∈A) if and only if at the root r of T, R(r) contains a valid record ((ρi )i∈A, (µi )i∈A, (ν i )i∈A) such that all of the following hold.

• (R*1) For all i ∈ A and for all j ∈ A: (a) µii ≥ ∑v∈V ui(v) n if we are considering the fairness notion ϕ = PROP; (b) µii ≥ µji if we are considering the fairness notion ϕ = EF; (c) µii ≥ µji -obj({ν j (i, {Λ}, 1) | Λ ⊆ 2[k] }) if we are considering a fairness notion ϕ ∈ {EF1,EFX}. This condition ensures that the allocation satisfies the desired fairness notion.

(R*2) For all i ∈ A, ρi = ({Λ}, 1) for some Λ ∈ 2[k] . This condition ensures that the allocation is connected.

Both of these conditions can be checked in O∗ (2k )-time for each record. Thus, to complete the proof it suffices to show how to compute the set of valid records R(t) at each node t of T , given the sets of valid records of the children of t in T .

This can be done by giving a construction for each case of t.

Using this we can compute the set of all valid records R(t) for every node t of T using a leaves-to-root dynamic program, achieving a final runtime of |I|O(n22k ) for EF1 and EFX and of 2O(2k n) · |I|O(n) for envy-free and proportional CFD.

Corollary 5. If |A| is bounded by a constant, envy-free and proportional CFD is FPT parameterized by clique-width.

6 Instances with FewAgent Types

Given the state of the art, the obvious question that arises from Theorem 4 is whether we can relax the parameterization by n to a less restrictive parameterization, notably to the number of agent types. We show later in Theorem 9 that this is not possible, i.e., for each ϕ ∈ F, ϕ-CFD is NP-hard even for one agent type and clique-width three.

On the other hand, as the main result for this section, we show that offsetting the "less restrictive" agent type parameter by a "more restrictive" graph parameter-notably treewidth-gives rise to an XP-algorithm for the problem.

Theorem 6. For each ϕ ∈ F, ϕ-CFD is in XP when parameterized by the treewidth and the number of agent types.

Proof Sketch. We show the theorem using a bottom-up dynamic programming algorithm along a tree decomposition (T, χ) of the graph G. As usual the main challenge lies in the definition of the records that we keep for each node t of T , where each record models an equivalence class of partial solutions for the sub-instance induced by the items in Gt, i.e., the graph G induced by all items contained in bags in the subtree rooted at t. To illustrate the main ideas behind the definition of our records, consider a solution, i.e., an allocation π = (πi)i∈A for the whole instance I = (G,A, (ui)i∈A) of ϕ-CFD for ϕ ∈ F. Then, our records need to keep information about all bundles that contain at least some items from Gt. There are two main types of those bundles: (1) bundles that do not contain any items from the current bag χ(t), and (2) bundles that do contain some item from χ(t). Note that the former bundles must be completely contained in Gt (because the tree decomposition does not allow any edges from Gt-χ(t) to G-Gt), while the latter bundles can still contain items from G-Gt and therefore do not even need to be connected inside Gt. Now, let At be the set of all agents being assigned a bundle of type (2), let AFt be the set of all agents being assigned a bundle of type (1), and let AIt be the set of all other agents, i.e., all agents whose bundles do not intersect with Gt. For the agents in AFt , remember the following.

• The number of agents in AFt of type a for every a ∈ A. This is important to ensure that we do not falsely assume more agents of a certain type than are present in the instance.
• We need to ensure that no agent in AFt envies an agent in At ∪ AIt , i.e., any agent that will be assigned items at a later stage of the algorithm. For this it suffices to remember the minimum value w.r.t. ua of any bundle assigned to an agent in AFt of type a for every a ∈ A. Note that this is only necessary if ϕ ∈ {EF, EF1, EFX} and can be skipped if ϕ = PROP.
• We need to ensure that no agent in At ∪ AIt envies an agent in AFt . Depending on ϕ ∈ {EF, EF1, EFX}, it will be sufficient to remember the following for every agent type a ∈ A: (1) the maximum value w.r.t. ua of any bundle assigned to an agent in AFt (if ϕ = EF), and (2) the maximum value w.r.t. ua of any bundle assigned to an agent in i ∈ AFt after removing an item in π′i of maximum/minimum value w.r.t. ua (if ϕ is EF1/EFX).

While the above information for the agents in AFt is still fairly straightforward, the real challenge arises for the agents in At, since we additionally have to take into account the connectivity of their bundles and in the case of EF1 and EFX even the connectivity of their bundles after removing an item. Consider an agent i ∈ At. Then, Gt[πi] is not necessarily connected (it might only become connected because of the items in πi \ Gt), which means that we have to remember not only which items of πi are in χ(t) but also the partition of those items into components of Gt[πi]. In the case of ϕ /∈ {EF1, EFX}, this together with the value of the partial bundle πi ∩ Gt w.r.t. ua for every agent type a ∈ A would actually be sufficient information. However, if ϕ ∈ {EF1, EFX} this does not suffice since in order to ensure that no agent in AFt ∪ AIt will envy i, we also need to know the minimum/maximum value of any item that could potentially be removed from the bundle πi. Since whether or not an item in πi ∩ Gt can be removed can really only be determined once we know the whole bundle πi, we need to store the minimum/maximum value of any item whose removal results in a certain refinement of the current partition of πi∩χ(t) into components of Gt[πi]. In other words, for every "refinement" of the current partition of πi ∩χ(t) into components of Gt[πi], we store the minimum/maximum value of any item r whose removal results in this refinement (defined by Gt[πi \ {r}]).

7 Towards Fixed-Parameter Tractability

From the perspective of parameterized complexity, the most obvious question that arises from Theorem 4 and 6 is whether one can obtain fixed-parameter algorithms under these parameterizations. We firmly answer this question by providing an involved reduction that establishes the W[1]-hardness of ϕ-CFD even under significantly stronger restrictions than those required by either of the two algorithms.

Theorem 7. For each ϕ ∈ F, ϕ-CFD is W[1]-hard parameterized by the vertex cover number and the number of agents, even when all agents have identical valuations.

Proof Sketch. We provide reductions from the W[1]-hard UNARY BIN PACKING problem [Jansen et al., 2013]: given a set of items with unary values and a set of k bins, determine if it is possible to allocate items to bins so that each bin receives the same total value, which we call B. On a high-level, the reduction constructs an instance of ϕ-CFD consisting of k (or, for technical reasons that arise in the case of EF1, 2k) agents and a complete bipartite graph with k bin-vertices on one side each representing one bin, and item-vertices on the other side each representing one item. We then attach one (or, in the case of EF1, two) leaves to the bin-vertices and set the valuations in a way which ensures that every fair allocation in the constructed CFD instance will force k agents to each receive one bin-vertex along with items whose values sum up precisely to B. This yields a correspondence between solutions to the ϕ-CFD instance and solutions to the original UNARY BIN PACKING instance, completing the reduction.

But given Theorem 7, is it really impossible to obtain fixedparameter algorithms for ϕ-CFD? Corollary 5 noted that if the number of agents is bounded by a constant, proportional as well as envy-free CFD becomes fixed-parameter tractable parameterized by clique-width alone. However, if we do not wish to restrict the agents or their types in this manner, the problem can be shown to be fixed-parameter tractable if we additionally restrict the number of valuations of a vertex, i.e., val = |{ui(v)|i ∈ [n], v ∈ V }|.

Theorem 8. For each ϕ ∈ F, ϕ-CFD is fixed-parameter tractable when parameterized by the vertex cover number, the number of agent types, and val.

Proof Sketch. Let (G = (V,E), A, (ui)i∈A) be an instance of ϕ-CFD. We compute a minimum size vertex cover S of G in time O(2vcn(G) · |V |) [Cygan et al., 2015].

Since NG(v) ⊆ S for each v ∈ V (G)\S, there are at most 2|S|val equivalent items where for v, w ∈ V (G) \ S, v ∼ w if and only if NG(v) = NG(w) and for all a ∈ A every agent a ∈ a values v and w equally. An equivalence class under this relation is completely determined by its neighborhood in G and its valuations for each agent type. Now, the algorithm proceeds in two steps. In the first step we branch on a possible structure of the sought solution, as will be described below.

For each leaf of the branching tree, we then construct an instance of ILP with a number of variables bounded in our parameters. Such an instance of ILP can then be solved in FPT time parameterized by the number of variables by Lenstra's well-known algorithm [Lenstra Jr., 1983].

In the branching step we first branch on which vertices of S are allocated to which agent (up to identical agent types), and denote the set of agents that receive at least one item of S as AS. Moreover, for each S′ ⊆ S and each possible valuation q for agent types in val|A| , we branch on whether an agent in A \ AS is allocated an item in the equivalence class determined by S′ and q. For each a ∈ AS we branch on whether a receives zero, one, or more items in the equivalence class determined by S′ and q. For each agent type we also branch on whether any agent of that type receives no items.

At this point, it is not difficult to ensure that each pursued branch remains connected. To complete the allocation, we use the aforementioned ILP formulation to ensure (1) the exact number of items of each equivalence class assigned to each agent a ∈ AS, when a is branched to receive at least two such items and (2) the exact number of agents in A \ AS

of each agent type that receive an item in a specific equivalence class, if it is branched that there is at least one agent of the agent type receiving an item in that equivalence class.

As our last result, we show that even using val as an additional parameter does not allow us to lift fixed-parameter tractability to structural parameters such as treewidth.

Theorem 9. For each ϕ ∈ F, ϕ-CFD is W[1]-hard when parameterized by the deletion distance to stars and the number of agents even when val = 1. Moreover, ϕ-CFD is NP -hard even when val = 1 and the clique-width is at most 3.

Proof Sketch. We prove our result via a reduction from UNARY BIN PACKING (UBP). Let (I, (si)i∈I, k,B) be an instance of UNARY BIN PACKING such that ∑i∈I si = k ·B. We construct an instance (G = (V,E),A, (ui)i∈A) of CFD such that for all i ∈ A and all v ∈ V it holds ui(v) = 1 and let u = ui for all i ∈ A. We let |A| = k. For each bin j ∈ [k], we create a bin vertex bj. For each item i ∈ I, we create si many vertices: one "center" vertex ci and si - 1 many "pendant" vertices p1i , p2i , . . . , psi-1 i and we denote Si = {ci, p1i , . . . , psi-1 i }. The center vertex ci is adjacent to all pendant vertices p1i , . . . , psi-1 i and all bin vertices b1, . . . , bk. Note that each connected component of G-{bj | j ∈ [k]} is a star of size si for some i ∈ I.

Given a solution (I1, I2, . . . , Ik) for UBP, we let πi = {bi} ∪ ⋃j∈Ii Sj it is easy to see that u(πi) = 1 +B and the allocation is fair. On the other hand, given a fair allocation π, we can observe that, since |V | = k · (B + 1), π has to be also PROP. To finish the proof, we show that every agent has to get exactly one bin vertex and if an agent gets the center vertex ci, then she gets all vertices in the star Si.

8 Concluding Remarks

Interestingly, it turns out that the complexity-theoretic behavior of CFD seems to exhibit very little variation between the different considered notions of fairness. It is also surprising that while fairly unrestrictive parameterizations suffice to guarantee XP-tractability (as showcased by Theorems 4 and 6), disproportionately stronger restrictions are required to achieve fixed-parameter tractability (see Theorems 7 and 8). We remark that all of our algorithms can also be straightforwardly extended to handle chores (i.e., negative evaluations).

While our results provide a detailed understanding of the complexity of CFD for several of the most prominent notions of fairness studied in the literature, there remain open questions that deserve further attention. One such question is that it is currently not known whether EF1 allocations always exist on path graphs [Bil`o et al., 2019].

Acknowledgments

Ganian and Hamm gracefully acknowledge support from the Austrian Science Fund (FWF, Projects P31336 and Y1329). Hamm also acknowledges support from FWF (Project W1255-N23). Ordyniak acknowledges the support by the EPSRC (EP/V00252X/1).