lemmaapx[lemma]Lemma

# Fair Division of a Graph into Compact Bundles

Jayakrishnan Madathil
University of Glasgow, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

We study the computational complexity of fair division of indivisible items in
an enriched model: there is an underlying graph on the set of items. And we
have to allocate the items (i.e., the vertices of the graph) to a set of
agents in such a way that (a) the allocation is fair (for appropriate notions
of fairness) and (b) each agent receives a bundle of items (i.e., a subset of
vertices) that induces a subgraph with a specific “nice structure.” This model
has previously been studied in the literature with the nice structure being a
connected subgraph. In this paper, we propose an alternative for connectivity
in fair division. We introduce what we call compact graphs, and look for fair
allocations in which each agent receives a compact bundle of items. Through
compactness, we try to capture the idea that every agent must receive a set of
“closely related” items. We prove a host of hardness and tractability results
for restricted input settings with respect to fairness concepts such as
proportionality, envy-freeness and maximin share guarantee.

Keywords: Fair division, Compact bundles, $(\alpha,\beta)$-Compact graphs,
Connectivity, Diameter, Proportionality, Envy-freeness, Maximin share
guarantee

‘

##  1 Introduction

We study a fair allocation problem: $m$ items are to be allocated among $n$
agents. The items are indivisible, the agents have preferences over the items,
and the allocation must be fair (for appropriate notions of fairness). A
typical fair allocation problem thus far. But wait, there’s more. The items to
be allocated are the vertices of a graph, and we have to allocate the items in
such a way that the allocation is fair _and_ each agent receives a bundle of
items (i.e., a subset of vertices) that induces a subgraph with a specific
“nice structure.” The fairness notions that we study are proportionality,
envy-freeness and maximin share guarantee; and the nice structure that we
study requires that each agent must receive a bundle of “closely related”
items.

While fair division of indivisible items has been studied extensively from
both economics and computational perspectives (Moulin, 2003; Aziz et al.,
2022; Amanatidis et al., 2022), fair division of graphs is a relatively recent
line of study, starting with the work of Bouveret et al. (2017). The classic
fair division literature assumes no relationship between the items; the items
are independent of each other. But there are any number of scenarios where the
items to be allocated, rather than being an assortment of isolated units, are
related to one another. And we can often model such relationships between the
items using a graph. The items, for example, may be rooms in a large building,
and the graph models adjacency between pairs of rooms; or the items may be a
valuable collection of vintage postage stamps, and the graph models
similarities between pairs of stamps on the basis of country, design or
typography; or the items may be the topics for a course (to be divided between
two professors who are planning to co-teach the course), and the graph models
connections between the topics. Fair division of graphs attempts to capture
precisely such settings.

While fair division of graphs has received considerable attention in recent
years (Deligkas et al., 2021; Bilò et al., 2022; Greco and Scarcello, 2020;
Igarashi and Peters, 2019; Bei et al., 2022), to the best of our knowledge,
all work so far has focused solely on _connected_ fair division. That is, each
agent should receive a set of vertices that induces a connected subgraph.
Bouveret et al. (2017), who introduced this model of fair division of graphs,
considered the example of office spaces in a university being allocated to
various research groups, where each research group should receive a contiguous
set of offices. This scenario can easily be modelled as a fair-division-of-a
graph problem where each agent must get a connected subgraph—agents represent
various research groups, and the vertices and the edges of the graph
respectively represent the offices and adjacency between pairs of offices.
Notice that while contiguity might be useful, the “closeness” of the offices
allocated to each group might be just as important. Simply demanding
contiguity might leave a research group with a set of offices along a long and
narrow corridor, which may not be an attractive proposition to the members of
the group. In the absence of other constraints, the connectivity requirement,
while desirable, might produce bundles with unwieldy topologies. In some
cases, demanding connected bundles for every agent may be too stringent a
requirement. For example, imagine a scenario with just one agent and two items
that are isolated from each other, where the agent has a utility of $1/2$ for
each of the two items and a total utility of $1$ for the two items together.
As we can see, demanding connectivity results in only one item being allocated
to the agent, costing her half her total utility for the set of items.

We can also think of the connectivity requirement in the fair division of
graphs as a direct adaptation of the contiguity requirement in the fair
division of divisible items, i.e., the cake cutting problem where each agent
should receive a contiguous piece of the cake (Stromquist, 1980; Goldberg et
al., 2020). But contiguity is a singularly important consideration in the cake
cutting setting, for otherwise an agent “who hopes only for a modest interval
of cake may be presented instead with a countable union of crumbs”
(Stromquist, 1980). That is not the case with graphs. Moreover, graphs are a
rich combinatorial structure capable of modelling a variety of relationships
among the items, and connectivity of the items allocated to each agent may not
always be the most important consideration. There is, however, a void when it
comes to our understanding of fair division of graphs under constraints other
than connectivity. In this paper, we take a first step towards filling this
void.

###  1.1 Our Contribution

We make three contributions. (1) Propose meaningful alternatives for
connectivity in the fair division of graphs. (2) Study the computational
complexity of finding fair allocations under such alternative constraints,
even on restricted inputs. The restrictions on the input are based on the
nature of the valuation functions and the structure of the graph on the set of
items. (3) Identify and exploit results and techniques from structural and
algorithmic graph theory to design efficient algorithms for fair division of
graphs. To that end, we propose an alternative for connectivity: We demand
that each agent must receive a _compact_ bundle of items. Through compactness,
we try to capture the idea that each agent must receive a set of closely
related items.

To formally define compact graphs, we introduce the following notation. For
$n\in\mathbb{N}$, $[n]$ denotes the set $\left\\{{1,2,\ldots,n}\right\\}$ and
$[n]_{0}=[n]\cup\left\\{{0}\right\\}$. For a graph $G$, $V(G)$ and $E(G)$
respectively denote the set of vertices and edges of $G$. For a path $P$ in
$G$, the length of $P$ is the number of edges in $P$. For vertices
$z,z^{\prime}\in V(G)$, the distance between $z$ and $z^{\prime}$, denoted by
$\text{dist}_{G}(z,z^{\prime})$ is the length of a shortest path between $z$
and $z^{\prime}$. The diameter of $G$, denoted by $\text{diam}(G)$, is the
maximum distance between a pair of vertices, i.e.,
$\text{diam}(G)=\max_{z,z^{\prime}\in V(G)}\text{dist}_{G}(z,z^{\prime})$. For
$z\in V(G)$ and a non-negative integer $\beta$,
$B_{G}(z,\beta)=\left\\{{z^{\prime}\in
V(G)~{}|~{}\text{dist}_{G}(z,z^{\prime})\leq\beta}\right\\}$; we call
$B_{G}(z,\beta)$ the ball of radius $\beta$ centred at $z$.

##### Compact graphs: Definitions.

For non-negative integers $\alpha$ and $\beta$, we say that a graph $G$ is
_$(\alpha,\beta)$ -compact_ if there exist vertices
$z_{1},z_{2},\ldots,z_{\alpha}\in V(G)$ such that for every $z\in V(G)$,
$\text{dist}(z,z_{i})\leq\beta$ for some $i\in[\alpha]$, i.e.,
$V(G)=\bigcup_{i=1}^{\alpha}B_{G}(z_{i},\beta)$.111In graph theory literature,
a set of vertices $\left\\{{z_{1},z_{2},\ldots,z_{\alpha}}\right\\}\subseteq
V(G)$ such that $V(G)=\bigcup_{i=1}^{\alpha}B_{G}(z_{i},\beta)$ is often
called a distance-$\beta$ dominating set (Haynes et al., 2020). So
$(\alpha,\beta)$-compact graphs are precisely those graphs that have a
distance-$\beta$ dominating set of size at most $\alpha$. Intuitively, $G$ is
$(\alpha,\beta)$-compact if $G$ can be “covered by $\alpha$ many balls, each
of _radius_ at most $\beta$.” We also define a related class of graphs called
strongly $(\alpha,\beta)$-compact graphs. We say that a graph $G$ is _strongly
$(\alpha,\beta)$-compact_ if there exist vertex subsets
$V_{1},V_{2},\ldots,V_{\alpha}\subseteq V(G)$ such that
$V(G)=\bigcup_{i=1}^{\alpha}V_{i}$ and for every $i\in[\alpha]$ and for every
$z,z^{\prime}\in V_{i}$, $\text{dist}_{G}(z,z^{\prime})\leq\beta$. In this
paper, we focus primarily on $(\alpha,\beta)$-compact graphs. (We consider the
empty graph—the graph $G$ with $V(G)=E(G)=\emptyset$—to be both
$(\alpha,\beta)$-compact and strongly $(\alpha,\beta)$-compact for every
$\alpha,\beta\geq 0$.)

##### Compact graphs: Examples.

Observe that if a graph $G$ is strongly $(\alpha,\beta)$-compact, then it also
$(\alpha,\beta)$-compact. But the converse need not hold. For example, a star
is $(1,1)$-compact, but not strongly $(1,1)$-compact. On the other hand, if
$G$ is $(\alpha,\beta)$ compact, then it is strongly
$(\alpha,2\beta)$-compact. When $\beta=0$, the two definitions coincide. For
example, a graph is $G$ is (strongly) $(\alpha,0)$-compact if and only if $G$
has at most $\alpha$ many vertices. And $G$ is strongly $(1,1)$-compact if and
only if $G$ is a clique; and $G$ is strongly $(1,\beta)$-compact if and only
if $G$ has diameter at most $\beta$. In particular, an $m$-vertex graph $G$ is
connected if and only if $G$ is (strongly) $(1,m-1)$-compact. Similarly, a
graph $G$ with $\alpha$ connected components is strongly
$(\alpha,\beta)$-compact if and only every component has diameter at most
$\beta$. In particular, a cluster graph with $\alpha$ components is strongly
$(\alpha,1)$-compact; a cluster graph is a graph in which every connected
component is a clique. As these examples show, the definition of (strongly)
compact graphs is expansive enough to accommodate several natural restrictions
on the structure of $G$, including properties of graphs such as number of
vertices, connectivity, bounded diameter etc.

####  1.1.1 Our Model

We study fair division problems of the following type. A typical instance of
our problem consists of a triplet $(G,N,\mathcal{V})$, where $G$ is an
$m$-vertex graph, $N$ is a set of agents with ${|{N}|}=n$, and $\mathcal{V}$
is an $n$-tuple of functions $(v_{i})_{i\in N}$, where
${{v_{i}}:{2^{V(G)}}\rightarrow{\mathbb{Q}_{\geq 0}}}$. For $i\in N$, $v_{i}$
is called the valuation function or utility function of agent $i$. We assume
throughout that the valuation functions are additive (unless otherwise
stated). That is, for $i\in N$, $S\subseteq V(G)$, we have
$v_{i}(S)=\sum_{z\in S}v_{i}(\left\\{{z}\right\\})$ and $v_{i}(\emptyset)=0$.
When $S=\left\\{{z}\right\\}$ is a singleton set, we omit the braces and
simply write $v_{i}(z)$. We call the set of vertices of $G$ goods or items as
well. Throughout the paper, we use $m$ for the number of items and $n$ for the
number of agents. And we use $N$ or $[n]$ for the set of agents.

| $\beta=0$ |  |  |  |
---|---|---|---|---|---
| $\alpha=1$ | $\alpha=2$ |  $\alpha\geq 1$ $\beta\geq 1$ |  $\alpha\geq 3$ $\beta\geq 0$ |  $\alpha=1$ $\beta\geq 0$ |  $\alpha\geq 1$ $\beta\geq 0$
Prop | P |  |  NP-hard
---
(strong)
follows from
Ferraioli et al. (2014)
|  NP-hard
---
(weak)
follows from
Lipton et al. (2004)
|  NP-hard
---
(strong)
| (a) FPT w.r.t. $n$
---
when $G$
is a path
(b) XP w.r.t.
number of
agent types
when $G$
is a path
| (a) XP w.r.t.
---
$n+\Delta(G)$
even for
arbitrary
valuations
(b) pseudo-XP w.r.t.
$n+{\sf tw}(G)$
for integer
valuations
EF |  | P▲
---
follows from
Gan et al. (2019)
|  |  |  |  | (c) pseudo-XP w.r.t
---
$n$
when $G$
is planar, for
MMS | P |  |  |  |  | integer valuations

Table 1: A summary of results for $(\alpha,\beta)$-compact allocations for
various choices of $\alpha$ and $\beta$. The results proved in this paper are
shaded in grey. Each row corresponds to a fairness concept. The last two
columns contain our main algorithmic results; all the other columns discuss
the polynomial time solvability or (weak or strong)-NP-hardness of the
problems depending on various choices of $\alpha$ and $\beta$. For a graph
$G$, $\Delta(G)$ and ${\sf tw}(G)$ denote the maximum degree and treewidth of
$G$, respectively. The “pseudo” in the last column indicates that the runtime
of the algorithm depends on the valuation functions. The $\blacktriangle$ in
the (EF, $\alpha=1,\beta=0$) cell indicates the additional constraint that
each agent be allocated exactly one item.

##### Compact allocations.

Consider $(G,N,\mathcal{V})$. An allocation is a function that assigns
pairwise disjoint subsets of $V(G)$ to the agents. That is, an allocation is a
function ${{\pi}:{N}\rightarrow{2^{V(G)}}}$ such that
$\pi(i)\cap\pi(j)=\emptyset$ for distinct $i,j\in N$. Consider an allocation
$\pi$. We call $\pi(i)$ agent $i$’s bundle under the allocation $\pi$. We say
that $\pi(i)$ is $(\alpha,\beta)$-compact if $G[\pi(i)]$ is
$(\alpha,\beta)$-compact. And we say that an allocation $\pi$ is
_$(\alpha,\beta)$ -compact_ if $\pi(i)$ is $(\alpha,\beta)$-compact for every
$i\in N$. The definition of a strongly $(\alpha,\beta)$-compact allocation is
analogous.

##### Fairness concepts.

We consider three well-studied fairness concepts—proportionality, envy-
freeness and maximin fairness. An allocation $\pi$ is _proportional_ if
$v_{i}(\pi(i))\geq(1/n)\cdot v_{i}(V(G))$ for every $i\in N$, i.e., every
agent receives at least a $1/n$ fraction of her utility for the whole graph.
And we say that $\pi$ is _envy-free_ if $v_{i}(\pi(i))\geq v_{i}(\pi(j))$ for
every pair of distinct agents $i,j\in N$, i.e., every agent prefers her own
bundle to that of the other agents. We now define maximin fair allocations by
suitably adapting the definition introduced by Budish (2011). For
$(G,N,\mathcal{V})$, let $\Pi(G,N,\mathcal{V})$ be the set of all allocations
${{\phi}:{N}\rightarrow{2^{V(G)}}}$. Let $\Gamma\subseteq\Pi(G,N,\mathcal{V})$
be any non-empty set of allocations. For every agent $i\in N$, we define the
$\Gamma$-maximin share guarantee of $i$, denoted by $\Gamma\mathchar
45\relax\mathtt{mms}_{i}(G,N,\mathcal{V})$, as follows:

$\Gamma\mathchar
45\relax\mathtt{mms}_{i}(G,N,\mathcal{V})=\max_{\pi\in\Gamma}\min_{j\in
N}v_{i}(\pi(j)).$

Informally, $\Gamma\mathchar 45\relax\mathtt{mms}_{i}(G,N,\mathcal{V})$ is the
maximum utility agent $i$ could guarantee for herself if agent $i$ were to
allocate the items, with the caveat that the allocation be in $\Gamma$, and
allowed to choose only the least valued bundle for herself. We say that an
allocation ${{\phi}:{N}\rightarrow{2^{V(G)}}}$ is _$\Gamma$ -maximin fair_ if
$v_{i}(\pi(i))\geq\Gamma\mathchar 45\relax\mathtt{mms}_{i}(G,N,\mathcal{V})$.
We are interested in $\Gamma$-maximin fair allocations for the case when
$\Gamma$ is the set of all $(\alpha,\beta)$-compact allocations, which we
denote by $\Gamma((\alpha,\beta)\mathchar 45\relax\mathtt{com})$. For
convenience, when $(G,N,\mathcal{V})$ and $\Gamma$ are clear from the context,
we may simply write $\mathtt{mms}_{i}$ instead of $\Gamma\mathchar
45\relax\mathtt{mms}_{i}(G,N,\mathcal{V})$.

##### Economic efficiency constraints.

We say that an allocation $\pi$ is complete if $\pi$ allocates all the
vertices of $G$, i.e., $\bigcup_{i\in N}\pi(i)=V(G)$. And we say that $\pi$ is
Pareto-optimal if there exists no allocation $\pi^{\prime}$ such that
$v_{i}(\pi^{\prime}(i))>v_{i}(\pi(i))$ for some $i\in N$ and
$v_{j}(\pi^{\prime}(j))\geq v_{j}(\pi(j))$ for every $j\in
N\setminus\left\\{{i}\right\\}$.

##### Computational questions.

Let $\alpha$ and $\beta$ be fixed integers. We are interested in computational
problems that take an instance $(G,N,\mathcal{V})$ as input, and the question
is to decide if $(G,N,\mathcal{V})$ admits an allocation that is (strongly)
$(\alpha,\beta)$-compact and fair? Depending on the fairness concept, we have
the following specific problems.

  * •

Prop-$({\alpha},{\beta})$-Compact-FD: Does $(G,N,\mathcal{V})$ admit an
allocation that is proportional and $(\alpha,\beta)$-compact?

  * •

EF-$({\alpha},{\beta})$-Compact-FD: Does $(G,N,\mathcal{V})$ admit an
allocation that is envy-free and $(\alpha,\beta)$-compact? As the empty
allocation (where no item is allocated) is trivially envy-free, we often
combine envy-freeness with efficiency constraints such as completeness or
Pareto-optimality. We thus have the corresponding computational questions:
Complete-EF-$({\alpha},{\beta})$-Compact-FD and PO-
EF-$({\alpha},{\beta})$-Compact-FD, where in addition to envy-freeness and
$(\alpha,\beta)$-compactness, the allocation must respectively be complete and
Pareto-optimal.

  * •

MMS-$({\alpha},{\beta})$-Compact-FD: Does $(G,N,\mathcal{V})$ admit an
allocation that is $\Gamma((\alpha,\beta)\mathchar
45\relax\mathtt{com})$-maximin fair and $(\alpha,\beta)$-compact?

We define the strongly compact variants of the problems analogously. Notice
that $\alpha$ and $\beta$ are fixed constants and not part of the input.

####  1.1.2 Our Results

We prove a host of hardness and algorithmic results for
$[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD, where we use $[\mathtt{X}]$ as
a placeholder for one of the three fairness concepts discussed above. See
Table 1 for a quick summary. Recall that $n$ is the number of agents and $m$
is the number of vertices in the input graph. We first discuss the polynomial
time solvability versus (weak and strong) NP-hardness of the problems. These
results are further divided into cases based on the choice of $\alpha$ and
$\beta$. The hardness results hold only for problems corresponding to
proportionality and envy-freeness, and they all hold for additive valuations.
And then we move on to our algorithmic results, specifically, FPT and XP
algorithms w.r.t. a combination of parameters, including the number of agents,
maximum degree and treewidth of the graph. We now list our results one by one.
First, NP-hardness.

  1. 1.

The well-known reduction from Partition that shows the NP-hardness of checking
whether a proportional allocation or an envy-free allocation exists (in the
classic fair allocation setting) (Lipton et al., 2004) extends to our setting
as well. We need only represent the set of items as a clique. Thus
Prop-$({\alpha},{\beta})$-Compact-FD, Complete-
EF-$({\alpha},{\beta})$-Compact-FD and PO-EF-$({\alpha},{\beta})$-Compact-FD
are all NP-hard for every $\alpha,\beta\geq 1$. These results hold even when
there are only two agents with identical additive valuations. Notice, however,
that a reduction from Partition only implies weak NP-hardness. Also, this
result does not cover the case when $\beta=0$.

  2. 2.

The case of $\beta=0$ warrants special attention. In this case, every agent
can receive at most $\alpha$ items as a graph $G$ is $(\alpha,0)$-compact if
and only if $G$ has at most $\alpha$ vertices. So we can ignore the underlying
graph, and treat the problem as an instance of the classic fair division
problem with the additional constraint that every agent be allocated at most
$\alpha$ items. In this case, the complexities of the problems vary depending
on the choice of $\alpha$.

    1. (a)

If $\alpha=1$, then every agent can receive at most one item. In this case,
for all three fairness notions, the corresponding problems are polynomial time
solvable. We can reduce each problem to a matching problem in an agents-items
bipartite graph. For envy-freeness, we have the additional constraint that
every agent must receive exactly one item; and the polynomial time algorithm
is due to Gan et al. (2019).

    2. (b)

The case of $\alpha=2$: The problem corresponding to proportionality, i.e.,
Prop-$({2},{0})$-Compact-FD, is strongly NP-hard. This is implied by a result
due to Ferraioli et al. (2014). The complexity of the problems corresponding
to envy-freeness and maximin fairness, however, are still open.

    3. (c)

The case when $\alpha\geq 3$ is covered by the next result.

  3. 3.

For every $\alpha\geq 3$ and $\beta\geq 0$, we prove that the problems
corresponding to (i) proportionality, (ii) envy-freeness + completeness and
(iii) envy-freeness + Pareto-optimality are all strongly NP-hard. These
results hold even for edgeless graphs.

Now, the algorithmic results.

  1. 4.

If $\alpha=1$ and the graph $G$ is a path, then for proportionality, the
corresponding problem admits an algorithm with runtime $2^{n}\cdot
m^{\mathcal{O}(1)}$, and hence is fixed-parameter tractable (FPT) with respect
to the number of agents. We also extend this result to an algorithm with
runtime $n^{p}\cdot m^{\mathcal{O}(1)}$, where $p$ is the number of _types_ of
agents. Two agents are of the same type if their valuations are identical.
These results hold for arbitrary valuations. Our algorithms are based on a
straightforward dynamic programming procedure, which is only a slight
adaptation of the algorithm of (Bouveret et al., 2017, Theorem 3.3) for
proportional and _connected_ fair division. But the fact that $\alpha=1$ is
crucial for these algorithms to work.

  2. 5.

For all three fairness concepts and for all values of $\alpha$ and $\beta$, we
design algorithms with runtime $m^{\mathcal{O}(\alpha n)}\cdot 2^{\alpha
n\cdot\Delta^{\mathcal{O}(\beta)}}$ for the corresponding problems, where
$\Delta$ is the maximum degree of $G$. We thus have slicewise polynomial time
(XP) algorithms parameterized by $n+\Delta$. The algorithms follow from the
simple observation that for any vertex $z\in V(G)$, the number of vertices
that are at distance at most $\beta$ from $z$ is at most $\Delta^{\beta+1}$.
Therefore, we can enumerate all $(\alpha,\beta)$-compact allocations in time
$m^{\mathcal{O}(\alpha n)}\cdot 2^{\alpha n\cdot\Delta^{\mathcal{O}(\beta)}}$.

  3. 6.

For all three fairness fairness concepts, we design pseudo-XP algorithms with
respect to the parameter ${\sf tw}+n$, where ${\sf tw}$ is the treewidth of
$G$. We design a single dynamic programming algorithm that works for all three
fairness concepts. We assume here that the valuations are integer-valued. Let
$W$ be the maximum value any agent has for the whole graph, i.e.,
$W=\max_{i\in N}v_{i}(V(G))$. Our algorithms have a runtime of $({\sf
tw}+n)^{\mathcal{O}({\sf tw}+n)}\beta^{\mathcal{O}({\sf tw})}\cdot
m^{\mathcal{O}(\alpha n)}\cdot W^{\mathcal{O}(n^{2})}$. In particular, when
the valuations are polynomially bounded, we have XP algorithms. These
algorithms yield a number of interesting corollaries, which we discuss below.

    1. (a)

Welfare maximisation: We can use our dynamic programming procedure to compute
$(\alpha,\beta)$-compact allocations that maximise welfare. For example, we
can answer questions such as this: Among all the allocations that maximise the
utilitarian social welfare, is there one that is also
$(\alpha,\beta)$-compact? The utilitarian social welfare of an allocation
$\pi$ is the sum of the utilities of the agents have under $\pi$, i.e.,
$\sum_{i\in N}v_{i}(\pi(i))$.

    2. (b)

Connected fair division: As noted earlier, an $m$-vertex graphs is connected
if and only if it is $(1,m-1)$ compact. Hence our algorithms work for
connected fair division as well, with a runtime of $({\sf
tw}+n)^{\mathcal{O}({\sf tw}+n)}\cdot m^{\mathcal{O}({\sf tw}+n)}\cdot
W^{\mathcal{O}(n^{2})}$.

    3. (c)

Implications for planar graphs (and more): On planar graphs, our algorithms
run in time $n^{\mathcal{O}(n)}\cdot m^{\mathcal{O}(\alpha n)}\cdot
W^{\mathcal{O}(n^{2})}$, i.e., a pseudo-XP algorithm parameterized by $n$. To
derive this result, we leverage the well-known fact that the treewidth of a
planar graph is $\mathcal{O}(D)$, where $D$ is the diameter of the graph
(Eppstein, 2000), and the fact that the diameter of every connected component
of an $(\alpha,\beta)$-compact graph is $\mathcal{O}(\alpha\beta)$.222We note
that the classes of bounded degree graphs, bounded treewidth graphs and planar
graphs are pairwise-incomparable. That is, no class is contained in either of
the two other classes. Hence an algorithm for problems restricted to one of
these classes does not automatically imply a similar result for the other
classes. In particular, the reliance on bounding treewidth by a function of
the diameter is crucial for deriving our algorithm on planar graphs. In fact,
such a runtime is possible not just on planar graphs, but on all graphs whose
treewidth is bounded by a function of its diameter. In particular, if
$\mathcal{F}$ is a minor-closed family of graphs and $\mathcal{F}$ excludes an
apex-graph, then on any graph $G\in\mathcal{G}$, our algorithms run in time
$f(n)\cdot m^{\mathcal{O}(\alpha n)}W^{\mathcal{O}(n^{2})}$. This follows from
a deep result in structural graph theory due to Eppstein (2000), who
characterised all minor-closed graph classes that have the “diameter-treewidth
property.”333A graph $G$ is an apex graph if $G-v$ is planar for some $v\in
V(G)$. That is, apex graphs are “planar plus 1 vertex” graphs. Consider a
family of graphs $\mathcal{F}$. We say that $\mathcal{F}$ has the diameter-
treewidth property if there exists a function
${{f}:{\mathbb{R}}\rightarrow{\mathbb{R}}}$ such that ${\sf tw}(G)\leq
f(\text{diam}(G))$ for every $G\in\mathcal{F}$. Notice that the function $f$
depends only on the family $\mathcal{F}$. Eppstein (2000) proved that if
$\mathcal{F}$ is a minor closed family of graphs, then $\mathcal{F}$ has the
diameter-treewidth property if and only if $\mathcal{F}$ excludes an apex
graph. For more details, see (Eppstein, 2000) or (Demaine and Hajiaghayi,
2004).

##### Results for strongly compact variants.

All our hardness results mentioned above hold for the strongly compact
variants of the respective problems as well. So do (i) our algorithm for
proportional allocations on paths when $\alpha=1$ and (ii) the XP algorithms
parameterized by $n+\Delta$. In addition, we show that for proportionality and
for envy-freeness + completeness, the strongly compact variants of the
corresponding problems are strongly NP-hard for every $\alpha,\beta\geq 1$.
(Notice that our strong NP-hardness results for the compact variants only
cover the case of $\alpha\geq 3$.)

##### Runtime of our algorithms.

The runtimes of the algorithmic results discussed above have an exponential
dependence on $n$ (the number of agents). But this need not be a disqualifying
factor as several fair division settings only have a constant number of
agents, and often just two agents. Common examples of 2-agent settings, as
noted by Plaut and Roughgarden (2020), include divorce settlements,
inheritance division and international border disputes. In fact, 2-agent
setting is one of the most intensively studied special cases in fair division;
see, for example, (Brams and Fishburn, 2000; Brams et al., 2022). We would
also like to point out that the exponential dependence of the runtime of our
treewidth-based algorithm on both $n$ and ${\sf tw}$ is also essential; notice
that our NP-hardness results for proportional or envy-free, compact
allocations when $\alpha\geq 3$ hold for graphs of treewidth zero (even when
the valuations are additive and polynomially bounded). The runtime of our
treewdith-based algorithm depends also on $W$, the maximum valuation of an
agent for the whole graph. This may be inevitable as well. As shown by
Igarashi and Peters (2019) in the context of connected fair division, unless
$\textsf{P}=\textsf{NP}$, there is no polynomial time algorithm that finds a
Pareto-optimal allocation even when the valuations are binary and additive and
the graph is a tree with bounded pathwidth or bounded diameter. We believe
that a similar result should hold for compact allocations as well. Also, as
noted above, we can use our algorithms to find welfare-maximising allocations.
Our algorithms can thus compute allocations with three properties: fairness,
compactness and economic efficiency. We would like to emphasise that for
algorithms that find efficient allocations, “pseudo” runtimes are rather
common; see, for example Barman et al. (2018); Aziz et al. (2023).

##### Choice of parameters.

We would like to add a word about the parameterizations that we use in our
algorithmic results. As noted above, in many fair allocation problems, the
number of agents is small, and therefore, parameterizations by the number of
agents or agent types are quite reasonable. In particular, such
parameterizations have been used by Bouveret et al. (2017) and Deligkas et al.
(2021) in the context of connected fair division of graphs. Now, about the the
graph parameters that we use. It is quite common in algorithmic graph theory
to leverage structural parameters of the input graph (maximum degree,
degeneracy, treewidth etc.) to design efficient algorithms. The two graph
parameters that we use—maximum degree and treewidth—have been leveraged this
way in the parameterized algorithms literature. Maximum degree, while being a
simple and reasonable parameter, is perhaps less interesting because a number
of problems remain NP-hard on graphs of constant degree. But treewidth is a
completely different story. It is considered as a natural measure of
“sparsity” of the graph, and has been studied extensively. Treewidth is
related to a number of other graph parameters, and it is the source of several
deep theorems in graph theory. See, for example, the Festschrift edited by
Fomin et al. (2020) for the many applications of treewidth in algorithm
design. We must also add that connected fair division of graphs has previously
been studied on special graphs such as paths, stars, trees, cycles etc., which
are all graphs of treewidth 1 or 2 (Bouveret et al., 2017; Lonc and
Truszczynski, 2018). Also, parameters such as treewidth and cliquewidth have
been used as structural parameters in connected fair division (Deligkas et
al., 2021). We discuss some of these works below. So it is very much in line
with the existing literature to use treewidth as a parameter to design
algorithms. In particular, one of our goals was to apply results and
techniques from graph theory literature to problems in fair division. And for
this purpose, treewidth is arguably the most suitable choice.

###  1.2 Related Work

Modern fair division literature goes back at least to the pioneering work of
Steinhaus (1948). For an overview of the relevant literature, we refer the
reader to the surveys by Lindner and Rothe (2016) on the divisible goods
setting; and by Aziz et al. (2022) or Amanatidis et al. (2022) on the
indivisible goods setting.

There is, in particular, a large volume of literature on fair division under
connectivity constraints. As for the cake cutting setting (i.e., divisible
goods), Stromquist (1980) proved that an envy-free allocation of the cake into
connected pieces exists, but there is no finite protocol that can find such an
allocation (Stromquist, 2008). Coming to the indivisible goods setting, the
work of Bouveret et al. (2017), which formally introduced this line of study,
contains several algorithmic and hardness results for the connected fair
division of a graph. They showed that finding a connected allocation that is
envy-free or proportional is NP-hard, even when the graph is a path. On the
other hand, a maximin allocation always exists and can be computed in
polynomial time if the graph is a tree. They also designed several FPT and XP
algorithms with respect to parameters such as number of agents and number of
agent types, for special cases of the graph. This was followed by the work of
Lonc and Truszczynski (2018), who studied the existence and complexity of
maximin fair allocations on cycles. Among other results, they proved that when
there are only three agents, there exists an allocation that guarantees each
agent a constant fraction of her maximin share. Most related to our work is
that of Deligkas et al. (2021), who undertook an in-depth study of the
parameterized complexity of connected fair division. They established a host
of hardness and algorithmic results—under various combinations of parameters
such as the number of agents, treewidth, cliquewidth etc.—with respect to
fairness concepts such as proportionality, envy-freeness, EF1 and EFX. A
number of recent works deal with the special case when the graph is a path,
under various fairness notions. In particular, Bilò et al. (2022) studied the
existence and complexity of EF1 and EF2 allocations; Igarashi (2022) studied
EF1 allocations and showed that EF1 allocations always exists for any number
of agents with monotone valuations; Suksompong (2019) studied approximate
guarantees for proportionality, envy-freeness and equitability; and Misra et
al. (2021) studied the complexity of finding allocations that are equitable up
to one item (EQ1) combined with economic efficiency notions such as Pareto-
optimality, non-wastefulness etc. In addition to these works that mainly deal
with the existence or computational questions associated with connected fair
division, Bei et al. (2022) studied the price of connectivity—the loss
incurred by agents when the connectivity constraint is imposed—for maximin
fair allocations. Their techniques included the application of several graph
theoretic tools and concepts to fair division.

Much of the literature on fair division under restricted input settings focus
on restrictions on valuations, number of agents or relaxations of fairness
notions. To the best of our knowledge, there are only a handful of works that
consider restrictions on the _structure_ of bundles allocated to agents (other
than connected fair division in the context of graphs). The typical
restriction on bundles involves what can be called cardinality constraints.
The canonical example is the house allocation problem, where each agent must
receive exactly one item. Gan et al. (2019) studied envy-freeness and Kamiyama
et al. (2021) studied proportionality and equitability in the house allocation
setting. Ferraioli et al. (2014) et al. studied the problem of maximising
egalitarian welfare, under the additional constraint that each agent be
allocated exactly $k$ items. Biswas and Barman (2018) introduced a more
general variant of cardinality constraints: the items are partitioned into
groups and there is a cap on each group’s contribution to any agent’s bundle.
And they showed that a $1/3$-approximate maximin fair allocation can be
computed efficiently; Hummel and Hetland (2022) recently improved the
approximation guarantee to $1/2$. See the survey by Suksompong (2021) for a
comprehensive discussion of various constraints in fair division.

##  2 Preliminaries

We use this section only to collect all the notation and terminology we use in
one place. Some of the terms that we define here will be used only in Section
6.

##### Sets, tuples and functions.

For $n\in\mathbb{N}$, $[n]$ denotes the set $\left\\{{1,2,\ldots,n}\right\\}$,
$[n]_{0}$ denotes the set $\left\\{{0,1,2,\ldots,n}\right\\}$;
${[n]}_{\text{od}}$ and ${[n]}_{\text{ev}}$ respectively denote the set of odd
numbers in $[n]$ and the set of even numbers in $[n]$, i.e.,
${[n]}_{\text{od}}=[n]\cap\left\\{{1,3,5,\ldots}\right\\}$ and
${[n]}_{\text{ev}}=[n]\cap\left\\{{2,4,6,\ldots}\right\\}$. We use the
shorthand $(z_{i})_{i\in[n]}$ for the tuple $(z_{1},z_{2},\ldots,z_{n})$. For
sets $X,Y$, a function ${{f}:{X}\rightarrow{Y}}$ and a subset $Z\subseteq X$,
$f\big{|}_{Z}$ denotes the restriction of $f$ to $Z$. That is,
${{f\big{|}_{Z}}:{Z}\rightarrow{Y}}$ is the function from $Z$ to $Y$ such that
$f\big{|}_{Z}(z)=f(z)$ for every $z\in Z$. For sets
$X,Y,X^{\prime},Y^{\prime}$ and a function ${{f}:{X}\rightarrow{Y}}$,
$\mathtt{ext}(f,X^{\prime},Y^{\prime})$ denotes the set of all functions
${{g}:{X\cup X^{\prime}}\rightarrow{Y\cup Y^{\prime}}}$ such that $g(x)=f(x)$
for every $x\in X$. That is, for every
$g\in\mathtt{ext}(f,X^{\prime},Y^{\prime})$, $g\big{|}_{X}=f$.

##### Partition.

Consider a non-empty set $S$. A partition of $S$ is a family
$\mathcal{P}\subseteq 2^{S}$ of non-empty subsets of $S$ such that
$\bigcup_{P\in\mathcal{P}}P=S$ and $P\cap P^{\prime}=\emptyset$ for every
distinct $P,P^{\prime}\in\mathcal{P}$. For a partition $\mathcal{P}$ of $S$,
each set $P\in\mathcal{P}$ is called a block of $\mathcal{P}$. And for $z\in
S$, we denote the block of $\mathcal{P}$ that contains $z$ by
$\mathtt{block}_{\mathcal{P}}(z)$, i.e., $\mathtt{block}_{\mathcal{P}}(z)=P$
if $P\in\mathcal{P}$ and $z\in P$. When the partition $\mathcal{P}$ is clear
from the context, we omit the subscript and simply write $\mathtt{block}(z)$.
Consider $z\in S$ and let $\mathcal{P}$ be a partition of
$S\setminus\left\\{{z}\right\\}$. By $\mathtt{add}(z,\mathcal{P})$, we denote
the set of all partitions of $S$ obtained from $\mathcal{P}$ by adding $z$ to
one of the blocks of $\mathcal{P}$. That is, if
$\mathcal{P}=\left\\{{P_{1},P_{2},\ldots,P_{r}}\right\\}$ is a partition of
$S\setminus\left\\{{z}\right\\}$, then
$\mathtt{add}(z,\mathcal{P})=\left\\{{\mathcal{P}^{1},\mathcal{P}^{2},\ldots,\mathcal{P}^{r}}\right\\}$,
where for each $i\in[r]$, $\mathcal{P}^{i}$ is the partition of $S$ defined as
$\mathcal{P}^{i}=\left\\{{P^{i}_{1},P^{i}_{2},\ldots,P^{i}_{r}}\right\\}$ with
$P^{i}_{i}=P_{i}\cup\left\\{{z}\right\\}$ and $P^{i}_{j}=P_{j}$ for every
$j\in[r]\setminus\left\\{{i}\right\\}$.

##### Rooted partition.

We now define an annotated version of a partition called a rooted partition. A
rooted partition $\mathcal{P}$ is nothing but a partition, but each block $P$
of $\mathcal{P}$ has a designated element, which we call the root of $P$.
Formally, a rooted partition of $S$ is an ordered pair $(\mathcal{P},R)$ such
that $\mathcal{P}$ is a partition of $S$, $R\subseteq S$ with
${|{R}|}={|{\mathcal{P}}|}$ and for each block $P$ of $\mathcal{P}$, ${|{P\cap
R}|}=1$; we call the unique element of $P\cap R$ the root of $P$.

##### Graphs.

All graphs is this paper are undirected. For a graph $G$, $V(G)$ and $E(G)$
respectively denote the vertex set and edge set of $G$. Consider a graph $G$.
For a path $P$ in $G$, the length of $P$ is the number of edges in $P$. For
vertices $z,z^{\prime}\in V(G)$, the distance between $z$ and $z^{\prime}$ in
$G$, denoted by $\text{dist}_{G}(z,z^{\prime})$, is the length of a shortest
path between $z$ and $z^{\prime}$. If $z=z^{\prime}$, then
$\text{dist}_{G}(z,z^{\prime})=0$. For a vertex $z\in V(G)$ and a non-negative
integer $\beta$, we use $B(z,\beta)$ to denote the set of all vertices in $G$
that are at distance at most $\beta$ from $z$, i.e.,
$B_{G}(z,\beta)=\\{z^{\prime}\in
V(G)~{}|~{}\text{dist}_{G}(z,z^{\prime})\leq\beta\\}$. (We may omit the
subscript $G$ when the graph is clear from the context.) The diameter of $G$,
denoted by $\text{diam}(G)$, is the maximum distance between any pair of
vertices in $G$, i.e., $\text{diam}(G)=\max_{z,z^{\prime}\in
V(G)}\text{dist}(z,z^{\prime})$. For a graph $G$, a subgraph $H$ of $G$ is
called a spanning subgraph if $V(H)=V(G)$. An acyclic spanning subgraph is
called a spanning forest. A tree is a connected, acyclic graph. A rooted tree
$T$ is a tree in which we designate exacly one vertex $x\in V(T)$ as the
“root” of $T$; and we say that $T$ is rooted at $x$. For a tree rooted at
$x\in V(T)$, and vertices $z,z^{\prime}\in V(T)$, we say that $z$ is a
descendant of $z^{\prime}$ if $z^{\prime}$ lies on the unique path in $T$ from
$x$ to $z$. For a rooted tree $T$ and $z\in V(T)$, by the sub-tree of $T$
rooted at $z$, we mean the sub-tree of $T$ induced by $z$ and all descendants
of $z$, and we root the sub-tree at $z$. A rooted forest is a graph in which
each connected component is a rooted tree. For a rooted forest $G$, by the set
of roots of $G$, we mean the set $R\subseteq V(G)$ that consists of the root
of each connected component of $G$. That is, for each connected component of
$H$ of $G$, $R\cap V(H)=\left\\{{x_{H}}\right\\}$, where $x_{H}$ is the root
of $H$. For a connected graph $G$ and a vertex $z\in V(G)$, a BFS tree of $G$
rooted at $z$ is a spanning tree of $G$, produced by a breadth-first search
traversal of $G$, starting at $z$. If $H$ is a BFS tree of $G$ rooted at $z$,
then for every $z^{\prime}\in V(G)$, we have
$\text{dist}_{G}(z,z^{\prime})=\text{dist}_{H}(z,z^{\prime})$.

##### Merge of two graphs.

For graphs $G_{1}$ and $G_{2}$ with $V(G_{1})=V(G_{2})$, by the merge of
$G_{1}$ and $G_{2}$, denoted by $\mathtt{merge}(G_{1},G_{2})$ we mean the
(multi)graph $G$ obtained by the union of $G_{1}$ and $G_{2}$. That is,
$V(G)=V(G_{1})=V(G_{2})$ and $E(G)=E(G_{1})\cup E(G_{2})$ (treated as a
multiset). Thus, for $z,z^{\prime}\in V(G)$, $zz^{\prime}\in E(G)$ if and only
if $zz^{\prime}\in E(G_{1})$ or $zz^{\prime}\in E(G_{2})$. And if
$zz^{\prime}\in E(G_{1})$ _and_ $zz^{\prime}\in E(G_{2})$, then $G$ contains
two parallel edges between $z$ and $z^{\prime}$.

##### Partition into the connected components.

For a graph $G$ and a non-empty set $Z\subseteq V(G)$, by the _partition of
$Z$ into the connected components of $G$_, we mean the partition $\mathcal{P}$
of $Z$ such that for $z,z^{\prime}\in Z$, $z$ and $z^{\prime}$ are in the same
block of $\mathcal{P}$ if and only if they are in the same connected component
of $G$.

##### Graphical representation of a partition.

For a non-empty set $S$ and a partition $\mathcal{P}$ of $S$, a graphical
representation of $\mathcal{P}$, denoted by $\mathtt{G}(\mathcal{P})$, is an
acyclic graph with vertex set $S$ such that $\mathcal{P}$ is precisely the
partition of $S$ into the connected components of $\mathtt{G}(\mathcal{P})$.
That is, each block of $\mathcal{P}$ corresponds to a connected component of
$\mathtt{G}(\mathcal{P})$ and vice versa; and since $\mathtt{G}(\mathcal{P})$
is acyclic, each connected component is a tree. Notice that
$\mathtt{G}(\mathcal{P})$ need not be unique. So by $\mathtt{G}(\mathcal{P})$,
we only mean any fixed (arbitrarily chosen) acyclic graph that satisfies the
required property.

##### Acyclic join of partitions.

For partitions $\mathcal{P}^{\prime},\mathcal{P}^{\prime\prime}$ and
$\mathcal{P}$ of $S$, we say that $\mathcal{P}$ is an acyclic join of
$\mathcal{P}^{\prime}$ and $\mathcal{P}^{\prime\prime}$ if the merge of
$\mathtt{G}(\mathcal{P}^{\prime})$ and
$\mathtt{G}(\mathcal{P}^{\prime\prime})$ is a graphical representation of
$\mathcal{P}$. For rooted partitions
$(\mathcal{P}^{\prime},R^{\prime}),(\mathcal{P}^{\prime\prime},R^{\prime\prime})$
and $(\mathcal{P},R)$ of $S$, we say that $(\mathcal{P},R)$ is an acyclic join
of $(\mathcal{P}^{\prime},R^{\prime})$ and
$(\mathcal{P}^{\prime\prime},R^{\prime\prime})$ if $\mathcal{P}$ is an acyclic
join of $\mathcal{P}^{\prime}$ and $\mathcal{P}^{\prime\prime}$ and
$R=R^{\prime}\cap R^{\prime\prime}$. We now make the following observation
about the complexity of checking if a given partition is an acyclic join.

######  Observation 2.1.

Given a non-empty set $S$ and rooted partitions
$(\mathcal{P}^{\prime},R^{\prime}),(\mathcal{P}^{\prime\prime},R^{\prime\prime})$
and $(\mathcal{P},R)$ of $S$, we can check in time ${|{S}|}^{\mathcal{O}(1)}$
if $(\mathcal{P},R)$ is an acyclic join of $(\mathcal{P}^{\prime},R^{\prime})$
and $(\mathcal{P}^{\prime\prime},R^{\prime\prime})$. This is possible because
(i) we can construct $\mathtt{G}(\mathcal{P}^{\prime})$ and
$\mathtt{G}(\mathcal{P}^{\prime})$ in time ${|{S}|}^{\mathcal{O}(1)}$, and
(ii) we can also construct the merge of $\mathtt{G}(\mathcal{P}^{\prime})$ and
$\mathtt{G}(\mathcal{P}^{\prime})$ and verify whether it is a graphical
representation of $\mathcal{P}$ in time ${|{S}|}^{\mathcal{O}(1)}$, and (iii)
we can also verify whether $R=R^{\prime}\cap R^{\prime\prime}$ in time
${|{S}|}^{\mathcal{O}(1)}$.

##### Parameterized complexity.

We use standard terminology from parameterized complexity, for which we refer
the reader to the book by Cygan et al. (2015). A typical parameterized problem
on graphs consists of an $m$-vertex graph $G$ and a non-negative integer $k$
as input, and we have to decide if $(G,k)$ satisfies a fixed property. The
integer $k$ may be given explicitly as part of the input, or it may be a
function of the input graph $G$. We call $k$ the parameter, and say that the
problem is parameterized by $k$. We say that the problem is fixed-parameter
tractable (or belongs to the class FPT) if it admits an algorithm running in
time $f(k)m^{\mathcal{O}(1)}$, for some computable function $f$. We also call
an algorithm with such a runtime an FPT algorithm. And we say that the problem
belongs to the class XP (slicewise polynomial time) if it admits an algorithm
running in time $f(k)m^{g(k)}$ for some computable functions $f$ and $g$.

#### Tree decomposition

Consider a graph $G$. A tree decomposition of $G$ is a pair
$(T,\\{X_{t}~{}|~{}t\in V(T)\\})$, where $T$ is a tree and every node $t\in
V(T)$ has a set $X_{t}\subseteq V(G)$ associated with it, such that
$(T,\\{X_{t}~{}|~{}t\in V(T)\\})$ satisfies the following conditions. (a)
$\bigcup_{t\in V(T)}X_{t}=V(G)$. (b) For every edge $uv\in E(G)$, there exists
a node $t\in V(T)$ such that $u,v\in X_{t}$. (c) For every $u\in V(G)$, the
set $\\{t\in V(T):u\in X_{t}\\}$ induces a connected subtree of $T$. We call
each $X_{t}$ a bag. The width of a tree decomposition
$(T,\left\\{{X_{t}~{}|~{}t\in V(T)}\right\\})$ is $\max_{t}{|{X_{t}}|}-1$. The
treewidth of a graph $G$, denoted by ${\sf tw}(G)$ is the minimum width of a
tree decomposition $G$. When $G$ is clear from the context, we simply write
${\sf tw}$. When talking about a tree decomposition
$(T,\left\\{{X_{t}~{}|~{}t\in V(T)}\right\\})$ of a graph $G$, to avoid any
confusion, we follow the common practice of referring to the vertices of $T$
as nodes, and reserve the term vertex exclusively for the vertices of $G$.

We now define a particular kind of tree decompositions called nice tree
decompositions, which come in handy while designing algorithms. A tree
decomposition $(T,\left\\{{X_{t}~{}|~{}t\in V(T)}\right\\})$ of a graph $G$ is
said to be a nice tree decomposition if it has the following properties. (a)
$T$ is rooted tree. (b) If $t\in V(T)$ is the root or a leaf, then
$X_{t}=\emptyset$. (c) Every non-leaf node $t$ of $T$ is one of the following
four types: (c.1) introduce vertex node: $t$ has exactly one child, say
$t^{\prime}$, and $X_{t}=X_{t^{\prime}}\cup\left\\{{z}\right\\}$ for some
$z\notin X_{t^{\prime}}$; (c.2) forget node: $t$ has exactly one child, say
$t^{\prime}$, and $X_{t}=X_{t^{\prime}}\setminus\left\\{{z}\right\\}$ for some
$z\in X_{t^{\prime}}$; (c.3) introduce edge node: $t$ has exactly one child,
say $t^{\prime}$, and $X_{t}=X_{t^{\prime}}$, and for some edge
$zz^{\prime}\in E(G)$ with $z,z^{\prime}\in X_{t}$, the node $t$ is labelled
with the edge $zz^{\prime}$. (c.4) join node: $t$ has exactly two children,
say $t^{\prime}$ and $t^{\prime\prime}$, and
$X_{t}=X_{t^{\prime}}=X_{t^{\prime\prime}}$.

Consider a graph $G$, a nice tree decomposition $(T,\\{X_{t}~{}|~{}t\in
V(T)\\})$ of $G$ and two nodes $t,t^{\prime}\in V(T)$, where $t^{\prime}$ is
the unique child of $t$. If $t$ is an introduce node with
$X_{t}=X_{t^{\prime}}\cup\left\\{{z}\right\\}$, then we say that the vertex
$z$ is introduced at $t$ or that $t$ introduces the vertex $z$. Similarly, if
$t$ is an introduce edge node labelled with an edge $zz^{\prime}\in E(G)$,
then we say that $zz^{\prime}$ is introduced at $t$ or that $t$ introduces
$zz^{\prime}$. And if $t$ is a forget node with
$X_{t}=X_{t^{\prime}}\setminus\left\\{{z}\right\\}$, then we say that the
vertex $z$ is forgotten at $t$ or that $t$ forgets the vertex $z$. We assume
throughout without loss of generality that in a nice tree decomposition, every
vertex of $G$ is introduced at exactly one node of $T$ and forgotten at
exactly one node of $T$; and that every edge of $G$ is introduced at exactly
one node of $T$. For a node $t$, we use $G_{t}$ to denote the subgraph of $G$
that consists of all the vertices and edges introduced in the subtree rooted
at $t$. When designing an algorithm for a problem parameterized by treewidth,
we assume that a nice tree decomposition of $G$ of width ${\sf tw}(G)$ is also
given as part of the input. This assumption is harmless because given an
$m$-vertex graph $G$, we can compute a nice tree decomposition of $G$ of width
$\mathcal{O}({\sf tw}(G))$ in time $2^{\mathcal{O}({\sf
tw}(G))}m^{\mathcal{O}(1)}$ (Bodlaender et al., 2016).

##  3 Preliminary Results and Observations

In this section, we record a few straightforward results that more or less
follow from the definition of (strongly) $(\alpha,\beta)$-compact graphs. We
will use some of these results in Sections 4 and 6. Specifically, results from
Sections 3.4, 3.5 and 3.6 will be used in later sections. But Sections 3.1,
3.2 and 3.3 are standalone sections. These sections respectively discuss the
weak NP-hardness of $[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD, the XP
algorithm for $[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD parameterized by
the number of agents and the maximum degree of $G$, and the polynomial time
algorithms for $[\mathtt{X}]$-$({1},{0})$-Compact-FD.

###  3.1 NP-Hardness of Compact Fair Division

We show the NP-hardness of deciding whether a proportional or envy-free
(strongly) $(\alpha,\beta)$-compact allocation exists. We note that the well-
known reduction from Partition (Lipton et al., 2004) that shows the NP-
hardness of Prop-FD and EF-FD can be extended to our setting as well. We just
need to represent the set of items as a clique. For the sake of completeness,
we state the result and sketch its proof.

######  Theorem 3.1.

For every fixed $\alpha,\beta\geq 1$, Prop-$({\alpha},{\beta})$-Compact-FD,
Complete-EF-$({\alpha},{\beta})$-Compact-FD and PO-
EF-$({\alpha},{\beta})$-Compact-FD are all NP-hard when the valuations are
encoded in binary, and even when there are only two agents with identical
valuations. So are the strongly compact variants of these three problems.

###### Proof.

To prove NP-hardness, we reduce from the Partition problem, in which the input
consists of $m$ non-negative integers $x_{1},x_{2},\ldots,x_{m}$ such that
$\sum_{j\in[m]}x_{j}=2W$; and the question is to decide if there exists a
subset of indices $J\subseteq[m]$ such that $\sum_{j\in J}x_{j}=W$. Given an
instance $(x_{1},x_{2},\ldots,x_{m})$ of Partition, we construct an instance
$(G,N,\mathcal{V})$ of $[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD as
follows, (where $[\mathtt{X}]$ is a placeholder for proportionality or envy-
freeness and completeness or envy-freeness and Pareto-optimality). We take $N$
= [2]; and for every $j\in[m]$, introduce an item $z_{j}$. We take $G$ to be
the clique with vertex set $\left\\{{z_{j}~{}|~{}j\in[m]}\right\\}$. Finally,
for $i\in N$, we define the valuation function
${{v_{i}}:{V(G)}\rightarrow{\mathbb{Q}_{\geq 0}}}$, where
$v_{i}(z_{j})=x_{j}$. Notice that for any $Z\subseteq V(G)$, the subgraph
$G[Z]$ is a clique and hence (strongly) $(\alpha,\beta)$-compact. Now, an
allocation ${{\pi}:{N}\rightarrow{2^{V(G)}}}$ is proportional (or complete and
envy-free, or Pareto-optimal and envy-free) if and only if
$v_{i}(\pi(i))=\sum_{z_{j}\in\pi(i)}x_{j}=(1/2)\cdot\sum_{j=1}^{m}x_{j}=W$ for
each $i\in[2]$. ∎

###  3.2 Compact Allocations of Bounded Degree Graphs

We now consider the special case of
$[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD when the maximum degree of the
graph $G$ is bounded, where $[\mathtt{X}]$ is a placeholder for
proportionality, envy-freeness or maximin fairness. Consider
$(G,N,\mathcal{V})$, where the degree of each vertex of $G$ is at most
$\Delta$. Observe then that for every $z\in V(G)$ and for every $j\geq 0$, the
number of vertices of $G$ that are at a distance of $j$ from $z$ is at most
$\Delta^{j}$. We thus have
${|{B_{G}(z,\beta)}|}\leq\sum_{j=0}^{\beta}\Delta^{j}\leq\Delta^{\beta+1}$. As
an immediate consequence of this observation, we derive the following lemma.

######  Lemma 3.2.

Consider an instance $(G,[n],\mathcal{V})$ of $({\alpha},{\beta})$-Compact-FD.
Then the number of $(\alpha,\beta)$-comapct allocations of
$(G,[n],\mathcal{V})$ is at most $m^{\alpha n}\cdot 2^{\alpha
n\cdot\Delta^{\mathcal{O}(\beta)}}$, where $\Delta$ is the maximum degree of
$G$. Moreover, we can enumerate all $(\alpha,\beta)$-compact allocations in
time $m^{\mathcal{O}(\alpha n)}\cdot 2^{\alpha
n\cdot\Delta^{\mathcal{O}(\beta)}}$.

###### Proof.

To prove the lemma, we will bound the possible number of choices for an
$(\alpha,\beta)$-compact allocation. Consider any $(\alpha,\beta)$-compact
allocation ${{\pi}:{N}\rightarrow{2^{V(G)}}}$. Then for every $i\in[n]$, there
exist vertices $z_{i}^{1},z_{i}^{2},\ldots,z_{i}^{\alpha}\in V(G)$ such that
$\pi(i)=\bigcup_{j=1}^{\alpha}B_{G[\pi(i)]}(z_{i}^{j},\beta)\subseteq\bigcup_{j=1}^{\alpha}B_{G}(z_{i}^{j},\beta)$.
And as we observed earlier, we have
${|{B_{G}(z,\beta)}|}\leq\Delta^{\mathcal{O}(\beta)}$, and thus
${|{\pi(i)}|}\subseteq\alpha\cdot\Delta^{\mathcal{O}(\beta)}$.

Now, the number of choices for $(z_{i}^{1},z_{i}^{2},\ldots,z_{i}^{\alpha})$
is at most $m^{\alpha}$; and the number of choices for $\pi(i)$ such that
$\pi(i)\subseteq\bigcup_{j=1}^{\alpha}B_{G}(z_{i}^{j},\beta)$ is at most
$2^{\alpha\cdot\Delta^{\mathcal{O}(\beta)}}$. Hence the number of choices for
$\pi(i)$ is at most $m^{\alpha}\cdot
2^{\alpha\cdot\Delta^{\mathcal{O}(\beta)}}$.

Notice now that any allocation $\pi$ is characterised by the tuple
$(\pi(1),\pi(2),\ldots,\pi(n))$. Therefore, the number of choices for $\pi$ is
at most $\left(m^{\alpha}\cdot
2^{\alpha\cdot\Delta^{\mathcal{O}(\beta)}}\right)^{n}=m^{\alpha n}\cdot
2^{\alpha n\cdot\Delta^{\mathcal{O}(\beta)}}$.

To enumerate all $(\alpha,\beta)$-compact allocations, we go over all possible
choices for $(z_{i}^{j}))_{i\in[n],j\in[\alpha]}$ and consider all possible
choices for $(\pi(1),\pi(2),\ldots,\pi(n))$, where
$\pi(i)\subseteq\bigcup_{j=1}^{\alpha}B_{G}(z_{i}^{j},\beta)$; and we check if
$(\pi(1),\pi(2),\ldots,\pi(n))$ constitutes an $(\alpha,\beta)$-compact
allocation. ∎

Notice that once we enumerate all $(\alpha,\beta)$-compact allocations, we can
verify if at least one of those allocations is fair, with respect to the
fairness concepts proportionality, envy-freeness and maximin-fairness. Notice
in particular that once we enumerate all $(\alpha,\beta)$-compact allocations,
we can compute $\Gamma((\alpha,\beta)\mathchar 45\relax\mathtt{com})\mathchar
45\relax\mathtt{mms}_{i}(G,[n],\mathcal{V})$ for every $i\in[n]$. Thus, as an
immediate consequence of Lemma 3.2, we have the following result.

######  Theorem 3.3.

For every $\alpha,\beta\geq 0$, Prop-$({\alpha},{\beta})$-Compact-FD,
EF-$({\alpha},{\beta})$-Compact-FD and MMS-$({\alpha},{\beta})$-Compact-FD
admit algorithms that run in time $m^{\mathcal{O}(\alpha n)}\cdot 2^{\alpha
n\cdot\Delta^{\mathcal{O}(\beta)}}$.

##### Analogous result for strongly compact variants.

We can use the same idea as in Lemma 3.2 to solve the strongly
$(\alpha,\beta)$-compact variants of the problems as well. If
${{\pi}:{[n]}\rightarrow{2^{V(G)}}}$ is a strongly compact allocation, then
for every $i\in[n]$, there exist $V_{i}^{1},V_{i}^{2},\ldots,V_{i}^{\alpha}$
such that $\pi(i)=V_{i}^{1}\cup V_{i}^{2}\cup\cdots V_{i}^{\alpha}$ and for
every $j\in[\alpha]$ and every $z,z^{\prime}\in V_{i}^{j}$, we have
$\text{dist}_{G[\pi(i)]}(z,z^{\prime})\leq\beta$. So, for any fixed
$\hat{z}_{i}^{j}\in V_{i}^{j}$, we have $V_{i}^{j}\subseteq
B_{G[\pi(i)]}(z_{i}^{j},\beta)\subseteq B_{G}(z_{i}^{j},\beta)$. Hence
${|{V_{i}^{j}}|}\leq{|{B_{G}(z_{i}^{j},\beta)}|}\leq\Delta^{\mathcal{O}(\beta)}$.
Thus the number of strongly $(\alpha,\beta)$-compact allocations is also
bounded by $m^{\alpha n}\cdot 2^{\alpha n\cdot\Delta^{\mathcal{O}(\beta)}}$.
To enumerate all such allocations, we go over all tuples
$(z_{i}^{j})_{i\in[n],j\in[\alpha]}$ such that $z_{i}^{j}\in V_{i}^{j}$.
Moreover, notice that for each tuple
$(V_{i}^{1},V_{i}^{2},\ldots,V_{i}^{\alpha})$, for each $j\in[\alpha]$ and
$z,z^{\prime}\in V_{i}^{j}$, we can indeed check in polynomial time whether
$\text{dist}_{G[\pi(i)]}(z,z^{\prime})\leq\beta$, where $\pi(i)=V_{i}^{1}\cup
V_{i}^{2}\cup\cdots V_{i}^{\alpha}$. That is, we can check whether $\pi(i)$ is
indeed strongly $(\alpha,\beta)$-compact. We thus have the following result.

######  Theorem 3.4.

For every $\alpha,\beta\geq 0$, Prop-Str-$({\alpha},{\beta})$-Compact-FD, EF-
Str-$({\alpha},{\beta})$-Compact-FD and MMS-Str-$({\alpha},{\beta})$-Compact-
FD admit algorithms that run in time $m^{\mathcal{O}(\alpha n)}\cdot 2^{\alpha
n\cdot\Delta^{\mathcal{O}(\beta)}}$.

###  3.3 The Case of $\bm{(\alpha,\beta)=(1,0)}$

Consider an instance $(G,N,\mathcal{V})$ of
$[\mathtt{X}]$-$({1},{0})$-Compact-FD. Observe that for any $(1,0)$-compact
allocation $\pi$, we have ${|{\pi(i)}|}\leq 1$ for every $i\in N$. That is,
every agent must receive at most one item. In this case, we can reduce the
problems corresponding to proportionality and maximin fairness to matching
problems. For proportionality, we construct the agents-items bipartite graph
$H$: there is a vertex in $H$ for every agent $i\in N$ and there is a vertex
in $H$ for every item $z\in V(G)$. And there is an edge in $H$ between $i\in
N$ and $z\in V(G)$ if $v_{i}(z)\geq(1/n)\cdot v_{i}(V(G))$. Notice that
$(G,N,\mathcal{V})$ admits an allocation that is proportional and
$(1,0)$-compact if and only if $H$ has a matching that saturates all the
agent-vertices, which we can check in polynomial time.

For maximin fairness, we apply an identical procedure. Recall that
$\Gamma((1,0)\mathchar 45\relax\mathtt{com})$ denotes the set of all $(1,0)$
compact allocations. For convenience, in this section, we simply write
$\mathtt{mms}_{i}$ for $\Gamma((1,0)\mathchar 45\relax\mathtt{com})\mathchar
45\relax\mathtt{mms}_{i}(G,N,\mathcal{V})$ for every $i\in N$. As before, we
construct the agents-items bipartite graph $H$ but with the following
difference. There is an edge in $H$ between $i$ and $z$ if and only if
$v_{i}(z)\geq\mathtt{mms}_{i}$. The rest of the arguments are identical to
that of proportionality. To construct $H$, we need to compute
$\mathtt{mms}_{i}$. But this is quite straightforward, as $\mathtt{mms}_{i}=0$
if $m<n$ and otherwise, $\mathtt{mms}_{i}$ is precisely the value agent $i$
has for her $n$th most valued item. We relegate a formal proof of this fact to
the appendix.

Recall that $\Gamma((1,0)\mathchar 45\relax\mathtt{com})$ denotes the set of
all $(1,0)$ compact allocations. For convenience, in this section, we simply
write $\mathtt{mms}_{i}$ for $\Gamma((1,0)\mathchar
45\relax\mathtt{com})\mathchar 45\relax\mathtt{mms}_{i}(G,N,\mathcal{V})$ for
every $i\in N$. The following lemma says that $\mathtt{mms}_{i}=0$ if $m<n$;
and otherwise, $\mathtt{mms}_{i}$ is precisely the value agent $i$ has for her
$n$th most valued item.

######  Lemma 3.5.

Fix $i\in[n]$ and consider an ordering
$\sigma^{i}=(z^{i}_{1},z^{i}_{2},\ldots,z^{i}_{m})$ of the items such that
$v_{i}(z^{i}_{1})\geq v_{i}(z^{i}_{2})\geq\cdots\geq v_{i}(z^{i}_{m})$. If
$m<n$, then $\mathtt{mms}_{i}=0$; otherwise
$\mathtt{mms}_{i}=v_{i}(z^{i}_{n})$.

###### Proof.

Fix $i\in[n]$. Suppose first that $m<n$. Then, for any $(1,0)$-compact
allocation ${{\pi^{\prime}}:{[n]}\rightarrow{2^{V(G)}}}$, there exists an
agent $j^{\prime}\in[n]$ such that $\pi^{\prime}(j^{\prime})=\emptyset$. Hence
$v_{i}(\pi^{\prime}(j^{\prime}))=0$, and in particular, $\min_{j\in
N}v_{i}(\pi^{\prime}(j))=v_{i}(\pi^{\prime}(j^{\prime}))=0$. Thus, by the
definition of $\mathtt{mms}_{i}$, we have $\mathtt{mms}_{i}=0$. Suppose now
that $m\geq n$. Consider the ordering
$\sigma^{i}=(z^{i}_{1},z^{i}_{2},\ldots,z^{i}_{m})$. Recall that we have
$v_{i}(z^{i}_{1})\geq v_{i}(z^{i}_{2})\geq\cdots\geq v_{i}(z^{i}_{m})$. We
will show that $\mathtt{mms}_{i}=v_{i}(z^{i}_{n})$. Let us first see that
$\mathtt{mms}_{i}\geq v_{i}(z^{i}_{n})$. Consider the allocation $\pi$ defined
by $\pi(j)=z^{i}_{j}$ for every $j\in[n]$. First, the allocation $\pi$ is
$(1,0)$-compact as each agent receives at most one item. Second, we have
$v_{i}(z^{i}_{n})\leq v_{i}(z^{i}_{j})$ for every $j\in[n]$, and therefore,
$\min_{j\in[n]}v_{i}(\pi(j))=v_{i}(\pi(n))=v_{i}(z^{i}_{n})$. Thus, by the
definition of $\mathtt{mms}_{i}$, we have
$\mathtt{mms}_{i}\geq\min_{j\in[n]}v_{i}(\pi(j))=v_{i}(z^{i}_{n})$. Let us now
see that $\mathtt{mms}_{i}\leq v_{i}(z^{i}_{n})$. Let $\phi$ be a
$(1,0)$-compact allocation that maximises $\min_{j\in[n]}v_{i}(\phi(j))$, and
we thus have $\mathtt{mms}_{i}=\min_{j\in[n]}v_{i}(\phi(j))$. If there exists
an agent, say $j^{\prime}\in[n]$, such that $j^{\prime}$ does not receive any
item under $\phi$, i.e., $\phi(j^{\prime})=\emptyset$, then
$v_{i}(\phi(j^{\prime}))=0$, which implies that
$\mathtt{mms}_{i}=\min_{j\in[n]}v_{i}(\phi(j))=0\leq v_{i}(z^{i}_{n})$. So,
assume that $\phi(j)\neq\emptyset$ for every $j\in[n]$. Since there are $n$
agents, and since $\phi$ is $(1,0)$-compact, $\phi$ allocates exactly $n$
items. In particular, $\phi$ allocates $z^{i}_{r}$ for some $r\geq n$, which
implies that $\mathtt{mms}_{i}=\min_{j\in[n]}v_{i}(\phi(j))\leq
v_{i}(z^{i}_{r})\leq v_{i}(z^{i}_{n})$. We have thus shown that
$\mathtt{mms}_{i}=v_{i}(z^{i}_{n})$. ∎

As for envy-freeness, we impose the additional constraint that each agent must
receive exactly one item. Then the corresponding problem is polynomial time
solvable, as shown by Gan et al. (2019). Their algorithm is also a matching
algorithm, which works as follows: We construct the graph where each agent is
adjacent to her most valued items and look for a matching that saturates all
agents or a Hall’s violator. If we find a matching, then we have an envy-free
allocation; else, we remove a Hall’s violator and recurse.

We thus have the following result.

######  Theorem 3.6.

$[\mathtt{X}]$-$({1},{0})$-Compact-FD is polynomial time solvable, where
$[\mathtt{X}]$ is a placeholder for proportionality, envy-freeness or maximin
fairness.

###  3.4 Diameter of a Connected $\bm{(\alpha,\beta)}$-Compact Graph

Observe that $(\alpha,\beta)$-compactness is not a subgraph-closed property.
That is, if $G$ is an $(\alpha,\beta)$-compact graph and $H$ is a subgraph of
$G$ then $H$ need not necessarily be $(\alpha,\beta)$-compact. But if $H$ is a
connected component of $G$, then $H$ necessarily is $(\alpha,\beta)$-compact.
Moreover, the diameter of $H$ is bounded by $\mathcal{O}(\alpha\beta)$. We
record this fact below.

######  Lemma 3.7.

Let $G$ be an $(\alpha,\beta)$-compact graph. Then for every connected
component $H$ of $G$, $H$ is $(\alpha,\beta)$-compact and
$\text{diam}(H)=\mathcal{O}(\alpha\beta)$.

###### Proof.

Since $G$ is $(\alpha,\beta)$-compact, there exist vertices
$z_{1},z_{2},\ldots,z_{\alpha}\in V(G)$ such that
$V(G)=\bigcup_{j\in[\alpha]}B_{G}(z_{j},\beta)$. Consider a connected
component $H$ of $G$. Notice that for every $j\in[\alpha]$ such that $H$
contains the vertex $z_{j}$, we have $B_{G}(z_{j},\beta)=B_{H}(z_{j},\beta)$.
Let $J=\left\\{{j\in[\alpha]~{}|~{}z_{j}\in V(H)}\right\\}$. Then
$V(H)=\bigcup_{j\in J}B_{H}(z_{j},\beta)$. As ${|{J}|}\leq\alpha$, $H$ is
$(\alpha,\beta)$-compact.

To see that $\text{diam}(H)=\mathcal{O}(\alpha\beta)$, observe first that for
every $j\in J$ and $z,z^{\prime}\in B_{H}(z_{j},\beta)$, we have
$\text{dist}_{H}(z,z^{\prime})\leq\text{dist}_{H}(z,z_{j})+\text{dist}_{H}(z_{j},z^{\prime})\leq
2\beta$. Now, consider an auxiliary graph $H^{\prime}$ on ${|{J}|}$ vertices,
defined as follows. For each $j\in J$, $H^{\prime}$ contains a vertex $y_{j}$.
For $j,j^{\prime}\in J$, $y_{j}y_{j^{\prime}}\in E(H^{\prime})$ if and only if
either $B_{H}(z_{j},\beta)\cap B_{H}(z_{j^{\prime}},\beta)\neq\emptyset$ or
there exists $z\in B_{H}(z_{j},\beta)$ and $z^{\prime}\in
B_{H}(z_{j^{\prime}},\beta)$ such that $zz^{\prime}\in E(H)$. (Informally,
$H^{\prime}$ is obtained from $H$ by “contracting” each $B_{H}(z_{j},\beta)$
into a single vertex). Notice that $H^{\prime}$ has ${|{J}|}\leq\alpha$
vertices; and since $H$ is connected, $H^{\prime}$ is connected as well. Now,
consider $z,z^{\prime}\in V(H)$. Let us observe that $H$ contains a
$z$-$z^{\prime}$ path of length $\mathcal{O}(\alpha\beta)$. Let
$j,j^{\prime}\in J$ be such that $z\in B_{H}(z_{j},\beta)$ and $z^{\prime}\in
B_{H}(z_{j^{\prime}},\beta)$. Let $Q$ be a path in $H^{\prime}$ from $y_{j}$
to $y_{j^{\prime}}$; the length of $Q$ is at most ${|{J}|}-1\leq\alpha-1$.
Observe that we can “expand out” each vertex of $Q$ to a path in $H$ of length
at most $2\beta$; and thus obtain a $z$-$z^{\prime}$ path of length
$\mathcal{O}(\alpha\beta)$. Hence
$\text{dist}_{H}(z,z^{\prime})=\mathcal{O}(\alpha\beta)$ for every
$z,z^{\prime}\in V(H)$, and the lemma follows. ∎

######  Observation 3.8.

Let us observe an immediate consequence of Lemma 3.9. Consider a graph $G$ and
an $(\alpha,\beta)$-compact allocation ${{\pi}:{[n]}\rightarrow{2^{V(G)}}}$.
Then the subgraph of $\bm{G}$ induced by the set of allocated vertices, i.e.,
$\bm{G[\pi([n])]}$, is $\bm{(n\alpha,\beta)}$ compact. To see this, notice
that for each $i\in[n]$, there exist
$z_{1}^{i},z_{2}^{i},\ldots,z_{\alpha}^{i}$ such that
$\pi(i)=\bigcup_{j=1}^{\alpha}B_{G[\pi(i)]}(z_{j}^{i},\beta)$. Notice that
$B_{G[\pi(i)]}(z_{j}^{i},\beta)\subseteq B_{G[\pi([n])]}(z_{j}^{i},\beta)$.
And we have
$\pi([n])=\bigcup_{i=1}^{n}\pi(i)=\bigcup_{i=1}^{n}\bigcup_{j=1}^{\alpha}B_{G[\pi(i)]}(z_{j}^{i},\beta)\subseteq\bigcup_{i=1}^{n}\bigcup_{j=1}^{\alpha}B_{G[\pi([n])]}(z_{j}^{i},\beta)$.
That is, $G[\pi([n])]$ can be covered by at most $n\alpha$ balls, each of
radius at most $\beta$, which implies that $G[\pi(n)]$ is
$(n\alpha,\beta)$-compact. But then, Lemma 3.7 implies that
$\bm{\text{diam}(H)=\mathcal{O}(n\alpha\beta)}$ for every connected component
$\bm{H}$ of $\bm{G[\pi([n])]}$.

###  3.5 Annotated Allocations

Consider a graph $G$. Suppose that $G$ is a $(\alpha,\beta)$-compact. Then
there exist vertices $z_{1},z_{2},\ldots,z_{\alpha}\in V(G)$ such that
$V(G)=\bigcup_{j\in[\alpha]}B_{G}(z_{j},\beta)$. Let $G^{\prime}$ be the graph
obtained from $G$ by adding a new vertex $\hat{z}$ and making $\hat{z}$
adjacent to $z_{1},z_{2},\ldots z_{\alpha}$. We then have
$V(G^{\prime})=B_{G^{\prime}}(\hat{z},\beta+1)$. That is, $G^{\prime}$ is
$(1,\beta+1)$-compact. To exploit this idea in our algorithms, we introduce an
annotated variant of $({\alpha},{\beta})$-Compact-FD. For a graph $G$, a
vertex $\hat{z}\in V(G)$ and a non-negative integer $\beta$, we say that $G$
is a $(\hat{z};\beta)$-annotated graph if $z\in B_{G}(\hat{z},\beta)$ for
every $z\in V(G)$, i.e., every vertex in $G$ is within a distance of at most
$\beta$ from $\hat{z}$. Consider a graph $G$, a set of agents $N=[n]$ and an
ordered sequence $(\hat{z}_{i})_{i\in N}$ of $n$ distinct vertices
$\hat{z}_{i}\in V(G)$. We say that an allocation
${{\pi}:{N}\rightarrow{2^{V(G)}}}$ is $((\hat{z}_{i})_{i\in
N};\beta)$-annotated if for every $i\in[n]$, (i) $\hat{z}_{i}\in\pi(i)$ and
(ii) $G[\pi(i)]$ is a $(\hat{z}_{i};\beta)$-annotated graph. And we define the
associated computational problem Annotated-FD as follows: Given
$(G,N,\mathcal{V})$, $(\hat{z}_{i})_{i\in N}$ and $\beta$ as input, does
$(G,N,\mathcal{V})$ admit a $((\hat{z}_{i})_{i\in N};\beta)$-annotated
allocation? We can augment the definition of the problem to include any of the
fairness concepts as well. With respect to the fairness concept
$[\mathtt{X}]$, we thus define $[\mathtt{X}]$-Annotated-FD: Given
$(G,N,\mathcal{V})$, $(\hat{z}_{i})_{i\in N}$ and $\beta$ as input, does
$(G,N,\mathcal{V})$ admit an allocation that is $[\mathtt{X}]$-fair and
$((\hat{z}_{i})_{i\in N};\beta)$-annotated?444To be precise, when it comes to
annotated allocations, while the definitions of proportional and envy-free
allocations remain unchanged, we must adapt the definition of maximin-fair
annotated allocations appropriately. For $(\hat{z}_{i})_{i\in N}$, we define
$\Gamma(((\hat{z}_{i})_{i\in N};\beta)\mathchar 45\relax\mathtt{anno})$ to be
the set of all $((\hat{z}_{i})_{i\in N};\beta)$-annotated allocations. And an
allocation $\pi$ is $\Gamma(((\hat{z}_{i})_{i\in N};\beta)\mathchar
45\relax\mathtt{anno})$-maximin fair if
$v_{i}(\pi(i))\geq\Gamma(((\hat{z}_{i})_{i\in N};\beta)\mathchar
45\relax\mathtt{anno})\mathchar 45\relax\mathtt{mms}_{i}(G,N,\mathcal{V})$ for
every $i\in N$. The following lemma says that to solve an instance of
$[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD, it is enough to solve
$m^{\mathcal{O}(\alpha n)}$ many instances of $[\mathtt{X}]$-Annotated-FD.

######  Lemma 3.9.

Consider an instance $(G,[n],\mathcal{V})$ of
$[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD. Then there exist
$m^{\mathcal{O}(\alpha n)}$ many instances of $[\mathtt{X}]$-Annotated-FD such
that $(G,[n],\mathcal{V})$ is a yes-instance of
$[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD if and only if at least one of
the $m^{\mathcal{O}(\alpha n)}$ instances of $[\mathtt{X}]$-Annotated-FD is a
yes-instances. Moreover, these $m^{\mathcal{O}(\alpha n)}$ instances of
$[\mathtt{X}]$-Annotated-FD can be constructed in time $m^{\mathcal{O}(\alpha
n)}$.

###### Proof.

Let $T$ be the set of all tuples $(C_{1},C_{2},\ldots,C_{n})$ such that for
every $i\in[n]$, $C_{i}\subseteq V(G)$, ${|{C_{i}}|}\leq\alpha$, and
$C_{i}\cap C_{j}=\emptyset$ for distinct $i,j\in[n]$. Corresponding to each
tuple $\tau=(C_{1},C_{2},\ldots,C_{n})\in T$, we construct an instance
$(G^{\tau},[n],\mathcal{V}^{\tau};(\hat{z}_{i})_{i\in[n]},\beta^{\tau})$ of
$[\mathtt{X}]$-Annotated-FD as follows. To construct $G^{\tau}$, we add $n$
new vertices $\hat{z}_{1},\hat{z}_{2},\ldots,\hat{z}_{n}$ to $G$; and for each
$i\in[n]$, we make $\hat{z}_{i}$ adjacent to all the vertices in $C_{i}$. We
set $v^{\tau}_{i}(\hat{z}_{j})=0$ and $v^{\tau}_{i}(z)=v_{i}(z)$ if $z\in
V(G^{\tau})\setminus\left\\{{\hat{z}_{j}~{}|~{}j\in[n]}\right\\}$. And we take
$\beta^{\tau}=\beta+1$.

First, notice that ${|{T}|}=m^{\mathcal{O}(\alpha n)}$, as the number of
subsets of $V(G)$ of size at most $\alpha$ is
$\sum_{j=0}^{\alpha}\binom{m}{j}=m^{\mathcal{O}(\alpha)}$; and hence there are
$m^{\mathcal{O}(\alpha n)}$ tuples $(C_{1},C_{2},\ldots,C_{n})$ with
${|{C_{i}}|}\leq\alpha$ for every $i\in[n]$. And notice that for each tuple
$\tau\in T$, we can construct the corresponding instance
$(G^{\tau},[n],\mathcal{V}^{\tau};(\hat{z}_{i})_{i\in[n]},\beta^{\tau})$ of
Annotated-FD in time $m^{\mathcal{O}(1)}$. We can also verify that
$(G,[n],\mathcal{V})$ is a yes-instance of
$[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD if and only if
$(G^{\tau},[n],\mathcal{V}^{\tau};(\hat{z}_{i})_{i\in[n]},\beta^{\tau})$ is a
yes-instance of $[\mathtt{X}]$-Annotated-FD for some $\tau\in T$.

Consider an $(\alpha,\beta)$-compact allocation
${{\pi}:{[n]}\rightarrow{2^{V(G)}}}$. Then for each $i\in[n]$, there exist
$z^{i}_{1},z^{i}_{2},\ldots,z^{i}_{\alpha}$ such that
$\pi(i)=\bigcup_{j\in[\alpha]}B_{G[\pi(i)]}(z^{i}_{j},\beta)$. Consider the
tuple $\tau=(C_{i})_{i\in[n]}$, where
$C_{i}=\left\\{{z^{i}_{1},z^{i}_{2},\ldots,z^{i}_{\alpha}}\right\\}$. Then
$\tau\in T$. Consider the allocation
${{\pi^{\tau}}:{[n]}\rightarrow{2^{V(G^{\tau})}}}$, where
$\pi^{\tau}(i)=\pi(i)\cup\left\\{{\hat{z}_{i}}\right\\}$. Notice that
$\pi^{\tau}$ is a $((\hat{z}_{i})_{i\in[n]};\beta+1)$-annotated allocation.
This follows from the fact that for $i\in[n]$, and $z\in\pi(i)$, there exists
$j\in[\alpha]$ such that $\text{dist}_{G[\pi(i)]}(z^{i}_{j},z)\leq\beta$,
which implies that
$\text{dist}_{G^{\tau}[\pi^{\tau}(i)]}(\hat{z}_{i},z)\leq\beta+1$. Notice also
that for every $i,j\in[n]$, as $v^{\tau}_{i}(\hat{z}_{j})=0$, we have
$v_{i}(\pi(j))=v^{\tau}_{i}(\pi^{\tau}(j))$; and hence $\pi$ is
$[\mathtt{X}]$-fair if and only if $\pi^{\tau}$ is $[\mathtt{X}]$-fair.

Conversely, suppose there exists $\tau=(C_{i})_{i\in[n]}\in T$ such that
${{\phi}:{[n]}\rightarrow{2^{V(G^{\tau})}}}$ is a
$((\hat{z}_{i})_{i\in[n]};\beta+1)$-annotated allocation. Then the allocation
${{\phi^{\prime}}:{[n]}\rightarrow{2^{V(G)}}}$ defined by
$\phi^{\prime}(i)=\phi(i)\setminus\left\\{{\hat{z}_{i}}\right\\}$ for every
$i\in[n]$ is an $(\alpha,\beta)$-compact allocation. To see this, fix
$i\in[n]$ and consider the set $D_{i}=\phi(i)\cap N_{G^{\tau}}(\hat{z}_{i})$.
Notice that $D_{i}\subseteq C_{i}$, and hence ${|{D_{i}}|}\leq\alpha$. Now
consider $z\in\phi(i)\setminus\left\\{{\hat{z}_{i}}\right\\}$, there exists a
$z$-$\hat{z}_{i}$ path of length at most $\beta+1$ in $G^{\tau}[\phi(i)]$. Let
$P$ be such a path, and let $y_{i}$ be the unique neighbor of $\hat{z}_{i}$ in
$P$. Then $y_{i}\in D_{i}$. Let $P^{\prime}_{i}$ denote the $z$-$y_{i}$
subpath of $P$. Notice that $P^{\prime}_{i}$ is a path in
$G[\phi^{\prime}(i)]$ and that $P^{\prime}_{i}$ has length at most $\beta$.
Thus $z\in B_{G[\phi^{\prime}(i)]}(y_{i},\beta)$. Since $z$ was an arbitrary
element of $\phi^{\prime}(i)=\phi(i)\setminus\left\\{{\hat{z}_{i}}\right\\}$,
we can conclude that $\phi(i)=\bigcup_{y\in D_{i}}B_{G[\phi(i)]}(y,\beta)$,
which implies that $G[\phi(i)]$ is $(\alpha,\beta)$-compact. Also, as
$v^{\tau}_{i}(\phi(j))=v_{i}(\phi^{\prime}(j))$, $\phi$ is $[\mathtt{X}]$-fair
if and only if $\phi^{\prime}$ is $[\mathtt{X}]$-fair. ∎

######  Remark 3.10.

Consider a tuple $\tau=(C_{1},C_{2},\ldots,C_{n})$ as defined in the proof of
Lemma 3.9. And consider our construction of the instance
$(G^{\tau},[n],\mathcal{V}^{\tau};(\hat{z}_{i})_{i\in[n]},\beta^{\tau})$ of
$[\mathtt{X}]$-Annotated-FD. Recall that $\beta^{\tau}=\beta+1$. Consider
$z\in V(G)$ such that $z\notin\bigcup_{i\in[n]}\bigcup_{z^{\prime}\in
C_{i}}B_{G}(z^{\prime},\beta)$. Notice that
$z\notin\bigcup_{i\in[n]}B_{G^{\tau}}(\hat{z}_{i},\beta+1)$. Hence $z$ remains
un-allocated under _every_ $((\hat{z}_{i})_{i\in[n]};\beta+1)$-annotated
allocation. We can therefore safely delete $z$ from $V(G)$. Therefore, we can
assume without loss of generality that
$V(G)=\bigcup_{i\in[n]}\bigcup_{z^{\prime}\in C_{i}}B_{G}(z^{\prime},\beta)$,
which implies that $G$ is $(\alpha n,\beta)$-compact, as
${|{C_{i}}|}\leq\alpha$ for every $i\in[n]$. Then, by Observation 3.8, we have
$\text{diam}(H)=\mathcal{O}(n\alpha\beta)$ for every connected component $H$
of $G$.

###  3.6 The Complexity of Recognising (Strongly) Compact Graphs

Consider the recognition problem for (strongly) $(\alpha,\beta)$-compact
graphs. That is, the problem of testing whether a given a graph $G$ is
(strongly) $(\alpha,\beta)$-compact (for fixed $\alpha$ and $\beta$). We can
recognise $(\alpha,\beta)$-compact graphs in polynomial time. Given an
$m$-vertex graph $G$, for every choice of $\alpha$ vertices
$z_{1},z_{2},\ldots,z_{\alpha}$, we can check if
$V(G)=\bigcup_{j\in[\alpha]}B_{G}(z_{j},\beta)$, and we can do this in time
$m^{\mathcal{O}(1)}$. Since the number of choices for
$z_{1},z_{2},\ldots,z_{\alpha}$ is $m^{\mathcal{O}(\alpha)}$, we conclude that
we can check if $G$ is $(\alpha,\beta)$-compact in time
$m^{\mathcal{O}(\alpha)}$. As $\alpha$ is a constant, we can indeed check if
$G$ is $(\alpha,\beta)$-compact in polynomial time. For future reference, we
note this fact.

######  Remark 3.11.

For fixed $\alpha$ and $\beta$, we can recognise $(\alpha,\beta)$-compact
graphs in polynomial time.

But the case of strong compactness is quite different. For $\alpha\leq 2$, the
problem is polynomial time solvable and for $\alpha\geq 3$, the problem is NP-
hard. If $\alpha=1$, then the problem is the same as testing whether
$\text{diam}(G)\leq\beta$, which can be done in polynomial time. If
$\alpha=2$, then the problem can be reduced to 2-SAT, and hence it can still
be solved in polynomial time. For $\alpha\geq 3$, the problem is NP-hard even
when $\beta=1$. Notice that $G$ is strongly $(\alpha,1)$-compact if and only
if there exist $V_{1},V_{2}\ldots,V_{\alpha}\subseteq V(G)$ such that
$G[V_{i}]$ is a clique for every $i\in[\alpha]$. So checking whether $G$ is
$(\alpha,1)$-compact is the same as checking whether $V(G)$ can be covered by
$\alpha$ cliques. This problem is called the $\alpha$-Clique Cover problem,
which is known to be NP-complete (Karp, 1972). In fact, notice that
$\alpha$-Clique Cover is equivalent to the well known $\alpha$-Colouring
problem. For a graph $G$, $V(G)$ can be covered using $\alpha$ cliques if and
only if $V(\overline{G})$ can be covered using $\alpha$ independent sets,
where $\overline{G}$ is the complement of $G$; and $V(\overline{G})$ can be
covered using $\alpha$ independent sets if and only if the vertices of
$\overline{G}$ can be properly coloured using $\alpha$ colours.

##  4 Strong NP-Hardness of (Strongly) Compact Fair Division

In this section, we establish the strong NP-hardness of (strongly) compact
fair division. We consider three fairness and efficiency combinations (i)
proportionality, (ii) envy-freeness plus completeness and (iii) envy-freeness
plus Pareto-optimality. For each of these three choices, we show that the
corresponding problem of checking whether there exists a fair (strongly)
$(\alpha,\beta)$-compact allocation is strongly NP-hard for every fixed
$\alpha\geq 3$ and $\beta\geq 0$.555Notice that even though Theorem 3.1
already establishes the NP-hardness of these problems for $\alpha,\beta\geq
1$, Theorem 3.1 only implies _weak_ NP-hardness, as we reduced from Partition.
Besides Theorem 3.1 only works for $\beta\geq 1$. These results hold even the
graph $G$ is edgeless and thus has treewidth $0$. And notice that if $G$ is an
edgeless graph, then for any $S\subseteq V(G)$, $G[S]$ is (strongly)
$(\alpha,\beta)$-compact if and only if ${|{S}|}\leq\alpha$. For
proportionality and envy-freeness + completeness, we also show that the
strongly compact variants of the corresponding problems are NP-hard for every
fixed $\alpha,\beta\geq 1$. All the hardness results hold even when the
valuations are additive and polynomially bounded. We prove these results one
by one.

###  4.1 Strong NP-Hardness of $\bm{(\alpha,\beta)}$-Compact FD for
$\bm{\alpha\geq 3}$

######  Theorem 4.1.

For every $\alpha\geq 3$ and $\beta\geq 0$, Prop-$({\alpha},{\beta})$-Compact-
FD is strongly NP-complete.

###### Proof.

Fix $\alpha\geq 3$ and $\beta\geq 0$. Membership of
Prop-$({\alpha},{\beta})$-Compact-FD in NP is trivial: Given an allocation, we
can verify in polynomial time whether it is proportional, and by Remark 3.11,
we can also verify whether the allocation is $(\alpha,\beta)$-compact. We now
show NP-hardness by a reduction from Exact Cover by ${\alpha}$-Sets
(X$\alpha$C), which is known to be NP-complete for every $\alpha\geq 3$ (Karp,
1972).666Exact Cover by ${3}$-Sets (X$3$C) was, in fact, one of Karp’s
original 21 NP-complete problems (Karp, 1972). The original paper of Karp only
shows the NP hardness of X3C. But it is straightforward to extend that result
to show NP-hardness of X$\alpha$C for every $\alpha>3$ as well. For the sake
of completeness, we sketch a proof of this fact in the appendix. In
X$\alpha$C, the input consists of a set $X$ such that ${|{X}|}=\alpha s$ and a
family $\mathcal{F}\subseteq 2^{X}$ of subsets of $X$ such that
${|{F}|}=\alpha$ for every $F\in\mathcal{F}$; and the question is to decide if
$(X,\mathcal{F})$ has an exact cover, i.e., a sub-family
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ such that
${|{\mathcal{F}^{\prime}}|}=s$ and $\bigcup_{F\in\mathcal{F}^{\prime}}F=X$.
Consider an instance $(X,\mathcal{F})$ of X$\alpha$C. Let ${|{F}|}=r$ and
$\mathcal{F}=\left\\{{F_{1},F_{2},\ldots,F_{r}}\right\\}$. Notice first that
if $r={|{\mathcal{F}}|}<s$, then $(X,\mathcal{F})$ is a no-instance of
X$\alpha$C, and in this case, we return a trivial no-instance of
Prop-$({\alpha},{\beta})$-Compact-FD. If $r=s$, then $(X,\mathcal{F})$ is a
yes-instance if and only if $\bigcup_{F\in\mathcal{F}}=X$, and we can verify
this in polynomial time. In this case, we return a trivial yes-instance or no-
instance of Prop-$({\alpha},{\beta})$-Compact-FD accordingly. So from now on,
we assume without loss of generality that $r>s$. Given $(X,\mathcal{F})$, we
now construct an instance $(G,N,\mathcal{V})$ of
Prop-$({\alpha},{\beta})$-Compact-FD as follows. Corresponding to each
$F_{i}\in\mathcal{F}$, we introduce an agent $i$; in addition we introduce a
“dummy” agent $r+1$. Thus $N=[r+1]$. Corresponding to each $x\in X$, we
introduce an item $w_{x}$; in addition, we introduce $r-s$ “auxiliary” items
$y_{1},y_{2},\ldots,y_{r-s}$ and a “special” item $y_{*}$. And we define the
graph $G$ to be the edge-less graph with vertex set
$V(G)=\left\\{{y_{*}}\right\\}\cup\left\\{{y_{j}~{}|~{}j\in[r-s]}\right\\}\cup\left\\{{w_{x}~{}|~{}x\in
X}\right\\}$. Finally, we define the valuation functions as follows. Consider
$i\in[r]$. For each $x\in X$, we set

$v_{i}(w_{x})=\begin{cases}1/(\alpha r+\alpha),&\text{ if }x\in F_{i}\\\
0,&\text{ if }x\notin F_{i};\end{cases}$

$v_{i}(y_{j})=1/(r+1)$ for every $j\in[r-s]$; and $v_{i}(y_{*})=s/(r+1)$.
Finally, $v_{r+1}(w_{x})=0$ for every $x\in X$; $v_{r+1}(y_{j})=0$ for every
$j\in[r-s]$; and $v_{r+1}(y_{*})=1$. Notice that we have
$v_{i}(V(G))=\sum_{z\in V(G)}v_{i}(z)=1$ for every $i\in N$. And notice also
that since $G$ is edge-less, for every non-empty subset $S\subseteq V(G)$, the
subgraph $G[S]$ is $(\alpha,\beta)$-compact if and only if
${|{S}|}\leq\alpha$.

Assume that $(X,\mathcal{F})$ is a yes-instance, and let
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ be an exact cover for
$(X,\mathcal{F})$. Then ${|{\mathcal{F}}|}=s$ and
${|{\mathcal{F}\setminus\mathcal{F}^{\prime}}|}=r-s$. Assume without loss of
generality that
$\mathcal{F}\setminus\mathcal{F}^{\prime}=\left\\{{F_{1},F_{2},\ldots,F_{r-s}}\right\\}$.
We define an allocation ${{\pi}:{N}\rightarrow{2^{V(G)}}}$ as follows.
Consider $i\in[r]$. If $F_{i}\in\mathcal{F}^{\prime}$, then we set
$\pi(i)=\left\\{{w_{x}~{}|~{}x\in F_{i}}\right\\}$ so that
$v_{i}(\pi(i))=\sum_{x\in F_{i}}v_{i}(w_{x})={|{F_{i}}|}(1/(\alpha
r+\alpha))=1/(r+1)$; and if
$F_{i}\in\mathcal{F}\setminus\mathcal{F}^{\prime}$, then $i\in[r-s]$, and we
set $\pi(i)=\left\\{{y_{i}}\right\\}$ so that $v_{i}(\pi(i))=1/(r+1)$. And we
set $\pi(r+1)=\left\\{{y_{*}}\right\\}$ so that $v_{r+1}(\pi(r+1))=1$. Notice
that $\pi$ is a complete allocation; and as $v_{i}(\pi(i))\geq 1/(r+1)$ for
every $i\in N$, $\pi$ is proportional. As ${|{\pi(i)}|}\leq\alpha$ for every
$i\in N$, $\pi$ is $(\alpha,\beta)$-compact as well.

Conversely, assume that $(G,N,\mathcal{V})$ admits an
$(\alpha,\beta)$-compact, proportional allocation, say
${{\phi}:{N}\rightarrow{2^{V(G)}}}$. First, as $\phi$ is proportional, we have
$v_{i}(\phi(i))\geq(1/{|{N}|})\cdot v_{i}(V(G))=1/(r+1)$ for every $i\in N$.
In particular, $v_{r+1}(\phi(r+1))\geq 1/(r+1)$, which implies that
$y_{*}\in\phi(r+1)$. Thus $y_{*}\notin\phi(i)$ for every $i\in[r]$. Let
$R=\\{i\in[r]~{}|~{}\phi(i)\subseteq\\{w_{x}~{}|~{}x\in X\\}\\}$. Observe that
${|{R}|}\geq s$. To see this, notice that there exist at most $r-s$ agents
$i\in[r]$ such that $y_{j}\in\phi(i)$ for some $j\in[r-s]$. Therefore there
exist at least $s$ agents $i\in[r]$ such that
$\phi(i)\subseteq\left\\{{w_{x}~{}|~{}x\in X}\right\\}$. Now, for every $i\in
R$, we must have $w_{x}\in\phi(i)$ for every $x\in F_{i}$, for otherwise
$v_{i}(\phi(i))<1/(r+1)$. As $\phi$ is $(\alpha,\beta)$-compact and $G$ is
edge-less, we have ${|{\phi(i)}|}\leq\alpha$, and hence
$\phi(i)=\left\\{{w_{x}~{}|~{}x\in F_{i}}\right\\}$ for every $i\in R$. Also,
since $\phi$ is an allocation, for distinct $i,i^{\prime}\in R$, we have
$\phi(i)\cap\phi(i^{\prime})=\emptyset$ and hence $F_{i}\cap
F_{i^{\prime}}=\emptyset$. Then ${|{R}|}\geq s$ implies that ${|{\bigcup_{i\in
R}F_{i}}|}=\alpha{|{R}|}\geq\alpha s$. Since ${|{X}|}=\alpha s$, we can
conclude that ${|{R}|}=s$ and $\bigcup_{i\in R}F_{i}=X$, and hence
$\left\\{{F_{i}~{}|~{}i\in R}\right\\}$ is an exact cover for
$(X,\mathcal{F})$. ∎

By slightly modifying the reduction in the proof of Theorem 4.1, we can show
that Complete-EF-$({\alpha},{\beta})$-Compact-FD is NP-complete as well. We
only sketch the proof below as the arguments are identical to the ones used to
prove Theorem 4.1.

######  Theorem 4.2.

For every $\alpha\geq 3$ and $\beta\geq 0$, Complete-
EF-$({\alpha},{\beta})$-Compact-FD is strongly NP-complete.

###### Proof Sketch.

Membership in NP is again trivial. To show hardness, we reduce from
(X$\alpha$C). Given an instance $(X,\mathcal{F})$, we proceed exactly as in
the proof of Theorem 4.1 except for the following three differences. (1) We no
longer have the agent $r+1$. That is, $N=[r]$ and $i\in N$ corresponds to the
set $F_{i}\in\mathcal{F}$. (2) We no longer have the item $y_{*}$. Thus the
graph $G$ is the edge-less graph with vertex set
$V(G)=\left\\{{y_{j}~{}|~{}j\in[r-s]}\right\\}\cup\left\\{{w_{x}~{}|~{}x\in
X}\right\\}$. (3) We modify the valuation functions to ensure that (a)
$v_{i}(\\{w_{x}~{}|~{}x\in X\\})=v_{i}(\\{y_{j}\\})$ for every $i\in[r]$ and
$j\in[r-s]$ and (b) $\sum_{z\in V(G)}v_{i}(z)=1$ for every $i\in N$.
Specifically, we define the valuation functions as follows. Consider
$i\in[r]$. For $x\in X$, we have

$v_{i}(w_{x})=\begin{cases}1/(\alpha r-\alpha s+\alpha),&\text{ if }x\in
F_{i}\\\ 0,&\text{ if }x\notin F_{i};\end{cases}$

and $v_{i}(y_{j})=1/(r-s+1)$ for every $j\in[r-s]$.

Now, if $(X,\mathcal{F})$ is a yes-instance, then we have an exact cover
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ for $(X,\mathcal{F})$; and we
define an allocation ${{\pi}:{N}\rightarrow{2^{V(G)}}}$ exactly as in the
proof of Theorem 4.1. We thus have ${|{\pi(i)}|}\leq\alpha$ for every
$i\in[r]$, and hence $\pi$ is $(\alpha,\beta)$-compact. And for every pair of
distinct $i,i^{\prime}\in[r]$, we can verify that $v_{i}(\pi(i))=1/(r-s+1)$
and $v_{i}(\pi(i^{\prime}))\leq 1/(r-s+1)$. Thus every agent is envy-free
under $\pi$.

Conversely, consider a complete, envy-free, $(\alpha,\beta)$-compact
allocation ${{\phi}:{N}\rightarrow{2^{V(G)}}}$. Since $\phi$ is complete,
every item is allocated; in particular, $y_{j}$ is allocated for every
$j\in[r-s]$. Fix $j\in[r-s]$ and let $i^{\prime}\in[r]$ be such that
$y_{j}\in\phi(i^{\prime})$. Then for every agent $i\in[r]$, we have
$v_{i}(\phi(i^{\prime}))\geq 1/(r-s+1)$. But then, since $\phi$ is envy-free,
we must have $v_{i}(\phi(i))\geq 1/(r-s+1)$ as well. Now we consider the set
$R=\\{i\in[r]~{}|~{}\phi(i)\subseteq\\{w_{x}~{}|~{}x\in X\\}\\}$. In
particular, we must have $v_{i}(\phi(i))\geq 1/(r-s+1)$ for every $i\in R$.
And using exactly the same arguments that we used in Theorem 4.1, we can prove
that ${|{R}|}=s$ and $\left\\{{F_{i}~{}|~{}i\in R}\right\\}$ is an exact cover
for $(X,\mathcal{F})$. ∎

In Theorem 4.2, we can replace completeness with Pareto-optimality, and the
reduction would still hold. We thus have the following result.

######  Theorem 4.3.

For every $\alpha\geq 3$ and $\beta\geq 0$, PO-
EF-$({\alpha},{\beta})$-Compact-FD is strongly NP-hard.

###### Proof Sketch.

We use the same reduction as in the proof of Theorem 4.2, and construct the
instance $(G,N,\mathcal{V})$ of PO-EF-$({\alpha},{\beta})$-Compact-FD from a
given instance $(X,\mathcal{F})$ of X$\alpha$C.

Notice that the allocation $\pi$ that we defined in the forward direction of
the proof of Theorem 4.2 is indeed Pareto-optimal. To prove this, it is
sufficient to prove that $\pi$ achieves the maximum utilitarian social
welfare, i.e., $\sum_{i\in N}v_{i}(\pi(i))=\max_{\pi^{\prime}}\sum_{i\in
N}{v_{i}(\pi^{\prime}(i))}$, where the maximum is over all allocations
${{\pi^{\prime}}:{N}\rightarrow{2^{V(G)}}}$. Notice that for each $z\in V(G)$,
if $\pi$ allocates $z$ to agent $i$, then for every agent $i^{\prime}$, we
have $v_{i}(z)\geq v_{i^{\prime}}(z)$. This fact, along with the completeness
of $\pi$ and the additivity of $v_{i}$s, implies that $\pi$ achieves the
maximum utilitarian social welfare. To prove this formally, we can first
verify that $\sum_{i\in N}v_{i}(\pi(i))=(\alpha s)/(\alpha r-\alpha
s+1)+(r-s)/(r-s+1)=r/(r-s+1)$.

Now, for any allocation ${{\pi^{\prime}}:{N}\rightarrow{2^{V(G)}}}$, we have,

$\displaystyle\sum_{i\in N}v_{i}(\pi^{\prime}(i))$
$\displaystyle\leq\sum_{z\in V(G)}\max_{i\in N}v_{i}(z)$
$\displaystyle=\sum_{x\in X}\max_{i\in
N}v_{i}(w_{x})+\sum_{j\in[r-s]}\max_{i\in N}v_{i}(y_{j})$
$\displaystyle=\sum_{x\in X}\frac{1}{\alpha r-\alpha
s+\alpha}+\sum_{j\in[r-s]}\frac{1}{r-s+1}$ $\displaystyle=\frac{\alpha
s}{\alpha r-\alpha s+\alpha}+\frac{r-s}{r-s+1}$
$\displaystyle=\frac{r}{r-s+1}$ $\displaystyle=\sum_{i\in N}v_{i}(\pi(i)),$

which shows that $\pi$ is Pareto-optimal.

For the backward direction, consider a Pareto-optimal, envy-free,
$(\alpha,\beta)$-compact allocation ${{\phi}:{N}\rightarrow{2^{V(G)}}}$.
(Notice that in the proof of Theorem 4.2, we used completeness only to ensure
that $y_{j}$ is allocated (for at least one $j\in[r-s]$) under the allocation
$\phi$. And for this, Pareto-optimality is sufficient.) Every Pareto-optimal
allocation must necessarily be complete, because for every $z\in V(G)$, we
have $v_{i}(z)>0$ for some $i\in[r]$.777We can, in fact, argue that every
Pareto-optimal, $(\alpha,\beta)$-compact allocation $\phi$ must necessarily
allocate $y_{j}$ for some $j\in[r]$. Suppose $\phi$ does not allocate $y_{j}$
for every $j\in[r-s]$. Then $\phi([r])\subseteq\\{w_{x}~{}|~{}x\in X\\}\\}$,
which implies that ${|{\phi([r])}|}\leq\alpha s$. Recall that we are under the
assumption that $r>s$. Since ${|{\phi(i)}|}\leq\alpha$ for every $i\in[r]$,
there exists an agent $p\in[r]$ such that ${|{\phi(p)}|}<\alpha$. We can thus
allocate $y_{1}$ to $p$, (while still ensuring $(\alpha,\beta)$-compactness),
which will increase $p$’s utility by $v_{p}(y_{1})=1/(r-s+1)$. And this
contradicts the assumption that $\phi$ is Pareto-optimal. The rest of the
arguments are identical to that in the proof of Theorem 4.2. ∎

Observe that in each of the reductions in the proofs of Theorems 4.1, 4.2 and
4.3, the graph $G$ that we constructed is edge-less. Thus for $S\subseteq
V(G)$, the subgraph $G[S]$ is $(\alpha,\beta)$-compact if and only if $G[S]$
is _strongly_ $(\alpha,\beta)$-compact. Therefore, even if we replace
compactness with strong compactness in Theorems 4.1, 4.2 and 4.3, the hardness
results would still hold. We thus have the following result.

######  Theorem 4.4.

For every $\alpha\geq 3$ and $\beta\geq 0$, Prop-
Str-$({\alpha},{\beta})$-Compact-FD, Complete EF-
Str-$({\alpha},{\beta})$-Compact-FD and Complete EF-
Str-$({\alpha},{\beta})$-Compact-FD are all strongly NP-hard.

Theorems 4.1-4.4, however, do not cover the case when $\alpha\leq 2$. We
provide a partial answer for this case in Section 4.2. In particular, for the
strongly compact variants, we show that the problems of proportional as well
as envy-free + complete allocations are still NP-hardfor every $\alpha\geq 1$
and $\beta\geq 1$.

######  Lemma 4.5.

For every $\alpha\geq 3$, Exact Cover by $\alpha$-Sets (X$\alpha$C) is NP-
complete.

###### Proof.

Membership in NP is trivial. When $\alpha=3$, the problem is known to be NP-
complete (Karp, 1972). Fix $\alpha>3$. To prove NP-hardness, we reduce from
X3C. Consider an instance $(X,\mathcal{F})$ of X3C, where
$X=\left\\{{x_{1},x_{2},\ldots,x_{3s}}\right\\}$ and
$\mathcal{F}=\left\\{{F_{1},F_{2},\ldots,F_{r}}\right\\}$. Recall that
${|{F_{i}}|}=3$ for every $i\in[r]$. We construct an instance
$(U,\mathcal{A})$ of X$\alpha$C by (i) adding a carefully chosen number of new
elements to $X$, (b) adding $\alpha-3$ of the newly introduced elements to
each $F_{i}\in\mathcal{F}$ and (c) adding all possible $\alpha$-sized subsets
of the newly introduced elements to $\mathcal{F}$. To construct $U$, we add
$3sr\alpha(\alpha-3)-3s$ new elements to $X$. Formally, let
$X^{\prime}=\left\\{{y_{1},y_{2},\ldots,y_{3sr\alpha(\alpha-3)}}\right\\}$
such that $X^{\prime}\cap X=\emptyset$; and we take $U=X\cup X^{\prime}$. Thus
${|{U}|}=3s+3sr\alpha(\alpha-3)-3s=\alpha(\alpha-3)(3sr)$. Let
$\mathcal{F}^{\prime}$ be the family of sets obtained from $\mathcal{F}$ as
follows. For each $i\in[r]$,
$Y_{i}=\\{y_{i(\alpha-3)},y_{i(\alpha-3)-1},y_{i(\alpha-3)-(\alpha-4)}\\}$.
That is, $Y_{1}=\left\\{{y_{1},y_{2},\ldots,y_{\alpha-3}}\right\\}$,
$Y_{2}=\left\\{{y_{(\alpha-3)+1},y_{(\alpha-3)+2},\ldots,y_{2(\alpha-3)}}\right\\}$
and so on. Now, let $F^{\prime}_{i}=F_{i}\cup Y_{i}$ for every $i\in[r]$.
Notice that $F^{\prime}_{i}\subseteq U$ and ${|{F^{\prime}_{i}}|}=\alpha$ for
every $i\in[r]$ and $F^{\prime}_{i}\cap F^{\prime}_{j}=F_{i}\cap F_{j}$ for
every distinct $i,j\in[r]$. Also, let $\mathcal{F}^{\prime}$ be the family of
all $\alpha$-sized subsets of $X^{\prime}$, i.e.,
$\mathcal{F}^{\prime}=\left\\{{Y\subseteq
X^{\prime}~{}|~{}{|{Y}|}=\alpha}\right\\}$. Notice that
${|{\mathcal{F}^{\prime}}|}=\binom{{|{X^{\prime}}|}}{\alpha}=\binom{3sr\alpha(\alpha-3)-3s}{\alpha}=(\alpha
sr)^{\mathcal{O}(\alpha)}$. And we take
$\mathcal{A}=\left\\{{F^{\prime}_{i}~{}|~{}i\in[r]}\right\\}\cup\mathcal{F}^{\prime}$.
Notice that $(U,\mathcal{A})$ can be constructed in polynomial time. We claim
that $(X,\mathcal{F})$ is a yes-instance of X$3$C if and only if
$(U,\mathcal{A})$ is a yes-instance of X$\alpha$C.

Let $\hat{\mathcal{F}}\subseteq\mathcal{F}$ be an exact cover for
$(X,\mathcal{F})$. Let
$\hat{\mathcal{F}_{1}}=\\{F^{\prime}_{i}~{}|~{}F_{i}\in\hat{\mathcal{F}}\\}$.
Notice that ${|{\hat{\mathcal{F}_{1}}}|}={|{\hat{\mathcal{F}}}|}=s$ and that
$F^{\prime}_{i}\cap F^{\prime}_{j}=F_{i}\cap F_{j}=\emptyset$ for every
distinct $F_{i},F_{j}\in\hat{\mathcal{F}}$. Now, let
$Y^{\prime}=\bigcup_{F_{i}\in\hat{\mathcal{F}}}Y_{i}$. Then
${|{Y^{\prime}}|}={|{\hat{\mathcal{F}}}|}\cdot(\alpha-3)=s(\alpha-3)$. And
consider the set $X^{\prime}\setminus Y^{\prime}$. Notice that
${|{X^{\prime}\setminus
Y^{\prime}}|}=3sr\alpha(\alpha-3)-3s-s(\alpha-3)=s(3r\alpha(\alpha-3)-3-\alpha+3)=\alpha
s(3r(\alpha-3)-1)$. Fix a partition $\hat{\mathcal{F}_{2}}$ of
$X^{\prime}\setminus Y^{\prime}$ such that every set in
$\hat{\mathcal{F}_{2}}$ has size exactly $\alpha$. Such a partition
$\hat{\mathcal{F}_{2}}$ has exists as ${|{X^{\prime}\setminus Y^{\prime}}|}$
is a multiple of $\alpha$. Notice that
${|{\hat{\mathcal{F}_{2}}}|}=s(3r(\alpha-3)-1)$ and that that the sets in
$\hat{\mathcal{F}_{2}}$ are pairwise-disjoint. We now define
$\hat{A}=\hat{\mathcal{F}_{1}}\cup\hat{\mathcal{F}_{2}}$. And we have
${|{\hat{\mathcal{A}}}|}={|{\hat{\mathcal{F}_{1}}}|}+{|{\hat{\mathcal{F}_{2}}}|}=s+s(3r(\alpha-3)-1)=(\alpha-3)(3sr)=(1/{\alpha}){|{U}|}$,
and
$\bigcup_{F\in\hat{\mathcal{A}}}F=\left(\bigcup_{F\in\hat{\mathcal{F}_{1}}}F\right)\cup\left(\bigcup_{F\in\hat{\mathcal{F}_{2}}}F\right)=(X\cup
Y^{\prime})\cup(X^{\prime}\setminus Y^{\prime})=U$. Thus $\hat{\mathcal{A}}$
is an exact cover for $(U,\mathcal{A})$.

Conversely, let $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ be an exact cover
for $(U,\mathcal{A})$. Notice that for every set $F\in\mathcal{A}^{\prime}$,
either ${|{F\cap X}|}=0$ or ${|{F\cap X}|}=3$; and if ${|{F\cap X}|}=3$. Since
$\mathcal{A}^{\prime}$ is an exact cover and since ${|{X}|}=3s$, there exist
exactly $s$ sets $F\in\mathcal{A}^{\prime}$ such that ${|{F\cap X}|}=3$. Also,
notice that if ${|{F\cap X}|}=3$, then $F=F^{\prime}_{i}=F_{i}\cup Y_{i}$ for
some $i\in[r]$. Let
$\mathcal{F}_{\mathcal{A}^{\prime}}=\left\\{{F_{i}\in\mathcal{F}~{}|~{}F^{\prime}_{i}\in\mathcal{A}^{\prime}}\right\\}$.
Then $\mathcal{F}_{\mathcal{A}^{\prime}}$ is an exact cover for
$(X,\mathcal{F})$. ∎

###  4.2 Strong NP-Hardness of Strongly $\bm{(\alpha,\beta)}$-Compact FD for
$\bm{\alpha,\beta\geq 1}$

######  Theorem 4.6.

For every fixed $\alpha,\beta\geq 1$, Prop-Str-$({\alpha},{\beta})$-Compact-FD
is strongly NP-hard.

###### Proof.

Fix $\alpha,\beta\geq 1$. We show NP-hardness by a reduction from the
$\beta$-Club problem, in which the input consists of a graph $H$ and a non-
negative integer $k$, and the question is to decide if $H$ has a $\beta$-club
of size exactly $k$. A $\beta$-club in $H$ is a set of vertices $S\subseteq
V(H)$ such that $\text{diam}(H[S])\leq\beta$. So the $\beta$-Club problem asks
if $H$ contains a set of exactly $k$ vertices that induces a subgraph of
diameter at most $k$. This problem is NP-complete (Bourjolly et al.,
2002).888We must note that there are two variants of the $\beta$-Club problem:
the “exact” and the “at least” variants. In the former, the task is to check
if $H$ contains a $\beta$-club of size exactly $k$, whereas in the latter
variant, the task is to check if $H$ contains a $\beta$-club of size at least
$k$. Notice that these two problems are not equivalent. A graph $H$ may
contain a $\beta$-club of size $k+1$, yet no $\beta$-club of size exactly $k$.
For example, take $H$ to be a cycle on $2\beta+1$ vertices and $k=2\beta$.
Bourjolly et al. (2002) shows that the “at least” variant is NP-hard. But
their reduction, in fact, proves the NP-hardness of the “exact” variant as
well.

Consider an instance $(H,k)$ of $\beta$-Club. Let
$V(H)=\left\\{{z_{1},z_{2},\ldots,z_{s}}\right\\}$. We assume without loss of
generality that $1<k<s$, and construct an instance $(G,N,\mathcal{V})$ of
Prop-Str-$({\alpha},{\beta})$-Compact-FD as follows. First, we take $G$ to be
the disjoint union of $H$ and $(\alpha-1)+(s+k-1)$ isolated vertices
$x_{1},x_{2},\ldots,x_{\alpha-1}$ and $y_{1},y_{2},\ldots,y_{s+k-1}$. (Just to
be clear, if $\alpha=1$, then we do not have the vertices
$x_{1},x_{2},\ldots,x_{\alpha-1}$.) That is,
$V(G)=V(H)\cup\left\\{{x_{j}~{}|~{}j\in[\alpha-1]}\right\\}\cup\left\\{{y_{j}~{}|~{}j\in[s+k-1]}\right\\}$,
and $E(G)=E(H)$. And we introduce $2s$ agents: a “special” agent $a^{*}$,
$s-k$ “regular” agents $a^{1},a^{2},\ldots,a^{s-k}$ and $s+k-1$ “dummy” agents
$b^{1},b^{2},\ldots,b^{s+k-1}$. Thus
$N=\left\\{{a^{*}}\right\\}\cup{N}^{\texttt{reg}}\cup{N}^{\texttt{dum}}$,
where ${N}^{\texttt{reg}}=\left\\{{a^{j}~{}|~{}j\in[s-k]}\right\\}$ and
${N}^{\texttt{dum}}=\left\\{{b^{j}~{}|~{}j\in[s+k-1]}\right\\}$. For every
agent $c\in N$, we now define the valuations
${{v_{c}}:{V(G)}\rightarrow{\mathbb{Q}_{\geq 0}}}$ as follows. For every
$i\in[s]$, $j\in[s+k-1]$ and $j^{\prime}\in[\alpha-1]$, we have

$\begin{matrix}{v_{c}(z_{i})=\begin{cases}\frac{1}{2\alpha ks},\text{ if
}c=a^{*}\\\ \frac{1}{2s},\text{ if }c\in{N}^{\texttt{reg}}\\\ 0,\text{ if
}c\in{N}^{\texttt{dum}};\end{cases}}&{v_{c}(y_{j})=\begin{cases}\frac{1}{s+k-1}-\frac{s+\alpha
k-k}{2\alpha ks(s+k-1)},\text{ if }c=a^{*}\\\ \frac{1}{2(s+k-1)},\text{ if
}c\in{N}^{\texttt{reg}}\\\ 1,\text{ if }c=b^{j}\\\ 0,\text{
otherwise;}\end{cases}}&{v_{c}(x_{j^{\prime}})=\begin{cases}\frac{1}{2\alpha
s},\text{ if }c=a^{*}\\\ 0,\text{ if }c\in
N\setminus\left\\{{a^{*}}\right\\}.\end{cases}}\end{matrix}$

We can verify that $v_{c}(V(G))=\sum_{u\in V(G)}v_{c}(u)=1$ for every agent
$c\in N$.

Assume that $(H,k)$ is a yes-instance of $\beta$-Club. Let $Q\subseteq V(H)$
be such that ${|{Q}|}=k$ and $Q$ is a $\beta$-club. Thus
$\text{diam}(H[Q])\leq\beta$. Let us assume without loss of generality that
$Q=\left\\{{z_{s-k+1},z_{s-k+2},\ldots,z_{s}}\right\\}$. And we define an
allocation ${{\pi}:{N}\rightarrow{2^{V(G)}}}$ as follows:
$\pi(a^{*})=Q\cup\left\\{{x_{j}~{}|~{}j\in[\alpha-1]}\right\\}$,
$\pi(a^{i})=z_{i}$ for every $i\in[s-k]$ and $\pi(b^{j})=y_{j}$ for every
$j\in[s+k-1]$. Observe that ${|{\pi(c)}|}=1$ for each agent
$c\in{N}^{\texttt{reg}}\cup{N}^{\texttt{dum}}$, and hence $\pi(c)$ is strongly
$(\alpha,\beta)$-compact. Now, as
$\pi(a^{*})=Q\cup\left\\{{x_{j}~{}|~{}j\in[\alpha-1]}\right\\}$, and
$\text{diam}(G[Q])=\text{diam}(H[Q])\leq\beta$ and
$\text{diam}(G[\left\\{{x_{j}}\right\\}])=0\leq\beta$ for every
$j\in[\alpha-1]$, we can conclude that $\pi(a^{*})$ is strongly
$(\alpha,\beta)$-compact as well. Finally, we have
$v_{a^{*}}(\pi(a^{*}))=\sum_{j=1}^{k}v_{a^{*}}(z_{s-k+j})+\sum_{j^{\prime}=1}^{\alpha-1}v_{a^{*}}(x_{j^{\prime}})=k\cdot(1/(2\alpha
ks))+(\alpha-1)\cdot(1/(2\alpha s))=1/2s$. Also, for every $i\in[s-k]$,
$v_{a^{i}}(\pi(a^{i}))=v_{a^{i}}(z_{i})=1/2s$; and for every $j\in[s-k+1]$,
$v_{b^{j}}(\pi(b^{j}))=v_{b^{j}}(\pi(y_{j}))=1$. Since $v_{c}(\pi(c))\geq
1/2s=1/{|{N}|}$ for every $c\in N$, $\pi$ is proportional.

Conversely, consider a proportional strongly $(\alpha,\beta)$-compact
allocation ${{\phi}:{N}\rightarrow{2^{V(G)}}}$. Then for every agent $c\in N$,
we have $v_{c}(\phi(c))\geq 1/(2s)$. Consider $b^{j}\in{N}^{\texttt{dum}}$.
Since $y_{j}$ is the only item for which $b^{j}$ has a non-zero valuation, we
can conclude that $y_{j}\in\phi(b^{j})$, which implies that
$\phi(\left\\{{a^{*}}\right\\}\cup\left\\{{a^{i}~{}|~{}i\in[s-k]}\right\\})\subseteq\left\\{{z_{1},z_{2},\ldots,z_{s}}\right\\}\cup\left\\{{x_{1},x_{2},\ldots,x_{\alpha-1}}\right\\}$.
We can assume without loss of generality that
$x_{j^{\prime}}\notin\phi(a^{i})$ for every $i\in[s-k]$ and
$j^{\prime}\in[\alpha-1]$; if $x_{j^{\prime}}\in\phi(a^{i})$ for some
$i,j^{\prime}$, then we can simply remove $x_{j^{\prime}}$ from $\phi(a^{i})$.
Since $v_{a^{i}}(x_{j^{\prime}})=0$, the resulting allocation would still be
proportional; and since $x_{j^{\prime}}$ is an isolated vertex, the resulting
allocation would still be $(\alpha,\beta)$-compact. Thus
$\phi(a^{i})\subseteq\left\\{{z_{1},z_{2},\ldots,z_{s}}\right\\}$ for every
$i\in[s-k]$. Therefore, since $\phi$ is proportional and hence
$\phi(a^{i})\neq\emptyset$ for every $i\in[s-k]$, we can conclude that every
agent in $\left\\{{a^{i}~{}|~{}i\in[s-k]}\right\\}$ receives at least one item
from $\left\\{{z_{1},z_{2},\ldots,z_{s}}\right\\}$. In other words, at least
$s-k$ items from $\left\\{{z_{1},z_{2},\ldots,z_{s}}\right\\}$ are allocated
to agents from $\left\\{{a^{i}~{}|~{}i\in[s-k]}\right\\}$. Let
$J=\left\\{{j\in[s]~{}|~{}z_{j}\in\phi(a^{i})\text{ for some
}i\in[s-k]}\right\\}$ and let $J^{*}=[s]\setminus J$. Then ${|{J}|}\geq s-k$,
and hence ${|{J^{*}}|}\leq k$.

We claim that ${|{J^{*}}|}=k$. Suppose not. Notice that
$\phi(a^{*})\subseteq{z_{j}~{}|~{}j\in
J^{*}}\cup\left\\{{x_{j^{\prime}}~{}|~{}j^{\prime}\in[\alpha-1]}\right\\}$.
Hence $v_{a^{*}}(\phi(a^{*}))\leq{|{J^{*}}|}\cdot(1/(2\alpha
ks))+(\alpha-1)\cdot(1/(2\alpha s))<k/(2\alpha ks)+(\alpha-1)/(2\alpha
s)=1/(2s)$. That is, $v_{a^{*}}(\phi(a^{*}))<1/(2s)=1/{|{N}|}$, a
contradiction to the fact that $\pi$ is proportional. Notice also that
$\left\\{{x_{j^{\prime}}~{}|~{}j^{\prime}\in[\alpha-1]}\right\\}\subseteq\phi(a^{*})$,
for otherwise, we would still have $\phi(a^{*})<1/(2s)$. Thus
$\phi(a^{*})=\left\\{{z_{j}~{}|~{}j\in
J^{*}}\right\\}\cup\bigcup_{j^{\prime}=1}^{\alpha-1}\left\\{{x_{j^{\prime}}}\right\\}$.
Since $\phi$ is $(\alpha,\beta)$-compact and since each $x_{j^{\prime}}$ is an
isolated vertex, we must have $\text{dist}_{G[\left\\{{z_{j}~{}|~{}j\in
J^{*}}\right\\}]}(z,z^{\prime})\leq\beta$, for every
$z,z^{\prime}\in\left\\{{z_{j}~{}|~{}j\in J^{*}}\right\\}$. Thus
$\text{diam}(G[\left\\{{z_{j}~{}|~{}j\in J^{*}}\right\\}])\leq\beta$, which
implies that $\text{diam}(H[\left\\{{z_{j}~{}|~{}j\in
J^{*}}\right\\}])\leq\beta$. That is, $\left\\{{z_{j}~{}|~{}j\in
J^{*}}\right\\}$ is a $\beta$-club in $H$, and since ${|{J^{*}}|}=k$, we can
conclude that $(H,k)$ is a yes-instance of $\beta$-Club.

∎

A few modifications to the reduction in the proof of Theorem 4.6 yields the
following result.

######  Theorem 4.7.

For every fixed $\alpha,\beta\geq 1$, Complete EF-
Str-$({\alpha},{\beta})$-Compact-FD is strongly NP-hard.

###### Proof.

We again reduce from $\beta$-Club. Given an instance $(H,k)$ of $\beta$-Club,
where $V(H)=\left\\{{z_{1},z_{2},\ldots,z_{s}}\right\\}$, we proceed as in the
proof of Theorem 4.6, but with the following differences. (1) We assume
without loss of generality that $s+\alpha-1$ is a multiple of $k+\alpha-1$,
i.e., $s+\alpha-1=p(k+\alpha-1)$ for some integer $p$. (Notice that we can
always add isolated vertices to $H$ to ensure this property.) (2) We take $G$
to be the union of $H$ and $p+k+\alpha-1$ isolated vertices
$y_{1},y_{2},\ldots,y_{p}$,
$y^{\prime}_{1},y^{\prime}_{2},\ldots,y^{\prime}_{k}$ and
$x_{1},x_{2},\ldots,x_{\alpha-1}$. (3) We have one special agent $a^{*}$ and a
set of $s$ regular agents ${N}^{\texttt{reg}}=\\{a^{1},a^{2},\ldots,a^{s}\\}$
and a set of $p$ dummy agents
${N}^{\texttt{dum}}=\\{b^{1},b^{2},\ldots,b^{p}\\}$. (4) Finally, we define
the valuation functions. For $c\in N$, $i\in[s]$, $j^{\prime}\in[\alpha-1]$,
we have

$\begin{matrix}{v_{c}(z_{i})=\begin{cases}1/(2(s+\alpha-1)),&\text{ if
}c=a^{*}\\\ 1/(k+1),&\text{ if }c=a^{i}\\\ 0,&\text{ otherwise;
}\end{cases}}&{v_{c}(x_{j^{\prime}})=\begin{cases}1/(2(s+\alpha-1)),&\text{ if
}c=a^{*}\\\ 0,&\text{ otherwise. }\end{cases}}\end{matrix}$

For $c\in N$, $j\in[p]$ and $\ell\in[k]$, we have

$\begin{matrix}{v_{c}(y_{j})=\begin{cases}1/(2p),&\text{ if }c=a^{*}\\\
1,&\text{ if }c=b^{j}\\\ 0,&\text{
otherwise;}\end{cases}}&{v_{c}(y^{\prime}_{\ell})=\begin{cases}{1}/{(k+1)},&\text{
if }c\in{N}^{\texttt{reg}}\\\ 0,&\text{ otherwise.}\end{cases}}\end{matrix}$

We can verify that $\sum_{x\in V(G)}v_{c}(x)=1$ for every agent $c\in N$.
(Recall that $s+\alpha-1=p(k+\alpha-1)$.)

Now, suppose that $H$ contains a $\beta$-club $Q\subseteq V(H)$ of size
exactly $k$. Assume without loss of generality that
$Q=\left\\{{z_{1},z_{2},\ldots,z_{k}}\right\\}$. We define an allocation
${{\pi}:{N}\rightarrow{2^{V(G)}}}$, where
$\pi(a^{*})=Q\cup\left\\{{x_{j^{\prime}}~{}|~{}j^{\prime}\in[\alpha-1]}\right\\}$;
for $i\in[s]$, $\pi(a^{i})=z_{i}$ if $i>k$ and $\pi(a^{i})=y^{\prime}_{i}$ if
$i\leq k$; and for $j\in[p]$, $\pi(b^{j})=y_{j}$. Since $Q$ is a $\beta$-club
in $H$ and hence in $G$ as $G[Q]=H[Q]$, we have, $\text{diam}(G[Q])\leq\beta$;
and since $\pi(a^{*})$ is the disjoint of $Q$ and $\alpha-1$ vertices,
$G[\pi(a^{*})]$ is strongly $(\alpha,\beta)$-compact. Also, since
${|{\pi(c)}|}=1$ for every agent $c\in N\setminus\left\\{{a^{*}}\right\\}$,
$G[\pi(c)]$ is strongly $(\alpha,\beta)$-compact as well. To see that $\pi$ is
an envy-free allocation, observe the following facts.

  1. 1.

The agent $a^{*}$ is envy-free.

    1. (a)

We have
$v_{a^{*}}(\pi(a^{*}))=\sum_{i=1}^{k}v_{a^{*}}(z_{i})+\sum_{j^{\prime}=1}^{\alpha-1}=k\cdot(1/(2(s+\alpha-1)))+(\alpha-1)\cdot(1/(2(s+\alpha-1)))=(k+\alpha-1)/(2(s+\alpha-1))=1/(2p)$.
The last equality follows from the fact that $s+\alpha-1=p(k+\alpha-1)$.

    2. (b)

For $i\in[s]$ with $i>k$, we have
$v_{a^{*}}(\pi(a^{i}))=v_{a^{*}}(z_{i})=1/(2(s+\alpha-1))<1/(2p)$.

    3. (c)

And for $i\in[s]$ with $i\leq k$, we have
$v_{a^{*}}(\pi(a^{i}))=v_{a^{*}}(y^{\prime}_{i})=0$ if $i\leq k$.

    4. (d)

For $j\in[p]$, $v_{a^{*}}(\pi(b^{j}))=v_{a^{*}}(y_{j})=1/(2p)$.

  2. 2.

For every $j\in[p]$, $b^{j}$ is envy-free as we have
$v_{b^{j}}(\pi(b^{j}))=v_{b^{j}}(y_{j})=1$ and $v_{b^{j}}(\pi(c))\leq 1$ for
every agent $c\in N$.

  3. 3.

For every $i\in[s]$, $a^{i}$ is envy-free.

    1. (a)

First, $v_{a^{i}}(\pi(a^{i}))=v_{a^{i}}(\pi(z_{i}))=1/(k+1)$ if $i>k$ and
$v_{a^{i}}(\pi(a^{i}))=v_{a^{i}}(\pi(y^{\prime}_{i}))=1/(k+1)$ if $i\leq k$.

    2. (b)

And
$v_{a^{i}}(\pi(a^{*}))=v_{a^{i}}(Q\cup\left\\{{x_{j^{\prime}}~{}|~{}j^{\prime}\in[\alpha-1]}\right\\})=\sum_{j=1}^{k}v_{a^{i}}(z_{j})+\sum_{j^{\prime}=1}^{\alpha-1}v_{a^{i}}(x_{j^{\prime}})$
Now, $v_{a^{i}}(x_{j^{\prime}})=0$ for every $j^{\prime}\in[\alpha-1]$. Notice
also that $\sum_{j=1}^{k}v_{a^{i}}(z_{j})=1/(k+1)$ if $i\leq[k]$ (as
$v_{a^{i}}(z_{i})=1/(k+1)$) and $\sum_{j=1}^{k}v_{a^{i}}(z_{j})=0$ if $i>k$.
In either case, $v_{a^{i}}(\pi(a^{*}))\leq 1/(k+1)=v_{a^{i}}(\pi(a^{i}))$.

    3. (c)

For distinct $i,j\in[s]$, $v_{a^{i}}(\pi(a^{j}))\leq 1/(k+1)$.

    4. (d)

For $i\in[s]$ and $j\in[p]$, $v_{a^{i}}(\pi(b^{j}))=v_{a^{i}}(y_{j})=0$.

Conversely, consider a complete, envy-free and strongly
$(\alpha,\beta)$-compact allocation ${{\phi}:{N}\rightarrow{2^{V(G)}}}$. Since
$\phi$ is complete, for every $\ell\in[k]$, the vertex $y^{\prime}_{\ell}$ is
allocated. But notice that $v_{a^{i}}(y^{\prime}_{\ell})=1/(k+1)$ for every
$i\in[s]$. Then, since $\phi$ is envy-free, we must have
$v_{a^{i}}(\phi(a^{i}))\geq 1/(k+1)$ for every $i\in[s]$. But notice that the
agent $a^{i}$ has non-zero valuations only for the vertex $z_{i}$ and the $k$
vertices $y^{\prime}_{1},\ldots,y^{\prime}_{k}$. Therefore, for every
$i\in[s]$, either $z_{i}\in\phi(a^{i})$ or $y^{\prime}_{\ell}\in\phi(a^{i})$
for some $\ell\in[k]$. Let $S=\left\\{{z_{i}\in
V(G)~{}|~{}z_{i}\in\phi(a^{i})}\right\\}$. Notice that ${|{S}|}\geq s-k$ as
there exist at most $k$ agents $a^{i}$ with $y^{\prime}_{\ell}\in\phi(a^{i})$
for some $\ell\in[k]$. Now, since $\phi$ is complete and envy-free and since
$v_{b^{j}}(y_{j})=1$ for every $j\in[p]$, we must have $y_{j}\in\phi(b^{j})$.
But notice that $v_{a^{*}}(\phi(b^{j}))\geq v_{a^{*}}(y_{j})=1/(2p)$. Since
$\phi$ is envy-free, we must have $v_{a^{*}}(\phi(a^{*}))\geq
v_{a^{*}}(\phi(b^{j}))\geq 1/(2p)$. Let $R=\left\\{{z_{i}|~{}i\in[s]\text{ and
}z_{i}\in\phi(a^{*})}\right\\}$. First, notice that
$R\subseteq\left\\{{z_{1},z_{2},\ldots,z_{s}}\right\\}\setminus S$. Then,
since ${|{S}|}\geq s-k$, we have ${|{R}|}\leq k$. Let us first observe that
${|{R}|}=k$. Suppose not. Then, $v_{a^{*}}(\phi(a^{*}))\leq
v_{a^{*}}(R)+v_{a^{*}}(\left\\{{x_{j^{\prime}}~{}|~{}j^{\prime}\in[\alpha-1]}\right\\})={|{R}|}\cdot(1/(2(s+\alpha-1)))+(\alpha-1)\cdot(1/(s+\alpha-1))<(k+\alpha-1)/(2(s+\alpha-1))=1/(2p)$.
That is, $v_{a^{*}}(\phi(a^{*}))<1/(2p)$, which is not possible as the agent
$a^{*}$ is envy-free. Thus ${|{R}|}=k$. Now, notice also that
$x_{j^{\prime}}\in\phi(a^{*})$ for every $j^{\prime}\in[\alpha-1]$, for
otherwise, we would still have $v_{a^{*}}(\phi(a^{*}))<1/(2p)$. Thus
$\phi(a^{*})$ contains $R$ and $\alpha-1$ isolated vertices
$x_{1},x_{2},\ldots,x_{\alpha-1}$. Then, since $\phi$ is
$(\alpha,\beta)$-compact, we can conclude that
$\text{dist}_{G[R]}(z,z^{\prime})\leq\beta$ for every $z,z^{\prime}\in R$.
Therefore, $\text{diam}(G[R])\leq\beta$, which implies that
$\text{diam}(H[R])\leq\beta$. Thus $R$ is a $\beta$-club of size $k$ in $H$. ∎

##  5 Proportional (Strongly) $(1,\beta)$-Compact Allocations on Paths

In this section, we consider we consider Prop-$({1},{\beta})$-Compact-FD and
Prop-Str-$({1},{\beta})$-Compact-FD in a highly restricted input setting: The
graph $G$ on the set of items is a path. We show that these problems admit FPT
algorithms when parameterized by the number of agents, and XP algorithms when
parameterized by the number of types of agents. We first observe the following
fact.

######  Observation 5.1.

Fix $\beta\geq 0$. A path $P$ is $(1,\beta)$-compact if and only if $P$ has at
most $2\beta+1$ vertices. And $P$ is strongly $(\alpha,\beta)$-compact if and
only if $P$ has at most $\beta+1$ vertices.

We now design a dynamic programming algorithm for
Prop-$({1},{\beta})$-Compact-FD. The algorithm for Prop-
Str-$({1},{\beta})$-Compact-FD only requires a slight adaptation. In the
remaining part of this section, we assume that we are given a instance
$(G,N,\mathcal{V})$ of Prop-$({1},{\beta})$-Compact-FD, where $G$ is a path
with $V(G)=\left\\{{z_{1},z_{2},\ldots,z_{m}}\right\\}$ and
$E(G)=\\{z_{i}z_{i+1}~{}|~{}i\in[m-1]\\}$. For $p,q\in[m]$ with $p\leq q$, let
$V_{p,q}=\left\\{{z_{p},z_{p+1},\ldots,z_{q}}\right\\}$ and
$G_{p,q}=G[V_{p,q}]$.

We now describe our DP. For each $i,j\in[m]$ with $j\leq i$ and for each non-
empty $N^{\prime}\subseteq N$, we define $A_{\texttt{co}}[i,j,N^{\prime}]=1$
if there exists a $(1,\beta)$-compact, proportional allocation
${{\pi}:{N^{\prime}}\rightarrow{2^{V(G_{1,i})}}}$ such that no item that
appears after $z_{j}$ in the ordering $z_{1},z_{2},\ldots,z_{i}$ is allocated
under $\pi$; and $A_{\texttt{co}}[i,j,N^{\prime}]=0$, otherwise. That is,
$A_{\texttt{co}}[i,j,N^{\prime}]=1$ if each agent in $N^{\prime}$ receives a
proportional, $(1,\beta)$-compact bundle and no $z_{j^{\prime}}$, where
$j^{\prime}>j$, gets allocated. Notice then that $(G,N,\mathcal{V})$ is a yes-
instance of Prop-$({1},{\beta})$-Compact-FD if and only if
$A_{\texttt{co}}[m,j,N]=1$ for some $j\in[m]$. To compute the entries, we use
the recurrence

$A_{\texttt{co}}[i,j,N^{\prime}]=\bigvee_{\begin{subarray}{c}{(i^{\prime},j^{\prime},a)}\\\
{i^{\prime}\leq j}\\\ {j^{\prime}\leq i^{\prime}}\\\ {a\in N^{\prime}}\\\
{{|{V_{j^{\prime}+1,i^{\prime}}}|}\leq 2\beta+1}\\\
{v_{a}(V_{j^{\prime}+1,i^{\prime}})\geq(1/{n})\cdot
v_{a}(V(G))}\end{subarray}}A_{\texttt{co}}[i^{\prime},j^{\prime},N^{\prime}\setminus\left\\{{a}\right\\}].$

Notice that the recurrence 5 simply checks if it is feasible to allocate all
the vertices from $z_{j^{\prime}+1}$ to $z_{i^{\prime}}$ to some agent $a\in
N^{\prime}$, while ensuring compactness and proportionality for every agent in
$N^{\prime}$. The condition ${|{V_{j^{\prime}+1,i^{\prime}}}|}\leq 2\beta+1$
ensures that the allocation remains $(1,\beta)$-compact, and the condition
$v_{a}(V_{j^{\prime}+1,i^{\prime}})\geq 1/{n}\cdot v_{a}(V(G))$ ensures
proportionality. The base case of the recurrence is when
$i=j={|{N^{\prime}}|}=1$. And for this case, notice that we have
$A[1,1,\left\\{{a}\right\\}]=1$ if and only if the allocation $\pi$ that
allocates the vertex $z_{1}$ to agent $a$ is proportional, i.e., if and only
if $v_{a}(z_{1})\geq(1/n)\cdot v_{a}(V(G))$. So for every $a\in N$, we set
$A[1,1,\left\\{{a}\right\\}]=1$ if $v_{a}(z_{1})\geq 1/n$, and set
$A[1,1,\left\\{{a}\right\\}]=0$ otherwise. Finally, notice that the number of
choices for $(i,j,N^{\prime})$ is $m^{2}\cdot 2^{n}$, and that the time taken
to compute each $A[i,j,N]$ is bounded by the number of choices for
$(i^{\prime},j^{\prime},a)$, which is at most $m^{2}\cdot n$. Thus the total
time taken by the algorithm is $\mathcal{O}(2^{n}\cdot n\cdot m^{4})$.

######  Remark 5.2.

Observe the following two facts. (1) The DP does not require that the
valuations be additive. (2) By slightly modifying the definition of
$A_{\texttt{co}}$, we can solve Prop-Str-$({1},{\beta})$-Compact-FD as well.
We define $A_{\texttt{sco}}[i,j,N^{\prime}]=1$ if there exists a strongly
$(1,\beta)$-compact, proportional allocation
${{\pi}:{N^{\prime}}\rightarrow{2^{V(G_{1,i})}}}$ such that no item that
appears after $z_{j}$ in the ordering $z_{1},z_{2},\ldots,z_{i}$ is allocated
under $\pi$; and $A_{\texttt{sco}}[i,j,N^{\prime}]=0$, otherwise. And we can
compute $A_{\texttt{sco}}[i,j,N^{\prime}]$ using a similar recurrence
relation. In light of Observation 5.1, we just need to replace the condition
${|{V_{j^{\prime}+1,i^{\prime}}}|}\leq 2\beta+1$ in 5 with
${|{V_{j^{\prime}+1,i^{\prime}}}|}\leq\beta+1$.

We summarise the discussion so far in this section in the following theorem.

######  Theorem 5.3.

Prop-$({1},{\beta})$-Compact-FD and Prop-Str-$({1},{\beta})$-Compact-FD are
FPT when parameterized by the number of agents. These results hold even when
the valuations are not additive.

Now, notice that if the agents’ valuations are identical, then we need not
keep track of the set $N^{\prime}$ of agents who have already received a
proportional and compact bundle of items. We simply need to remember _how
many_ agents have received bundles so far. That is, instead of going over all
tuples $(i,j,N^{\prime})$, we only need to consider tuples $(i,j,n^{\prime})$,
where $0\leq n^{\prime}\leq n$. And we can define and compute
$A_{\texttt{co}}[i,j,n^{\prime}]$ and $A_{\texttt{sco}}[i,j,n^{\prime}]$
accordingly. Thus instead of exponential dependence on the number of agents,
the algorithm now will only have a polynomial dependence on the number of
agents.

We can generalise the above idea further to design an XP algorithm
parameterized by the number of types of agents. We say that two agents
$a,a^{\prime}\in N$ are of the same type if their valuations are identical.
Let $p$ be the number of distinct types of agents, and let the types be
numbered from $1$ to $p$. Also for each $q\in[p]$, let $n_{q}$ be the number
of agents of type $q$ and let $v_{q}$ denote the valuation function
corresponding to an agent of type $j$. To design our algorithm, as before, we
process the graph from $z_{1}$ to $z_{m}$, and at every stage and for each
type $q\in[p]$, we keep track of the number of agents of type $q$ who received
bundles. Formally, for each $i,j\in[m]$, and each tuple
$(\ell_{1},\ell_{2},\ldots,\ell_{p})$, where $0\leq\ell_{q}\leq n_{q}$ for
every $q\in[p]$, we define
$A^{\prime}_{\texttt{co}}[i,j,(\ell_{1},\ell_{2},\ldots,\ell{p})]=1$ if there
exists a $(1,\beta)$-compact, proportional allocation
${{\pi}:{N}\rightarrow{2^{V(G_{1,i})}}}$ such that no item that appears after
$z_{j}$ in the ordering $z_{1},z_{2},\ldots,z_{i}$ is allocated under $\pi$,
and for each $q\in[p]$, exactly $\ell_{q}$ agents of type $q$ have received
bundles under $\pi$; and
$A^{\prime}_{\texttt{co}}[i,j,(\ell_{1},\ell_{2},\ldots,\ell{p})]=0$,
otherwise. Notice that $(G,N,\mathcal{V})$ admits a proportional,
$(1,\beta)$-compact allocation if and only if
$A^{\prime}_{\texttt{co}}[m,j,(n_{1},n_{2},\ldots,n_{p})]=1$ for some
$j\in[m]$.

For each $p$-tuple $(\ell_{1},\ell_{2},\ldots,\ell{p})$ and for each $q\in[p]$
with $\ell_{q}>0$, let $\ell^{q}_{r}=\ell_{r}$ if
$r\in[p]\setminus\left\\{{q}\right\\}$ and $\ell^{q}_{q}=\ell_{q}-1$. Now, to
compute $A^{\prime}_{\texttt{co}}[i,j,(\ell_{1},\ell_{2},\ldots,\ell_{p})]$,
we have the recurrence

$A^{\prime}_{\texttt{co}}[i,j,(\ell_{1},\ell_{2},\ldots,\ell_{p})]=\bigvee_{\begin{subarray}{c}{(i^{\prime},j^{\prime},q)}\\\
{i^{\prime}\leq j}\\\ {j^{\prime}\leq i^{\prime}}\\\ {q\in[p]}\\\
\ell_{q}>0\\\ {{|{V_{j^{\prime}+1,i^{\prime}}}|}\leq 2\beta+1}\\\
{v_{q}(V_{j^{\prime}+1,i^{\prime}})\geq(1/{n})\cdot
v_{q}(V(G))}\end{subarray}}A^{\prime}_{\texttt{co}}[i,j,(\ell^{q}_{1},\ell^{q}_{2},\ldots,\ell^{q}_{p})].$

For the base case of the recurrence, for every $i,j\in[m]$, we set
$A^{\prime}_{\texttt{co}}[i,j,(0,0,\ldots,0)]=1$; notice that in this case,
the empty allocation trivially satisfies all the required conditions. Also,
for each $q\in[p]$, let $\overline{1}_{q}$ denote the $p$-tuple
$(\ell_{1},\ell_{2},\ldots,\ell_{p})$, where $\ell_{r}=0$ if
$r\in[p]\setminus\left\\{{q}\right\\}$ and $\ell_{q}=1$. And we set
$A^{\prime}_{\texttt{co}}[1,1,\overline{1}_{q}]=1$ if
$v_{q}(z_{1})\geq(1/n)\cdot v_{q}(V(G))$.

Notice that the number of choices for the tuple
$(i,j,(\ell_{1},\ell_{2},\ldots,\ell_{p}))$ is at most $m^{2}\cdot n^{p}$. And
notice that to compute each
$A^{\prime}_{\texttt{co}}[i,j,(\ell_{1},\ell_{2},\ldots,\ell_{p})]$, we only
need to go over the entries
$A^{\prime}_{\texttt{co}}[i^{\prime},j^{\prime},(\ell^{q}_{1},\ell^{q}_{2},\ldots,\ell^{q}_{p})]$
for all triplets $(i^{\prime},j^{\prime},q)$, and the number of choices for
such triplets is at most $m^{2}\cdot p$. Hence the total runtime of the
algorithm is bounded by $\mathcal{O}(p\cdot n^{p}\cdot m^{4})$. Again, we can
solve the strongly compact variant by slightly modifying the DP. We thus have
the following result.

######  Theorem 5.4.

Prop-$({1},{\beta})$-Compact-FD and Prop-Str-$({1},{\beta})$-Compact-FD admit
XP algorithms parameterized by the number of types of agents. These results
hold even when the valuations are not additive.

######  Remark 5.5.

The fact that $\alpha=1$ is crucial for the results in this section. We cannot
generalise our strategy here to $\alpha>1$. Suppose $\alpha>1$. It might be
tempting to try and remember which subset of agents $N^{\prime}\subseteq N$
have received bundles so far, and how many connected pieces each of them
received. So, along with $i,j$, we would keep track of
$(N_{0},N_{1},N_{2},\ldots,N_{\alpha})$, where for each $\ell\in[\alpha]$,
$N_{\ell}$ is the set of agents who received exactly $\ell$ many connected
pieces of the path. But this information alone is inadequate. We would also
need to remember the valuation of each agent for the set of items she has
received so far.

##  6 Fair Division of Graphs of Bounded Treewidth

In this section, we show that for each of the three fairness
concepts—proportionality, envy-freeness and maximin fairness—the corresponding
problem of checking if there exists an allocation that is fair and
$(\alpha,\beta)$ compact admits a pseudo-XP algorithm, when parameterized by
the treewidth of the item graph and the number of agents. We design a single
dynamic programming procedure that works for all three fairness concepts. We
assume in this section that the valuations are _integer-valued_. Throughout
this section, we will use terminology and results from Sections 2, 3.4 and
3.5. We encourage the reader to have a quick look at these sections before
reading any further. The following theorem is the main contribution of this
section.

######  Theorem 6.1.

For every $\alpha$ and $\beta$, Prop-$({\alpha},{\beta})$-Compact-FD,
EF-$({\alpha},{\beta})$-Compact-FD and MMS-$({\alpha},{\beta})$-Compact-FD
admit algorithms that run in time $({\sf tw}+n)^{\mathcal{O}({\sf
tw}+n)}\cdot\beta^{{\sf tw}}\cdot m^{\mathcal{O}(\alpha n)}\cdot
W^{\mathcal{O}(n^{2})}$, where ${\sf tw}$ is the treewidth of the input graph
$G$ and $W$ is the maximum valuation of an agent for $G$, i.e., $W=\max_{i\in
N}v_{i}(V(G))$.

As an immediate corollary of Theorem 6.1, we derive the following result.

######  Theorem 6.2.

For every $\alpha$ and $\beta$, Prop-$({\alpha},{\beta})$-Compact-FD,
EF-$({\alpha},{\beta})$-Compact-FD and MMS-$({\alpha},{\beta})$-Compact-FD
admit algorithms that run in time $(\alpha\beta n)^{\mathcal{O}(\alpha\beta
n)}\cdot\beta^{\alpha\beta n}\cdot m^{\mathcal{O}(\alpha n)}\cdot
W^{\mathcal{O}(n^{2})}$ when the item graph $G$ is planar.

###### Proof.

To prove the theorem, we use the following facts. (1) For a planar graph $G$,
${\sf tw}(G)=\mathcal{O}(D)$, where $D$ is diameter of $G$ (see, for example,
Eppstein (2000)). (2) For a graph $G$, ${\sf tw}(G)=\max_{H}{\sf tw}(H)$,
where the maximum is over all connected components $H$ of $G$. (3) Given an
instance $(G,N,\mathcal{V})$ of $[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-
FD, by Remark 3.10, we can assume without loss of generality that
$\text{diam}(H)=\mathcal{O}(\alpha\beta n)$ for every connected component $H$
of $G$. Facts (1), (2) and (3) together imply that for an instance
$(G,N,\mathcal{V})$ of $[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD, we have
${\sf tw}(G)=\mathcal{O}(n\alpha\beta)$ if $G$ is planar. The theorem then
follows immediately from Theorem 6.1. ∎

We now prove Theorem 6.1. In light of Lemma 3.9, to solve
$[\mathtt{X}]$-$({\alpha},{\beta})$-Compact-FD, it is enough to solve
$[\mathtt{X}]$-Annotated-FD, for which we design an algorithm. More precisely,
we prove the following lemma.

######  Lemma 6.3.

There is an algorithm that, given an instance
$(G,[n],\mathcal{V},\beta,(\hat{z}_{i})_{i\in[n]})$ of Annotated-FD, an
$n^{2}$ tuple $(\hat{w}_{ij})_{i,j\in[n]}$, where $0\leq w_{ij}\leq W$ for
every $i,j\in[n]$ and a nice tree decomposition $(T,\\{X_{t}~{}|~{}t\in
V(T)\\})$ of $G$ as input, runs in time $({\sf tw}+n)^{\mathcal{O}({\sf
tw}+n)}\cdot\beta^{\mathcal{O}({\sf tw}+n)}\cdot m^{\mathcal{O}(1)}\cdot
W^{\mathcal{O}(n^{2})}$, and correctly decides if
$(G,[n],\mathcal{V},\beta,(\hat{z}_{i})_{i\in[n]}))$ admits a
$((\hat{z}_{i})_{i\in[n]};\beta)$-annotated allocation
${{\pi}:{[n]}\rightarrow{2^{V(G)}}}$ such that $v_{i}(\pi(j))=\hat{w}_{ij}$
for each $i,j\in[n]$.

The rest of this section is dedicated to proving Lemma 6.3. And for that, we
design a dynamic programming algorithm over a (nice) tree decomposition of
$G$. From now on, we assume that we are given
$(G,[n],\mathcal{V},\beta,(\hat{z}_{i})_{i\in[n]})$, an $n^{2}$ tuple
$(\hat{w}_{ij})_{i,j\in[n]}$, where $0\leq w_{ij}\leq W$ for every $i,j\in[n]$
and a nice tree decomposition $(T,\\{X_{t}~{}|~{}t\in V(T)\\})$ of $G$ of
width ${\sf tw}$. We first add $\bm{\hat{z}_{i}}$ for every $\bm{i\in[n]}$, to
every bag $\bm{X_{t}}$ (and denote the resulting tree decomposition by
$(T,\\{X_{t}~{}|~{}t\in V(T)\\})$ as well). Notice that this increases the
width of the tree decomposition by $n$; and $(T,\\{X_{t}~{}|~{}t\in V(T)\\})$
still remains a nice tree decomposition but for the fact that the bags
corresponding to the root node and the leaf nodes of $T$ are non-empty. In
particular, for $t\in V(T)$, where $t$ is a leaf node or $t$ is the root of
$T$, we have
$X_{t}=\left\\{{\hat{z}_{1},\hat{z}_{2},\ldots,\hat{z}_{n}}\right\\}$.
Following standard convention, for $t\in V(T)$, we use $G_{t}$ to denote the
subgraph of $G$ that consists of all the vertices and edges introduced in the
subtree rooted at $t$.

##### Outline of our algorithm.

Suppose that $\pi$ is the $((\hat{z}_{i})_{i\in[n]};\beta)$-annotated
allocation that we are looking for. Then for each $i\in[n]$ and for each
$z\in\pi(i)$, $\text{dist}_{G[\pi(i)]}(\hat{z}_{i},z)\leq\beta$. Let $H_{i}$
be a BFS tree of $G[\pi(i)]$, rooted at $\hat{z}_{i}$. Since $H_{i}$ is a BFS
tree rooted at $\hat{z}_{i}$, we have
$\text{dist}_{G[\pi(i)]}(\hat{z}_{i},z)=\text{dist}_{H_{i}}(\hat{z}_{i},z)$
for every $z\in\pi(i)$. For a node $t\in V(T)$, we guess how $H_{i}$
intersects with the graph $G_{t}$. Notice that $H_{i}$ is an acyclic graph and
it could possibly split into multiple connected components when intersected
with $G_{t}$. With this in mind, we guess the following features of the
intersection of $H_{i}$ with $G_{t}$: (a) the intersection of
$V(H_{i})(=\pi(i))$ with $X_{t}$, (b) how $H_{i}$ partitions the vertices of
$X_{t}\cap\pi(i)$ into connected components (c) for each $z\in
X_{t}\cap\pi(i)$, the distance in $H_{i}$ between $z$ and $\hat{z}_{i}$ and
(4) agent $i$’s valuations for the subsets of goods in $G_{t}$ that have been
allocated to herself as well as the other agents, i.e., $v_{i}(\pi(j)\cap
V(G_{t}))$ for every $i,j\in[n]$. We argue that these four pieces of
information are sufficient to design a dynamic programming algorithm that
constructs $\pi$ in a bottom up fashion over $T$.

##### Designing the DP: Necessary Ingredients.

To design our DP, for each node $t\in V(T)$, we first define a set
$\mathcal{C}_{t}$, (which formalises our guesses). Formally, for each $t\in
V(T)$, let $\mathcal{C}_{t}$ be the set of all tuples
$((S_{i},f_{i},(\mathcal{P}_{i},R_{i}))_{i\in[n]},(w_{ij})_{i,j\in[n]})$ with
the following properties.

  * •

For each $i\in[n]$, $S_{i}$ is a vertex subset such that $\hat{z}_{i}\in
S_{i}$ and $S_{i}\subseteq X_{t}\cap B_{G}(\hat{z}_{i},\beta)$ and $S_{i}\cap
S_{j}=\emptyset$ for every $j\in[n]\setminus\left\\{{i}\right\\}$.

  * •

For each $i\in[n]$, $(\mathcal{P}_{i},R_{i})$ is a rooted partition of $S_{i}$
such that $\hat{z}_{i}\in R_{i}$.

  * •

For each $i\in[n]$, ${{f_{i}}:{S_{i}}\rightarrow{[\beta]_{0}}}$ is a function
such that $f_{i}(\hat{z}_{i})=0$ and $f_{i}(z)\neq 0$ for every $z\in
S_{i}\setminus\left\\{{\hat{z}_{i}}\right\\}$.

  * •

The tuple $(w_{ij})_{i,j\in[n]}$ is an $n^{2}$-tuple of non-negative integers
such that $0\leq w_{ij}\leq W$ for every $i,j\in[n]$.

For example, when $n=2$, the set $\mathcal{C}_{t}$ consists of all tuples of
the form
$((S_{1},f_{1},(\mathcal{P}_{1},R_{1})),(S_{2},f_{2},(\mathcal{P}_{2},R_{2})),(w_{11},w_{12},w_{21},w_{22}))$.
We now bound ${|{\mathcal{C}_{t}}|}$.

######  Observation 6.4.

For each $t\in V(T)$, we have ${|{\mathcal{C}}|}_{t}\leq({\sf