# The Complexity of Envy-Free Graph Cutting

Argyrios Deligkas1 Eduard Eiben1 Robert Ganian2 Thekla Hamm3 Sebastian
Ordyniak4 1Royal Holloway, University of London, UK
2TU Wien, Austria
3Eindhoven University of Technology, the Netherlands
4University of Leeds, UK
<EMAIL_ADDRESS>{rganian,
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of fairly dividing a set of heterogeneous divisible
resources among agents with different preferences. We focus on the setting
where the resources correspond to the edges of a connected graph, every agent
must be assigned a connected piece of this graph, and the fairness notion
considered is the classical envy freeness. The problem is NP-complete, and we
analyze its complexity with respect to two natural complexity measures: the
number of agents and the number of edges in the graph. While the problem
remains NP-hard even for instances with 2 agents, we provide a dichotomy
characterizing the complexity of the problem when the number of agents is
constant based on structural properties of the graph. For the latter case, we
design a polynomial-time algorithm when the graph has a constant number of
edges.

##  1 Introduction

Cake cutting is, without a doubt, among the most influential problems in
social choice and has received significant attention in computer science,
mathematics, and economics Brams and Taylor (1996); Robertson and Webb (1998);
Moulin (2004); Procaccia (2013). The cake corresponds to a heterogeneous
divisible resource that is to be divided between a set of $n$ agents with
different preferences in a “fair” manner. In this paper, the fairness concept
we focus on is envy-freeness, where every agent prefers the piece of the cake
they get allocated over the piece any other agent gets.

In the classical formulation of the problem, the cake is represented as an
interval and the preference of every agent over the cake is given via a
valuation over any subinterval of the cake. In this setting, Dubins and
Spanier (1961) showed that an envy-free allocation always exists for arbitrary
valuations for the agents, where the piece an agent gets consists of a
countable number of subintervals. Stromquist (1980) strengthened this result
by removing the possibility of pieces that consist of a “union of crumbs”. In
fact, he showed that there is an envy-free allocation where the piece of every
agent is contiguous, i.e., it is a single subinterval.

Recently, Bei and Suksompong (2021) considered a generalized version cake
cutting on graphs. This augmented model allows to capture more general
scenarios which cannot be represented by splitting an interval into connected
pieces—consider, e.g., the task of splitting road or railway networks between
companies. We note that these settings do not always give rise to large
graphs: for instance, the ICE train network in Germany can be modeled as a
graph with merely 23 edges. Or, for yet another example, suppose that one
wants to schedule time on a high-performance computing cluster between teams
(agents). Suppose furthermore that the day is partitioned into, e.g., four
time-slots, with each time-slot being less or more desirable for different
agents. This setting, too, can easily be modeled using a graph with four
edges. In these as well as other examples, it is still desirable to ensure
that each agent receives a connected piece of the graph, but the natural model
for the cake is a graph where each individual edge may be split and behaves as
a single, uniform piece.

Observe that depending on the setting, it may either be the case that a vertex
is allocated to only a single agent (as in the case of junctions in the
division of road networks over maintenance companies), or that a vertex merely
acts as a bridge between edges and may be used by multiple agents (as in the
case of train stations in division of railway networks over rail companies).
We call the former setting “graph cutting” and the latter “vertex-disjoint
graph cutting”.

While both fair division problems always admit a contiguous envy free solution
when the underlying graph is a path (since they are special cases of the
classical cake cutting problem), this is no longer true for more general
graphs. In fact, it is not hard to construct graphs with no envy-free
solutions; this holds even for stars with three leafs and two agents with
identical valuations. Hence, in the setting studied here, the natural task is
to decide if a solution exists, and if it does to efficiently compute one.

Our Contributions. In this work, we explore the frontiers of tractability for
both variants of graph cutting under the envy free solution concept; we refer
to these problems as EF-GC and EF-VDGC, respectively. While it is not
difficult to show that both problems are -complete in general, here we analyze
the problem with respect to two of the most natural complexity measures that
characterize the input: the number of agents and the number of edges.

When considering the number of agents (i.e., $n$), we begin by extending the
-completeness lower bounds for both variants to the case of $n=2$ even on very
simple graphs—as simple as two vertices plus a matching (Theorem 4). However,
here we can show that the two variants do sometimes behave differently: while
EF-GC is also -hard on stars when $n=2$ (Theorem 3), we design a polynomial-
time algorithm for EF-VDGC on trees when $n$ is upper-bounded by an arbitrary
but fixed constant (Theorem 7). In order to achieve tractability for EF-GC, we
need to restrict ourselves to instances with a constant number of agents and
where the graph is a tree with a constant maximum degree (Theorem 8).

tw | $\Delta$ | EF-GC | EF-VDGC
---|---|---|---
2 | 3 |  -c (Th. 5) |  -c (Th. 5)
2 | 2 | ¶ (Th. 9) | ¶ (Th. 9)
1 | arbitrary |  -c (Th. 3) | ¶ (Th. 7)
1 | constant | ¶(Th. 8) | ¶ (Th. 7)
Table 1: Complexity of EF-GC and EF-VDGC for a constant number of agents for
different restrictions on the treewidth (tw) and the maximum degree
($\Delta$). All -completeness (-c) results hold already for only 2 agents.

In fact, we prove this is the best one can do from this perspective. Both
problems become -hard on instances with two agents and graphs of maximum
degree 3 which are “almost trees”—in particular, have treewidth 2 (Theorem 5).
On the other hand, we show that both problems are polynomial-time solvable on
cycles, which are graphs of maximum degree and treewidth $2$ (Theorem 9); this
provides a complete dichotomy for the complexity of both problems with respect
to treewidth and maximum degree (see Table 1).

Next, we target instances where the number of edges is bounded by a constant.
As the main technical contribution of this article, we show that both problems
under consideration become polynomial-time tractable under this restriction
(Theorem 10). The algorithm is non-trivial and combines insights into the
structure of a hypothetical solution with branching techniques, linear
programming subroutines and insights from multidimensional geometry.

Related Work. Bei and Suksompong (2021) studied graph cutting under the
fairness notions of proportionality and equitability; this was the first paper
that considered a graph structure with divisible items. For indivisible items
there are several different graph-based approaches. In the most common
modelling scenario the items correspond to the vertices of the graph and each
agent must get a connected subgraph Bei et al. (2019); Bilò et al. (2021);
Bouveret et al. (2017); Deligkas et al. (2021); Elkind et al. (2021a);
Igarashi and Peters (2019); Suksompong (2019).

A different line of work uses graphs to denote the relationships between the
agents, where an agent compares their bundle only against the bundles of the
agents they are connected with Abebe et al. (2017); Aziz et al. (2018); Bei et
al. (2017, 2020); Chevaleyre et al. (2017); Eiben et al. (2020).

There is a long line of papers for classical cake cutting and its extensions.
Su (1999) gave an alternative proof of existence of contiguous envy free
solutions using Sperner’s lemma; this proof was used in Deng et al. (2012) to
place the approximate version of the computational problem in PPAD. Recently,
Segal-Halevi and Suksompong (2021) extended the existential result for groups
of agents and Hosseini et al. (2020); Igarashi and Meunier (2021) extended the
result for multilayered cakes. Polynomial-time algorithms that compute
approximately envy-free contiguous allocations were presented in
Arunachaleswaran et al. (2019); Deng et al. (2012); Goldberg et al. (2020),
while Seddighin et al. (2019) provides a polynomial-time algorithm for the
problem for a very restricted class of valuations; to the best of our
knowledge this is the only positive result for exact solutions. On the other
hand, non-contiguous envy free cake cutting is easy to solve Cohler et al.
(2011); Kurokawa et al. (2013); Lipton et al. (2004).

In addition to the above, there are many other works that study variants of
cake cutting Elkind et al. (2021c, b); Segal-Halevi et al. (2016); Menon and
Larson (2017); Marenco and Tetzlaff (2014); Caragiannis et al. (2011); Brânzei
and Nisan (2019, 2017); Brânzei and Miltersen (2015); Bei et al. (2021);
Balkanski et al. (2014); Aumann and Dombb (2015).

##  2 Preliminaries and Problem Definition

Notation. For rational numbers $i,j\in\mathbb{Q}$, we use the standard
notation $[i,j]=\\{k\in\mathbb{Q}\mid i\leq k\leq j\\}$ for intervals and for
an interval $I=[i,j]$ we denote its length by $|I|=\max\\{j-i,0\\}$. We denote
the set of all non-negative rational numbers by $\mathbb{Q}^{+}$. Further, we
refer to the handbook by Diestel (2012) for standard graph terminology.
Throughout the paper we will consider simple undirected graphs.

Graph Cutting. Consider a set $A$ of $n$ agents, a connected graph $G=(V,E)$,
and for each agent $a\in A$ an edge weight function $u_{a}:E\to\mathbb{Q}^{+}$
over the edges of $G$; $u_{a}$ is the _utility_ (function) of agent $a$, and
for a specific edge $e\in E$ we call $u_{a}(e)$ the _utility_ of $a$ for $e$.

A _piece of an edge_ $e$ is a tuple $(e,I)$ where $I\subseteq[0,1]$ is a
possibly empty interval. We assume an arbitrary but fixed order $V$ of the
vertices of $G$, and say that pieces $(e,I)$ and $(e^{\prime},I^{\prime})$ of
two different edges $e,e^{\prime}\in E$ are _adjacent_ if

  * •

there is some $v\in V$ such that $e=uv$ and $e^{\prime}=vu^{\prime}$ (i.e. $e$
and $e^{\prime}$ are adjacent in $G$), and

  * •

if $u$ has a smaller index in the ordering of $V$ than $v$, then $1\in I$ and
$0\in I$ otherwise, and

  * •

similarly, if $u^{\prime}$ has a smaller index in the ordering of $V$ than
$v$, then $1\in I^{\prime}$ and $0\in I^{\prime}$ otherwise.

A _piece_ of $G$ is a collection $P$ of pieces of edges of $e$ such that for
every pair of pieces of edges $(e_{0},I_{0}),(e_{\ell},I_{\ell})$ in $P$ there
is a sequence of pieces of edges
$(e_{1},I_{1}),\dotsc,(e_{\ell-1},I_{\ell-1})$ in $P$ such that for all $j$
with $0\leq j<\ell$, $(e_{j},I_{j})$ and $(e_{j+1},I_{j+1})$ are adjacent. An
example is provided in Figure 1.

The utility of an agent $a$ for a piece $P$ is given as
$u_{a}(P)=\sum_{(e,I)\in P}|I|\cdot u_{a}(e)$. Note that $\\{(e,[0,1])\mid
e\in E\\}$ is also a piece of $G$. As is standard, our algorithms will assume
_normalized_ utilities, i.e., $u_{a}(G)=1$ for all $a\in A$111Instances with
non-normalized utilities can be trivially transformed into equivalent ones
with normalized utilities..

Edge pieces:
pink:$(v_{1}v_{2},[0,\frac{1}{2}])$,$(v_{1}v_{3},[0,1])$,
$(v_{1}v_{4},[0,1])$, $(v_{1}v_{5},[0,\frac{5}{6}])$, $(v_{3}v_{4},[0,1])$;
blue: $(v_{2}v_{3},[0,\frac{1}{2}])$, $(v_{2}v_{3},[\frac{3}{4},1])$;
green: $(v_{1}v_{5},[\frac{5}{6},1])$,
$(v_{1}v_{6},[\frac{1}{2},\frac{3}{4}])$
Only the pink edge pieces form a piece of the graph together; they are
adjacent via $v_{1}$, $v_{3}$ and $v_{4}$.

Figure 1: Examples of pieces of edges and of a graph.

A _partition_ of $G$ into pieces is a set $\Pi$ of pieces such that for every
edge $e\in E$ and every real $0\leq\alpha\leq 1$, there is precisely one piece
$P\in\Pi$ and one $(e,I)\in P$ such that $\alpha\in I$. In some cases it is
also necessary to allocate each vertex to a single piece: a partition of $G$
into pieces is _vertex-disjoint_ if all pieces of edges containing a vertex
belong to the same piece of the graph. See Figure 2 for an example.

This partition is not vertex-disjoint as $v_{1}$ is contained in both the
orange and pink piece of the graph. Already if one orange edge piece was pink,
the remaining orange edge piece could be given by an open interval, making the
partition vertex-disjoint.

Figure 2: Non-vertex-disjoint partition of a graph into seven connected pieces
of different colors.

Finally we are ready to define our problem of interest. In (piecewise) envy-
free graph cutting (EF-GC) we are given agents $A$, graph $G$ and utilities
$u_{a}:E\to\mathbb{Q}^{+}$ for each agent $a\in A$. Our task is to construct a
partition $\Pi$ of $G$ into pieces and a bijection (called an _assignment_)
$\pi:A\to\Pi$ such that for every pair of agents $a,a^{\prime}\in A$, it holds
that $u_{a}(\pi(a))\geq u_{a}(\pi(a^{\prime}))$. This condition is commonly
referred to as _envy-freeness_ in assignment and allocation problems, and when
it is violated for some $a$ and $a^{\prime}$, we say that $a$ _envies_
$a^{\prime}$.

We can analogously define the problem of (piecewise) envy-free vertex-disjoint
graph cutting (EF-VDGC) by additionally requiring $\Pi$ to be vertex-disjoint.
In fact, by replacing each vertex in an instance of EF-GC with a clique of
size $|E(G)|$, we obtain a simple reduction from the former problem to EF-
VDGC.

######  Observation 1.

EF-GC can be reduced to EF-VDGC in polynomial time.

Bounding the Number of Cells in Metric Spaces. One prominent tool our main
algorithm for solving EF-GC and EF-VDGC uses is a theorem that applies to the
behavior of polynomials in higher-dimensional spaces. To provide a high-level
intuition, consider a $d$-dimensional space that is cut into regions by
$s$-many hyperplanes or, more generally, “well-behaved cuts” defined by
bounded-degree polynomials. The combination of these cuts splits the whole
space into “cells”, each consisting of points that lie on the same side of
each of the $s$-many cuts. While the trivial bound for the number of these
cells is $2^{s}$, it can be shown that the number of such cells is in fact
polynomial in $s$ for fixed $d$ and that representatives of these cells can be
computed efficiently.

Let $V=\mathbb{R}^{d}$ and let us denote the ring of polynomials over
variables $X_{1}$, …, $X_{d}$ with coefficients in $\mathbb{R}$ by
$\mathbb{R}[X_{1},\dots,X_{d}]$. For a set of $s$ polynomials
$\mathcal{P}=\\{P_{1},\dots,P_{s}\\}\subset\mathbb{R}[X_{1},\dots,X_{d}]$, a
sign condition is specified by a sign vector $\sigma\in\\{-1,0,+1\\}^{s}$, and
the sign condition is non-empty over $V$ with respect to $\mathcal{P}$ if
there is a point $x\in V$ such that
$\sigma=(\operatorname{sign}(P_{1}(x)),\dots,\operatorname{sign}(P_{s}(x))),$
where $\operatorname{sign}(\alpha)$ is the sign function defined as

$\operatorname{sign}(\alpha)=\begin{cases}1,\text{ if }\alpha>0,\\\ 0,\text{
if }\alpha=0,\\\ -1,\text{ if }\alpha<0.\end{cases}$

The _realization space_ of $\sigma\in\\{-1,0,+1\\}^{s}$ over $V$ is the set

$R(\sigma)=\\{x|x\in
V,\sigma=(\operatorname{sign}(P_{1}(x)),\dots,\operatorname{sign}(P_{s}(x)))\\}.$

If $R(\sigma)$ is not empty then each of its non-empty semi-algebrically
connected (which is equivalent to just connected on semi-algebraic sets (Basu
et al., 2006, Theorem 5.22)) components is a _cell_ of $\mathcal{P}$ over $V$.

The following result, sometimes called Warren’s Theorem Warren (1968) , gives
an algorithm to compute a point in each cell of $\mathcal{P}$ over $V$.

######  Proposition 2 (Basu, Pollack and Roy (2006, Theorem 13.22), see also
Simonov et al. (2019)).

Let $\mathcal{P}\subset\mathbb{R}[X_{1},\dots,X_{d}]$ be a finite set of $s$
linear polynomials, i.e., each $P\in\mathcal{P}$ is of degree at most $1$. Let
$D$ be a ring generated by the polynomials in $\mathcal{P}$. There is an
algorithm using at most $\mathcal{O}(s^{d})$ algorithmic operations in $D$,
which given $\mathcal{P}$ computes a set of points meeting every non-empty
cell of $V$ over $\mathcal{P}$.

We remark Proposition 2 is merely the special case of Basu, Pollack and Roy
(2006, Theorem 13.22) restricted to $V=\mathbb{R}^{d}$ and linear polynomials.

##  3 Instances with Few Agents

In this section we consider the complexity of EF-GC and EF-VDGC for instances
with only a few agents. Interestingly, we will show that while both problems
are -hard even for instances with only two agents, EF-GC turns out to be
significantly harder when additional restrictions are considered for the input
graph. In particular, while EF-GC is already -hard on stars, EF-VDGC can be
solved in polynomial-time (for a fixed number of agents) even on trees and
only becomes -hard on graphs that have a vertex deletion set into a matching.
Moreover, the problem becomes much harder if we relax the graph structure from
trees to “tree-like graphs”: both problems become -hard on graphs that have
treewidth $2$ and maximum degree $3$ (see Figure 3 for an illustration).

######  Theorem 3.

EF-GC is -hard even when restricted to instances with two agents where the
graph is a star.

###### Proof.

We provide a simple polynomial-time reduction from the well-known -complete
Number Partitioning problem. Let $S$ be an instance of Number Partitioning,
i.e., $S$ is a multi-set of non-negative integers and the aim is to decide
whether there is a partition of $S$ into two subsets $S_{1}$ and $S_{2}$ such
that $\sum_{s\in S_{1}}s=\sum_{s\in S_{2}}s$. Given $S$, we construct an
instance $(A,G,(u_{a})_{a\in A})$ of EF-GC by setting $A=\\{a_{1},a_{2}\\}$,
$G$ is the star with center $c$ and with one leaf $l_{s}$ for every $s\in S$,
and $u_{a_{1}}((c,l_{s}))=u_{a_{2}}((c,l_{s}))=s$ for every $s\in S$. Observe
that w.l.o.g. we can assume that every edge is fully assigned to one of the
agents, since otherwise one of the agents would be assigned less than one
edge, which would not result in an envy-free assignment. Therefore, every
envy-free assignment results in a $2$-partition of the edges both having the
same total valuation, which shows that $S$ is a yes-instance of Number
Partitioning if and only if $(A,G,(u_{a})_{a\in A})$ is a yes-instance of EF-
GC. ∎

######  Theorem 4.

EF-VDGC is -hard even when restricted to instances with two agents where the
graph consists of a matching plus two additional vertices.

###### Proof.

The reduction is similar to the one employed in Theorem 3 and uses a
polynomial-time reduction from the Number Partitioning problem. Let $S$ be an
instance of Number Partitioning, i.e., $S$ is a multi-set of non-negative
integers and the aim is to decide whether there is a partition of $S$ into two
subsets $S_{1}$ and $S_{2}$ such that $\sum_{s\in S_{1}}s=\sum_{s\in S_{2}}s$.
Given $S$, we construct an instance $(A,G,(u_{a})_{a\in A})$ of EF-VDGC as
follows. We set $A=\\{a_{1},a_{2}\\}$ and the graph $G$ has two vertices
$c_{1}$ and $c_{2}$ as well as two vertices $l_{s}$ and $l_{s}^{\prime}$ for
every $s\in S$. Moreover, $G$ has all edges between $\\{c_{1},c_{2}\\}$ and
$\\{l_{s}\mid s\in S\\}$ and an edge between $l_{s}$ and $l_{s}^{\prime}$ for
every $s\in S$. Note that $G-\\{c_{1},c_{2}\\}$ is a matching. Finally, for
every $i\in\\{1,2\\}$, we set $u_{a_{i}}(e)=s$ if $e=(l_{s},l_{s}^{\prime})$
for some $s\in S$ and $u_{a_{i}}(e)=0$, otherwise. Note that w.l.o.g. we can
assume that every edge $(l_{s},l_{s}^{\prime})$ is fully assigned to exactly
one of the agents since otherwise one agent would only be assigned a part of
$(l_{s},l_{s}^{\prime})$ (and nothing else). Moreover, by assigning $c_{i}$ to
agent $a_{i}$, we can obtain an assignment that assigns any subset of the
edges $(l_{s},l_{s}^{\prime})$ to agent $a_{i}$ and all remaining such edges
to agent $a_{2-i+1}$. Since every such assignment is envy-free if and only if
the total valuations of the edges assigned to both agents is the same, we
obtain that $S$ is a yes-instance of Number Partitioning if and only if
$(A,G,(u_{a})_{a\in A})$ is a yes-instance of EF-VDGC. ∎

######  Theorem 5.

EF-VDGC and EF-GC are -hard even when restricted to instances with two agents
with identical valuations where the graph has treewidth 2 and maximum degree
3.

###### Proof.

Again, we will reduce from Number Partitioning. This time, the graph we will
construct has maximum degree 3 and it is not hard to verify that has treewidth
2. We will use the same construction to prove both results, this is depicted
at Figure 3. More formally, given an instance of Number Partitioning with $n$
positive integers, we create a graph with $4n$ vertices as follows. For every
$i\in[n]$, we construct the vertices $a_{i},b_{i},c_{i}$, and $d_{i}$ and the
edges $(a_{i},c_{i}),(c_{i},b_{i})$ and $(c_{i},d_{i})$. In addition, for
every $i\in[n-1]$ we create the edges $(a_{i},a_{i+1})$ and $(b_{i},b_{i+1})$.
To complete the construction, we need to specify the valuations of the agents.
We create two agents with identical valuations. For every $i\in[n]$, both
agents value the edge $(c_{i},d_{i})$ with $s_{i}$. Every other edge has value
0.

To prove the theorem we observe the following. Firstly, note that w.l.o.g. we
can assume that every edge $(c_{i},d_{i})$ is fully assigned to exactly one of
the agents since otherwise one agent would only be assigned a part of
$(c_{i},d_{i})$ (and nothing else). In addition, note that for EF-GC there is
no allocation where a vertex is shared by the two agents. To complete our
proof, we observe that every allocation corresponds to a partition of the $n$
integers, we can conclude that there exists an envy-free allocation if and
only if there is a solution for the Number Partitioning instance. ∎

Figure 3: The graph used in the proof of Theorem 5.

Next, we move on to the aforementioned algorithmic result for EF-VDGC. To
establish that, we first prove the following technical lemma.

######  Lemma 6.

Let $\mathcal{I}=(A,G,\\{u_{a}\\}_{a\in A})$ be an instance of EF-GC (EF-VDGC)
and let $G$ be a tree, or a cycle, and let $F$ be a set of edges of $G$. There
is an algorithm that runs in time polynomial in
$|A|^{|F|+1}\cdot|F|^{|A|}\cdot|\mathcal{I}|$, where $|\mathcal{I}|$ is the
encoding length of $\mathcal{I}$,and either outputs an assignment $\pi$ that
is envy-free such that each connected component of $G-F$ is assigned to
exactly one agent (and, for EF-VDGC, $\pi(A)$ is additionally a vertex-
disjoint partition) or correctly identifies that such an assignment does not
exist.

###### Proof.

Observe that $G-F$ consists of most $|F|+1$ connected components. In addition,
observe that there are at most $|A|^{|F|+1}$ many assignments of these
connected components to agents. Observe that there might exist agents that
have been assigned more than one component and other agents that might not
have been assigned any component. Consider now one of these assignments. For
each agent $a$ that is assigned more than one component, if we can, we make
their component connected by assigning a minimal set of edges from $F$ that
makes $\pi(a)$ connected. Note, that if $G$ is a tree this choice is unique,
if it exists. If $G$ is a cycle we branch on up to two such choices if they
exist. If we cannot make the piece of every agent connected, then we discard
this assignment and we proceed to the next one. Let $F^{\prime}\subseteq F$ be
the set of edges not yet assigned to any agent, after we convert the
components every agent gets into a single one. Each agent that is not assigned
any piece yet, will get a piece fully inside some edge of $F^{\prime}$. For
each such agent we branch on the edge they will be contained in. This results
in at most $|F^{\prime}|^{|A|}\leq|F|^{|A|}$ branches.

At this point there are two possibilities for an agent.

  * •

They are assigned to a single edge of $F$ and its piece is fully inside some
edge $e\in F$.

  * •

They get all edges in a subgraph $T$ of $G$ induced by a union of some
connected component of $G-F$ and edges of $F$. In this case the agent is also
allowed to get some pieces of edges incident with some vertex in $T$ (possibly
not the full edge), however we do not branch on such edges for this agent.

Note that if $\mathcal{I}$ is an instance of EF-VDGC, then we can check that
the trees $T_{1}$ and $T_{2}$ assigned to two different agents in our
branching are vertex disjoint and terminate the branch if it is not the case.

For each branch we now design an instance of Linear Programming (LP) that has
a solution if and only if there exists an envy-free assignment consistent with
our branching (which can be viewed as a “guess” of the properties of an
optimal solution). For each edge $e\in F^{\prime}$ and each agent $a\in A$
such that $a$ is allowed to have a piece inside the edge $e$ according to our
guess we have a variable $x_{e}^{a}$ which represents the length of the piece
of the edge $e$ that the agent $a$ gets. We add the following constraints into
the LP:

$\displaystyle x_{e}^{a}\geq 0$ $\displaystyle\text{for all }a\in A,e\in
F^{\prime}$ (1) $\displaystyle\sum_{a\text{ is allowed a piece of
e}}x_{e}^{a}=1$ $\displaystyle e\in F^{\prime}.$ (2)

Let $\mathbf{x}$ denote the vector of all variables in some fixed order. Given
$\mathbf{x}$, we can compute the value of the piece assigned to an agent $a$.
If agent $a$ is assigned a subtree $T$ and $F_{T}$ denotes the subset of edges
in $T$ that are incident with some vertex in $T$, then for every agent
$a^{\prime}\in A$ we set

$u_{a^{\prime}}(a,\mathbf{x})=u_{a^{\prime}}(T)+\sum_{e\in
F_{T}}u_{a^{\prime}}(e)\cdot x_{e}^{a}.$

For an agent $a$ that is fully assigned a piece inside an edge $e\in F$ and
every agent $a^{\prime}$, we set

$u_{a^{\prime}}(a,\mathbf{x})=u_{a^{\prime}}(e)\cdot x_{e}^{a}.$

Now for every ordered pair $(a,a^{\prime})$ of agents $a,a^{\prime}\in A$, we
add the following constraint to the LP:

$u_{a}(a,\mathbf{x})\geq u_{a}(a^{\prime},\mathbf{x}).$ (3)

It is rather straightforward to see that if Constraints (1) and (2) are
satisfied, then we can assign to each agent $a$ a connected piece of the graph
such that the length of the piece the agent $a$ gets inside the edge $e$ is
$x^{a}_{e}$ and if we guess the subgraph $T$ for the agent $a$, then $a$ is
assigned all edges inside $T$ fully. Moreover, it is easy to see that in this
case the utility of the agent $a$ is $u_{a}(a,\mathbf{x})$. Hence, Constraint
(3) implies that such assignment is envy-free. Moreover, assuming an envy-free
assignment $\pi_{\mathrm{SOL}}$ exists, one of our branches has to be
consistent with $\pi_{\mathrm{SOL}}$ and in that case the algorithm will
output a vertex-disjoint envy-free assignment. We conclude that if the
algorithm does not find a solution in any of the branches then the input is a
No-instance.

Overall this procedure requires time in
$\mathcal{O}(|A|^{|F|+1}\cdot|F|^{|A|}\cdot T(|F||A|+|A|))$, where $T(x)$
denotes the time required to solve a linear program with $x$ variables. The
most efficient currently known procedure requires $\mathcal{O}(x^{\omega}L)$
Alman and Williams (2021) where $\omega$ is the matrix multiplication constant
and $L$ is the number of input bits, which in our case is upper-bounded by
$|\mathcal{I}|$. ∎

Lemma 6 allows us to solve EF-VDGC on trees by applying initial branching to
reach a situation satisfying the preconditions of Lemma 6.

######  Theorem 7.

For each $c\in\mathbb{N}$, EF-VDGC restricted to instances with at most $c$
agents is polynomial-time solvable on trees.

###### Proof.

Let $\pi_{\mathrm{SOL}}$ be an arbitrary vertex-disjoint envy-free assignment.
Since $G$ is a tree and agents do not share vertices, we claim that there is a
set $F$ of at most $|A|-1$ edges with the following properties: (I) each of
the exactly $|F|+1$ components of $G-F$ is assigned to a single agent, and
(II) every edge $e\in F$ is split between the two agents assigned to the
components that contain a vertex incident with $e$ plus some of the agents who
are not assigned any of these components.

To see the claim, let us root $G$ in some arbitrary vertex $r$. Let $a_{r}$ be
the unique agent that contains the vertex $r$ in some piece of
$\pi_{\mathrm{SOL}}(r)$. For every other agent $a$, there is a unique point
$x$ in the closure of pieces of $a$ such that the unique path from $x$ to $r$
does not intersect any piece of $a$ (note that $x$ is not necessarily a vertex
and could be a point inside some edge). Given this point we assign to the
agent $a$ a single edge $e_{a}$ as follows:

  * •

if $x$ is inside some edge $f$, then we let $e_{a}=f$,

  * •

if $x$ is a vertex of $G$ and there is a unique edge $f$ that contains a piece
of $a$, then we let $e_{a}=f$, and

  * •

else $x$ is a vertex of $G$ incident to at least $2$ edges that get a piece of
$a$. We let $e_{a}$ be the unique edge incident on $x$ on the unique $x$-$r$
path in $G$.

Let $F=\\{e_{a}\mid a\in A\setminus\\{a_{r}\\}\\}$. We show that each
connected component of $G-F$ is assigned to a single agent. The rest of the
claim then follows straightforwardly from the connectivity of the pieces
assigned to single agents. Let $T$ be a subtree of $G$ induced by some
connected component of $G-F$. We can root $T$ in the unique vertex that is
“closest” to $r$. That is the vertex $r_{T}$ such that the unique $r_{T}$-$r$
path does not contain any vertex of $T$. We show that all edges of $T$ are
assigned to some agent $a$ such that $e_{a}$ is the unique edge from $r_{T}$
to its parent in $G$. We distinguish two possibilities. If all agents contain
a piece in at most one edge incident with $r_{T}$, then it is easy to see that
all edges incident with $r_{T}$ are in $F$. Therefore, $T$ is a singleton and
the claim follows. Else, if there is an agent $a$ such that $a$ gets pieces in
at least two edges incident on $r_{T}$. Then $e_{a}$ is the edge from $r_{T}$
to its parent and $a$ is the unique such agent; i.e., all other agents get
pieces in at most one edge incident on $r_{T}$. We show by induction on the
distance from $r_{T}$ that all edges in $T$ are fully assigned to $a$ by
$\pi_{\mathrm{SOL}}$. For the base case observe that if some agent contains a
piece of an edge $f$ incident with $r_{T}$, then $f\in F$ and in particular
$f\notin E(T)$. Therefore all the edges incident of $r_{T}$ in $T$ are
assigned to $a$ by $\pi_{\mathrm{SOL}}$. Now let us consider a vertex $v\in
V(T)$ at distance $i$ from $r_{T}$. We know, by the induction hypothesis, that
the unique edge $f$ between $v$ and its parent in $T$ is fully assigned to
$a$. If there is an agent $a^{\prime}$ that contains pieces in at least $2$
edges incident o $v$, then $e_{a^{\prime}}=f$, which is not possible as $f\in
E(T)$. Therefore every agent $a^{\prime}$ (other than $a$) contains a piece in
at most one edge incident with $v$ and if $a^{\prime}$ contains a piece inside
edge $f^{\prime}$ incident on $v$, then it is easy to see that
$e_{a^{\prime}}=f^{\prime}$ and $f^{\prime}\notin E(T)$. Hence all edges
incident with $v$ in $T$ are also fully assigned to $a$ and the claim follows
by induction. We note that the same discussion works even if $r_{T}=r$, in
which case we show that $T$ is assigned to $a_{r}$ analogously.

We can now enumerate all of the at most $|V(G)|^{|A|}$ possible sets of edges
$F\subseteq E(G)$ such that $|F|\leq|A|-1$. The theorem then follows by
applying Lemma 6 to $G$ and $F$.

Using the notation and the running time bound from the proof of Lemma 6, it
follows that the overall complexity lies in
$\mathcal{O}(|V(G)|^{|A|}\cdot|A|^{|A|}\cdot(|A|-1)^{|A|}\cdot T(|A|^{2}))$. ∎

To complete our understanding of EF-GC and EF-VDGC for instances with only
boundedly-many agents, we show that both problems are also polynomial-time
solvable on graphs of maximum degree $2$ (i.e., cycles) and that the former is
polynomial-time solvable on bounded-degree trees. These results follow a
similar approach as the proof of Theorem 7, which is a combination of initial
branching and Lemma 6.

######  Theorem 8.

For each $c,d\in\mathbb{N}$, EF-GC restricted to instances with at most $c$
agents is polynomial-time tractable on trees with maximum degree at most $d$.

###### Proof.

We show that there are at most $|A|$ many vertices and edges of $G$ than can
be in a piece of more than one agent. Given this claim, we can enumerate all
of the at most $(2\cdot|V(G)|-1)^{|A|}$ possible sets of vertices $U\subseteq
V(G)$ and edges $F\subseteq E(G)$ such that $|U\cup F|\leq|A|$. Let
$F^{\prime}$ be the union of $F$ and the edges incident with vertices in $U$.
Note that $|F^{\prime}|\leq|A|\cdot\Delta$, where $\Delta$ is the maximum
degree of a vertex in $G$. The theorem then follows by applying Lemma 6 to $G$
and $F^{\prime}$ in each branch.

The rest of the proof is devoted to showing that there are at most $|A|$ many
vertices and edges of $G$ than can be in a piece of more than one agent. Let
$\pi_{\mathrm{SOL}}$ be an arbitrary envy-free assignment. We start the proof
by showing that there are at most $|A|$ many vertices and edges of $G$ than
can be in a piece of more than one agent. Let $U$ be the set of such vertices
and $F$ the set of such edges. That is for every vertex $u\in U$ there exists
two different agents $a_{1}$ and $a_{2}$ such that both
$\pi_{\mathrm{SOL}}(a_{1})$ and $\pi_{\mathrm{SOL}}(a_{2})$ contain a piece
that contain $u$. Similarly, for every edge $e\in F$ there are two agents
$a_{1}$ and $a_{2}$ such that both $\pi_{\mathrm{SOL}}(a_{1})$ and
$\pi_{\mathrm{SOL}}(a_{2})$ contain a piece of the edge $e$. We will construct
an injective function $f\colon U\cup F\rightarrow A$, that is we show that we
can assign to every element (vertex or edge) in $U\cup F$ a unique agent. Let
us root $G$ in some arbitrary vertex $r$. For the rest of the proof, for a
vertex $v$, we will denote by $p_{v}$ the parent of the vertex $v$ in the
rooted tree $G$ rooted in $r$. For a vertex $u\in U$, at most one agent
contains a piece of the edge $up_{u}$ from $u$ to its parent $p_{u}$ that
contains the vertex $u$. Since there are at least two agents whose pieces
contain the vertex $u$, there is at least one other agent $a$ such that $a$
does not get a piece of the edge $up_{u}$, but gets a piece of some other edge
that contains the vertex $u$. We let $f(u)=a$. For an edge $e\in F$ let
$f=up_{u}$, where $p_{u}$ is the parent of $u$. We let $f(e)=a$, where $a$ is
the agent that gets the piece containing $u$. Note that since at least two
pieces contain a piece of the edge $e$, it follows that the piece of agent $a$
does not contains $p_{u}$.

Now let $x$ and $y$ be two different elements of $U\cup F$. We show that
$f(x)\neq f(y)$. Clearly, if $f(x)=f(y)=a$, then the piece assigned to the
agent $a$ under $\pi_{\mathrm{SOL}}$ contains a piece of both $x$ and $y$. We
will show that if an agent $a$ such that $\pi_{\mathrm{SOL}}(a)$ contains
piece of both $x$ and $y$, then either $f(x)\neq a$ or $f(y)\neq a$. Let $u$
denote the vertex $x$ if $x\in U$ otherwise let $u$ be the vertex such that
$x$ is the edge $up_{u}$ in $F$. Similarly, let $v$ be $y$ if $y\in U$ else
let $v$ be the vertex such that $y$ is the edge $vp_{v}$. Note that if
$f(x)=a$, then $\pi_{\mathrm{SOL}}(a)$ contains a piece containing the vertex
$u$. Similarly, if $f(y)=a$, then $\pi_{\mathrm{SOL}}(a)$ contains $v$. Since
piece of the agent $a$ is connected, it follows that $\pi_{\mathrm{SOL}}(a)$
contains a path from $u$ to $v$, moreover since $G$ is a tree, this path is
unique. Now note that if $v$ is an ancestor of $u$, then the unique path from
$u$ to $v$ contains the edge $up_{u}$ and from the definition of $f$ it
follows $f(x)\neq a$. If $u$ is an ancestor of $v$, then the unique path from
$u$ to $v$ in $G$ contains the edge $vp_{v}$, and $f(y)\neq a$. Finally, if
$v$ is not ancestor of $u$ and $u$ is not an ancestor of $v$, then the unique
path from $u$ to $v$ contains both edges $up_{u}$ and $vp_{v}$, hence
$f(x)\neq a$ and $f(y)\neq a$.

Using the notation and the running time bound from the proof of Lemma 6, it
follows that the overall complexity lies in
$\mathcal{O}((2|V(G)|-1)^{|A|}\cdot|A|^{|A|\Delta+1}\cdot(|A|\Delta)^{|A|}\cdot
T(|A|\Delta|A|+|A|))$. ∎

######  Theorem 9.

For each $c\in\mathbb{N}$, EF-GC and EF-VDGC restricted to instances with at
most $c$ agents is polynomial-time solvable on cycles.

###### Proof.

It is straightforward to see that in any partition of a cycle graph $G$ into
$|A|$ connected pieces there are at most $|A|$ edges that are assigned to two
different agents. The theorem then follows by branching on all $|V(G)|^{|A|}$
many possibilities of at most $|A|$ many edges shared by more than one agent.
The theorem then follows by applying Lemma 6 in each branch.

Using the notation and the running time bound from the proof of Lemma 6, it
follows that the overall complexity lies in
$\mathcal{O}(|V(G)|^{|}A|\cdot|A|^{2|A|+1}\cdot T(|A|^{2}+|A|))$. ∎

##  4 Instances with Few Edges

In the section we provide an algorithm showing that both EF-GC and EF-VDGC are
in parametrized by the number of edges in the input graph $G$.

######  Theorem 10.

EF-GC and EF-VDGC can be solved in time $|A|^{\mathcal{O}(|E(G)|^{2})}$.

The algorithm can be divided into three main steps. We start with a direct
brute-force branching over all assignments of agents that span more than one
edge, and for these special agents we identify precisely the edges from which
they will receive a piece. We also branch to determine the exact number of
agents that will be assigned to each edge. This will result in
$|A|^{\mathcal{O}(|E(G)|)}$ many initial branches, and each branch already
provides useful information about a hypothetical sought-after solution—but not
enough to solve the problem. Crucially, every solution to the original
instance corresponds to one of the branches.

Our aim in the second step will be to construct, for each branch, a Linear
Program (LP) to determine the exact lengths of all the pieces in an envy-free
partitioning. In particular, if the branch corresponds to a solution, then we
require that the LP outputs a partitioning that can be matched to agents in a
way which also produces a solution. Unfortunately, the branching carried out
in the previous step is not yet sufficient to construct such an LP: during the
construction, we need to apply an additional advanced branching step to
identify a small number of _envy-critical_ agents that are assigned completely
to a single edge. The property of these agents is that they will be the
“closest” to envying agents assigned to other edges in the graph, and in the
LP these will serve as anchors which ensure that an envy-free assignment will
exist as long as the assignment of agents is carried out in a way which
respects the selected envy-critical agents. Defining, bounding the number of,
and branching on these envy-critical agents is the most challenging part of
the algorithm, and is also where Proposition 2 will be used.

Finally, based on the branching decisions and a solution to the constructed
LP, we design an instance of bipartite matching that matches the remaining
unassigned agents with the pieces given by the LP instance. If a matching
exists we are guaranteed to have found a solution; if not, then our branch
does not correspond to a valid solution.

Initial Branching. For the remainder of this section, we fix an instance
$\mathcal{I}$ of EF-GC or EF-VDGC given by the set of agents $A$, graph
$G=(V,E)$, and utilities $u_{a}:E\to\mathbb{Q}^{+}$ for each agent $a\in A$.
Denote $k=|E(G)|$. We can now start with the branching phase. Let us assume
$\mathcal{I}$ admits an envy-free assignment $\pi_{\mathrm{SOL}}$ into some
partition of $G$ into pieces; we will describe the branching as a series of
“guesses” of the properties of this solution $\mathcal{I}$ and its
interactions with $G$.

First, observe that for each edge $e$ there are at most $2$ agents that can be
assigned a piece of the edge $e$ together with a piece of some other edge.
These are the agents in $\pi_{\mathrm{SOL}}$ that receive the piece
$(e,[0,c])$ and the piece $(e,[d,1])$ for some constant $c,d\in[0,1]$. For
each edge $e$, we guess the agent that gets the piece $(e,[0,c])$ (for some
unspecified $c\in[0,1]$) and say that this is the guess for pair $(e,0)$;
analogously, we guess the agent that gets the piece $(e,[d,1])$ (for some
unspecified $d\in[0,1]$) and say that this is the guess for pair $(e,1)$. This
results in $|A|^{2k}$ many branches. Let $A_{V}$ be the set of the at most
$2k$ agents guessed in the previous step.

All the remaining agents are assigned by $\pi_{\mathrm{SOL}}$ a piece
$\\{(e,[c,d])\\}$ for some edge $e$. For every such agent, we say that it gets
a piece _fully contained inside edge $e$_. While it is too computationally
expensive to guess precisely which agents get a piece fully contained in an
edge $e$, we will guess the number of agents that get a piece fully contained
in an edge $e$. This results in $|A|+1$ many guesses for each edge, amounting
to a branching factor of at most $(|A|+1)^{k}$. Let us denote by $n_{e}$ the
number of agents that get a piece fully contained in the edge $e$. We now
perform a set of sanity checks on our branching; in particular, we discard
branches which do not fulfil the following conditions:

  1. 1.

$|A_{V}|+\sum_{e\in E(G)}n_{e}=|A|$.

  2. 2.

For every agent $a\in A_{V}$, the guesses of pieces assigned to $a$ form a
connected subset of $G$. More formally, whenever our branch assigns an agent
$a$ to two distinct pairs $(e,i)$ and $(f,j)$, where $e,f\in E(G)$ and
$i,j\in\\{0,1\\}$, there must exist a path $P=e_{1}e_{2}\ldots e_{q}$ from
$e[i]$ to $f[j]$ such that for each $\iota\in[q]$ it holds that (I)
$n_{e_{\iota}}=0$ and (II) the agent $a$ is also the guess for both
$(e_{\iota},0)$ and $(e_{\iota},1)$.

  3. 3.

In the case of EF-VDGC, we will also verify that the branching corresponds to
a vertex-disjoint partition. In particular, for each vertex $v$ let $E_{v,0}$
be the set of edges incident to $v$ and a vertex preceding $v$ in the ordering
and $E_{v,1}$ be the set of edges incident to $v$ and a vertex succeeding $v$
in the ordering. We check that there is a single agent $a$ such that for each
edge $e\in E_{v,0}$, $a$ is the guess for $(e,0)$, and at the same time for
each edge $e^{\prime}\in E_{v,1}$, $a$ is the guess for $(e^{\prime},1)$.

Linear Programming. We can now begin describing the instance of LP that we
will use to determine the partition. For this, it will be useful to observe
that agents fully contained in the same edge must receive a segment of the
same length.

######  Observation 11.

Let $e\in E(G)$ be an edge and $a_{1},a_{2}\in A$ two agents such that
$\pi_{\mathrm{SOL}}(a_{1})=\\{(e,[x_{1},y_{1}])\\}$ and
$\pi_{\mathrm{SOL}}(a_{2})=\\{(e,[x_{2},y_{2}])\\}$, then
$|y_{1}-x_{1}|=|y_{2}-x_{2}|$.

###### Proof.

Since $u_{a_{1}}(\pi_{\mathrm{SOL}}(a_{1}))=|y_{1}-x_{1}|\cdot u_{a_{1}}(e)$
and $u_{a_{1}}(\pi_{\mathrm{SOL}}(a_{2}))=|y_{2}-x_{2}|\cdot u_{a_{1}}(e)$,
envy-freeness implies $|y_{1}-x_{1}|\geq|y_{2}-x_{2}|$. Similarly,
$u_{a_{2}}(\pi_{\mathrm{SOL}}(a_{1}))=|y_{1}-x_{1}|\cdot u_{a_{2}}(e)$ and
$u_{a_{2}}(\pi_{\mathrm{SOL}}(a_{2}))=|y_{2}-x_{2}|\cdot u_{a_{2}}(e)$, hence
envy-freeness implies $|y_{1}-x_{1}|\leq|y_{2}-x_{2}|$. ∎

For each edge $e\in E(G)$, the LP instance will have variables $x^{0}_{e}$,
$\delta_{e}$, and $x^{1}_{e}$. The variable $\delta_{e}$ represents the length
of each piece $(e,[c,d])$ assigned to any agent that gets a piece fully inside
$e$. The variable $x^{i}_{e}$ represents the length of the piece of the edge
$e$ that was assigned to the agent $a\in A_{V}$ which is the guess for pair
$(e,i)$. We start by adding the following two constraints saying that all
pieces have non-negative length and the sum of lengths of pieces on each edge
is exactly $1$.

$\displaystyle x^{0}_{e},\delta_{e},x^{1}_{e}\geq 0$ (4) $\displaystyle
x^{0}_{e}+n_{e}\cdot\delta_{e}+x^{1}_{e}=1.$ (5)

For each agent $a\in A_{V}$, let $\operatorname{Pieces}_{a}$ denote the set of
pieces that $a$ is the guess for: $\operatorname{Pieces}_{a}=\\{(e,i)\mid e\in
E(G),i\in\\{0,1\\},\text{ and }a\text{ is the guess for }(e,i)\\}$. Given the
intended meaning of variables $x^{0}_{e}$, $\delta_{e}$, and $x^{1}_{e}$, we
can now add constraints to guarantee envy-freeness between agents in $a\in
A_{V}$. For all $a,a^{\prime}\in A_{V}$ we create the constraint

$\sum_{(e,i)\in\operatorname{Pieces}_{a}}u_{a}(e)\cdot
x^{i}_{e}\geq\sum_{(e^{\prime},i^{\prime})\in\operatorname{Pieces}_{a^{\prime}}}u_{a}(e^{\prime})\cdot
x^{i^{\prime}}_{e^{\prime}},$ (6)

and for every $a\in A_{V}$ and $e\in E(G)$ we create the constraint

$\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a}(f)\cdot x^{i}_{f}\geq
u_{a}(e)\cdot\delta_{e}.$ (7)

Next, for every (ordered) pair of edges $e,f$ such that $n_{e}>0$ and
$n_{f}>0$, need to guarantee that agents that get a piece of length
$\delta_{e}$ do not envy agents with pieces fully inside edge $f$. If we knew
that $a\in A\setminus A_{V}$ gets a piece fully inside $e$, then for this
agent we could express this via the constraint $u_{a}(e)\cdot\delta_{e}\geq
u_{a}(f)\cdot\delta_{f}$. Unfortunately, we do not know which agents get a
piece fully inside $e$ and cannot obtain this information by exhaustive
branching in view of our time bounds.

To overcome this obstacle, let us order the agents in $A\setminus A_{V}$ by
the ratio $\frac{u_{a}(e)}{u_{a}(f)}$ and consider two agents $a_{1},a_{2}$
such that

$\frac{u_{a_{1}}(e)}{u_{a_{1}}(f)}\geq\frac{u_{a_{2}}(e)}{u_{a_{2}}(f)}.$

It is easy to see that $u_{a_{2}}(e)\cdot\delta_{e}\geq
u_{a_{2}}(f)\cdot\delta_{f}$ implies $u_{a_{1}}(e)\cdot\delta_{e}\geq
u_{a_{1}}(f)\cdot\delta_{f}$. Hence to capture the desired constraint it will
be sufficient to guess, for each ordered pair of edges $(e,f)$ the agent
$a_{(e,f)}$ that is assigned a piece fully inside $e$ (by
$\pi_{\mathrm{SOL}}$), and has the smallest value for the fraction
$\frac{u_{a_{(e,f)}}(e)}{u_{a_{(e,f)}}(f)}$ among all the agents that are
assigned a piece fully inside $e$. Intuitively, this corresponds to guessing
an envy-critical agent $a$: among all the agents fully assigned to $e$, the
agent $a$ is “closest” to envying agents fully assigned to $f$. Note that the
guessed envy-critical agents will later preclude some agents from receiving a
piece of $e$ (in particular, those that precede $a$ in the linear order
defined by the fractions).

The procedure described above introduces at most $k^{2}$ many guesses of
agents, which amounts to an additional branching factor of at most
$|A\setminus A_{V}|^{k^{2}}$. For each agent $a_{(e,f)}$, we then add the
following constraint to the LP instance

$u_{a_{(e,f)}}(e)\cdot\delta_{e}\geq u_{a_{(e,f)}}(f)\cdot\delta_{f}.$ (8)

We also perform additional consistency checks for this branching. First of
all, we discard branches which select the same agent as being envy-critical in
multiple pieces (i.e., if $e\neq e^{\prime}$ then we require $a_{(e,f)}\neq
a_{(e^{\prime},f^{\prime})}$, regardless of $f$ and $f^{\prime}$). Moreover,
since we have guessed at most $k-1$ agents for an edge $e$, we also check that
the intended meaning of the choice of the agent $a_{(e,f)}$ is satisfied so
far: for all triples of edges $e,f,f^{\prime}$ we check that

$\frac{u_{a_{(e,f^{\prime})}}(e)}{u_{a_{(e,f^{\prime})}}(f)}\geq\frac{u_{a_{(e,f)}}(e)}{u_{a_{(e,f)}}(f)}.$
(A)

At this point we have added constraints which prevent—assuming our guesses
were correct—an agent in $A_{V}$ from envying any other agent, and agents
outside of $A_{V}$ from envying each other. Finally, for every edge $e$ and
every agent $a\in A_{V}$ we would like to guarantee that the agents that get a
piece fully inside $e$ do not envy the agent $a$. Similarly as before, for
each specific agent $a^{\prime}$ that gets a piece fully inside $e$ we could
hypothetically ensure this via the constraint

$u_{a^{\prime}}(e)\cdot\delta_{e}\geq\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a^{\prime}}(f)\cdot
x^{i}_{f}.$

However, we again do not know the agents that are assigned a piece fully
inside $e$. Unfortunately, while for two edges $e$ and $f$ it was not too
difficult to define and identify envy-critical agents and write linear
constraints only for those, when comparing the envy of agents fully assigned
to $e$ towards an agent $a\in A_{V}$ that receives multiple pieces of edges,
the notion of “envy-criticality” we need depends on the size of the pieces $a$
gets from each edge. In particular, there is no fixed total ordering of the
agents that allows us to define envy-criticality. To give a concrete example
of this issue, for two different instantiations of the $x^{i}_{f}$ variables,
say $x^{i}_{f}:=c^{i}_{f}$ and $x^{i}_{f}:=d^{i}_{f}$, and two agents $a_{1}$
and $a_{2}$ it may hold that

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{1}}(f)\cdot
c^{i}_{f}}{u_{a_{1}}(e)}\geq\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{2}}(f)\cdot
c^{i}_{f}}{u_{a_{2}}(e)},$

but

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{1}}(f)\cdot
d^{i}_{f}}{u_{a_{1}}(e)}\leq\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{2}}(f)\cdot
d^{i}_{f}}{u_{a_{2}}(e)}.$

On the other hand, the assignment $\pi_{\mathrm{SOL}}$ does define some
specific instantiation of $x^{i}_{e}$’s for which there is a (not necessarily
strict) total ordering on the agents $a^{\prime}$ in $A$ capturing how “close”
they are to envying $a$, i.e., based on the value of

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a^{\prime}}(f)\cdot
x^{i}_{f}}{u_{a^{\prime}}(e)}.$

While we have no way of computing which total ordering arises from the
hypothetical assignment $\pi_{\mathrm{SOL}}$, we will later (in Lemma 12) use
Proposition 2 to show that only $|A|^{\mathcal{O}(k)}$ many such orderings are
possible, and moreover that we can enumerate all of these in time
$|A|^{\mathcal{O}(k)}$. For now, let us complete the description of the LP
with this in mind. Since the number of relevant orderings is bounded by
$|A|^{\mathcal{O}(k)}$, we can apply branching to guess the ordering that
arises from a hypothetical targeted assignment. At that point we can also
guess, for each edge $e$ and agent $a\in A_{V}$, the _envy-critical_
(according to this ordering) agent $\alpha_{e,a}$ that is assigned to the edge
$e$ and envies the agent $a$ the most—and later use this guess to preclude
some agents from being fully assigned to $e$.

For each guess, we add constraints to the LP which will ensure that the guess
will be consistent with whatever solution the LP produces. In particular, we
add the constraint

$u_{a^{\prime}}(e)\cdot\delta_{e}\geq\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a^{\prime}}(f)\cdot
x^{i}_{f}$ (9)

for every agent $a^{\prime}$ that envies $a$ at most as much as $\alpha_{e,a}$
according to the guessed ordering. More precisely, with each guess we will get
some instantiation $x^{i}_{e}=y^{i}_{e}$ witnessing this guess, and we will
insert a copy of Constraint 9 for every agent $a^{\prime}$ satisfying the
following property:

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{\alpha_{e,a}}(f)\cdot
y^{i}_{f}}{u_{\alpha_{e,a}}(e)}\geq\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a^{\prime}}(f)\cdot
y^{i}_{f}}{u_{a^{\prime}}(e)}.$ (B)

Our last task in this step is to provide a way to perform the branching over
total orders described above. Recall that each instantiation of the variables
$x_{e}^{i}$, for $i\in\\{0,1\\}$ and $e\in E(G)$, gives rise to a set of total
orderings of all agents in $A$. In particular, each ordering is associated
with precisely one pair $(a\in A_{V},e\in E(G))$. Here, each ordering captures
the relative envy towards $a$ under the assumption that the agents would be
assigned to $e$ (see Inequality B). We call a set of such orderings a
_portfolio_. Moreover, since $\pi_{\mathrm{SOL}}$ also corresponds to an
instantiation of the variables $x_{e}^{i}$, it too gives rise to a set of
total orderings, which we call a _portfolio of_ $\pi_{\mathrm{SOL}}$.

######  Lemma 12.

It is possible to construct, in time $A^{\mathcal{O}(k)}$, a set $\mathcal{R}$
of at most $k^{k}A^{\mathcal{O}(k)}$-many portfolios which is guaranteed to
contain the portfolio of $\pi_{\mathrm{SOL}}$.

###### Proof.

Let $V=\mathbb{R}^{2k}$ be an algebraic set defined by the constant zero
polynomial in variables $x^{i}_{e}$, for all $e\in E(G)$ and $i\in\\{0,1\\}$,
and let us define the set $\mathcal{P}$ of $k\cdot|A|^{3}$ many polynomials in
these variables. Namely for each edge $e\in E(G)$, agent $a\in A_{V}$, and
pair of agents $a_{1},a_{2}\in A$, let $P^{(e,a)}_{(a_{1},a_{2})}=$

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{1}}(f)\cdot
x^{i}_{f}}{u_{a_{1}}(e)}-\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{2}}(f)\cdot
x^{i}_{f}}{u_{a_{2}}(e)}.$

Note that

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{1}}(f)\cdot
x^{i}_{f}}{u_{a_{1}}(e)}>\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{2}}(f)\cdot
x^{i}_{f}}{u_{a_{2}}(e)}$

if and only if $\operatorname{sign}(P^{(e,a)}_{a_{1},a_{2}}(\vec{x}))=1$,

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{1}}(f)\cdot
x^{i}_{f}}{u_{a_{1}}(e)}=\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{2}}(f)\cdot
x^{i}_{f}}{u_{a_{2}}(e)}$

if and only if $\operatorname{sign}(P^{(e,a)}_{a_{1},a_{2}}(\vec{x}))=0$, and
$\operatorname{sign}(P^{(e,a)}_{a_{1},a_{2}}(\vec{x}))=-1$ otherwise. The
assignment $\pi_{\mathrm{SOL}}$ gives concrete values for $x^{i}_{e}$’s and
hence defines some point $w$ in $\mathbb{R}^{2k}$. Depending on the values of
the polynomials $P^{(e,a)}_{a_{1},a_{2}}$ in $w$, the point $w$ defines a sign
vector $\sigma$. The set of all points that define the same sign vector
$\sigma$ is a cell of $\mathcal{P}$ over $\mathbb{R}^{2k}$; observe that each
sign vector completely describes one possible ordering of the agents w.r.t.
these inequalities (or, equivalently, Inequality B).

Proposition 2 provides an algorithm that computes a point in each cell of
$\mathcal{P}$ over $V$ in time $k^{k}|A|^{\mathcal{O}(k)}$, which immediately
gives the same upper bound on the number of cells. Since $w$ is a point in
some cell, one of the points identified by the algorithm is in the same cell
as $w$ and defines the same sign vector $\sigma$. ∎

To formalize the description provided earlier, we now branch over all at most
$k^{k}|A|^{\mathcal{O}(k)}$ many portfolios obtained from Lemma 12, or
equivalently, points in the described metric space. Given some point
$y\in\mathbb{R}^{2k}$, we guess for each pair of edge $e\in E(G)$ and agent
$a\in A_{V}$ an agent $a_{e,a}$ as described above and introduce the LP
instance constraints described in (9). Finally, similarly as after introducing
Constraints (8), we can again check that the intended meaning of guessed
agents for each edge $e$ hold by checking Inequalities (A) and (B) for every
pair of agents guessed for each edge $e$. If at least one of the inequalities
do not hold, then we reject the branch. This finishes the construction of the
LP instance.

Bipartite Matching. Now, we can solve each LP instance in at most cubic time
Cohen et al. (2019). If the instance is unsatisfiable, then the algorithm
rejects this branch and continues to the next one. Else, given an LP solution
$x$, we can assign the values for the agents that we already guessed. Namely
for each agent $a\in A_{V}$, we let

$\pi(a)={\kern-5.0pt}\bigcup_{(e,0)\in\operatorname{Pieces}_{a}}{\kern-5.0pt}\\{(e,[0,x^{0}_{e}])\\}\cup{\kern-5.0pt}\bigcup_{(e,1)\in\operatorname{Pieces}_{a}}{\kern-5.0pt}\\{(e,[1-x^{1}_{e},1])\\}.$

Every other agent $a$ that we identified via a guess was fully assigned to
some particular edge $e$. Moreover, by Constraint 5, we can split the interval
$[x^{0}_{e},1-x^{1}_{e}]$ into $n_{e}$ pieces of length $\delta_{e}$; note
that if $n_{e}>0$ then $\delta_{e}$ cannot be equal to $0$. Let
$I_{a}\subseteq[x^{0}_{e},x^{1}_{e}]$ be any of the pieces that has not been
assigned to another agent yet and let $\pi(a)=(e,I_{a})$.

Finally, we are left with some unassigned agents and some unassigned pieces of
the graph, each consisting of a single piece of an edge. Since,
$|A_{V}|+\sum_{e\in E(G)}n_{e}=|A|$, the number of unsigned pieces equals the
number of unassigned agents. Moreover, since at this point we have a concrete
partition, for every pair of agent $a$ and piece $(e,I)$ we can in polynomial
time check whether $a$ would envy a piece in the partition or not (since this
check can be performed without knowing the assignments of the other agents);
in the former case we say that $a$ is _compatible_ with $(e,I)$, and otherwise
we say that they are _incompatible_. We can thus create an auxiliary bipartite
graph $H=(X\uplus Y,F)$ such that each vertex in $X$ is identified with an
unassigned agent, each vertex in $Y$ is identified with an unassigned piece,
and there is an edge between an agent $a\in X$ and a piece $(e,I)\in Y$ if and
only if they are compatible. We compute a maximum matching $M$ in $H$ using,
e.g., the Hopcroft-Karp algorithm in time at most $\mathcal{O}(|A|^{3})$. If
$M$ is not a perfect matching, then we reject the branch of our algorithm and
try another branch. Else for each unassigned agent $a$, we let $\pi(a)=M(a)$,
where $M(a)$ denotes the piece $(e,I)\in Y$ matched with the agent $a\in X$ by
the matching $M$. In this case the algorithm outputs Yes and optionally also
the assignment $\pi$ as a witness. If none of the branches lead to a positive
outcome, the algorithm outputs No.

This concludes the description of the algorithm, and we now proceed to
establishing its correctness.

######  Lemma 13.

If the above algorithm outputs an assignment $\pi$, then the assignment $\pi$
is envy-free.

###### Proof.

For the ease of presentation, we assume that for $i\in\\{0,1\\}$ and $e\in
E(G)$, $x^{i}_{e}$ and $\delta_{e}$ are the values of the same-name variables
that are output of the LP solver in the branch that leads to the assignment
$\pi$. By the construction of the assignment $\pi$ we have that for every
agent $a\in A_{V}$

$u_{a}(\pi(a))=\sum_{(e,i)\in\operatorname{Pieces}_{a}}u_{a}(e)\cdot
x^{i}_{e},$

and every other agent $a\in A\setminus A_{V}$ gets a piece that is fully
inside some edge $e$ and has length $\delta_{e}$, hence

$u_{a}(\pi_{a})=u_{a}(e)\cdot\delta_{e}.$

The fact that for every $(e,i)$, $e\in E(G)$ and $i\in\\{0,1\\}$, we guessed
an agent in $A_{V}$, that $|A_{V}|+\sum_{e\in E(G)}n_{e}=|A|$, and that all
constraints of type (5) are satisfied implies that $\pi(A)$ is indeed a
partition of $G$. Constraints of type (6) and (7) guarantee that the agents in
$A_{V}$ do not envy any other agent. Moreover, because for every edge and a
pair of agents assigned to that edge in our guessing part we check that
Inequalities (A) and (B) and because Constraints (8) and (9) are satisfied, we
get that all agents (partially) assigned in our branching phase do not envy
any other agent. Finally, all remaining agents are assigned by the matching
algorithm, which pairs them only with pieces they value the most and hence
none of the agents assigned by the matching algorithm envies any other agent.
∎

######  Lemma 14.

If $\mathcal{I}$ admits an envy-free assignment $\pi_{\mathrm{SOL}}$, then the
above algorithm will output an envy-free assignment.

###### Proof.

We will first describe the branch of our algorithm that corresponds to the
assignment $\pi_{\mathrm{SOL}}$, explain why we do not reject this branch and
show that the LP we obtain in this branch has a solution. Afterwards, we show
that any solution to this LP leads to an envy-free assignment.

Given $\pi_{\mathrm{SOL}}$, we can find the set of agents $A_{V}$ that get the
endpoint pieces of each edge as well as for each agent $a\in A_{V}$ we know
precisely which endpoint the agents gets. For agent $a\in A_{V}$ we denote by
$\operatorname{Pieces}_{a}$, in the same way as in the description of the
algorithm, the set of pairs $(e,i)$ such that if $i=0$, then
$\pi_{\mathrm{SOL}}(a)$ contains piece $(e,[0,c])$, for some $c\in[0,1]$, and
if $i=1$, then $\pi_{\mathrm{SOL}}(a)$ contains piece $(e,[d,1])$, for some
$d\in[0,1]$. Note that in one of the branches of our algorithm, we get
precisely same set of agents $A_{V}$ with precisely same
$\operatorname{Pieces}_{a}$ for each agent $a\in A_{V}$. Moreover, each of
agents induces a connected subset of $G$, hence we did not rejected the branch
for connectivity reasons. Given this pieces, we can already assign the values
for $x^{i}_{e}$’s in the LP instance. If $(e,0)\in\operatorname{Pieces}_{a}$
and $(e,[0,c])$ is a piece in $\pi_{\mathrm{SOL}}(a)$ such that $c\neq 1$,
then we let $x^{0}_{e}=c$, otherwise if $c=1$, then we let
$x^{0}_{e}=\frac{1}{2}$. Similarly, if $(e,1)\in\operatorname{Pieces}_{a}$ and
$(e,[c,1])$ is a piece in $\pi_{\mathrm{SOL}}(a)$ such that $c\neq 0$, then we
let $x^{1}_{e}=1-c$, otherwise if $c=0$, then we let $x^{1}_{e}=\frac{1}{2}$.
Note that

$u_{a}(\pi_{\mathrm{SOL}}(a))=\sum_{(e,i)\in\operatorname{Pieces}_{a}}u_{a}(e)\cdot
x^{i}_{e}.$

Now, for each edge $e\in E(G)$, we let $n_{e}$ be the number of agents that,
according to $\pi_{\mathrm{SOL}}$, get a piece fully inside the edge $e$ that
does not contain any endpoint of $e$. By Observation 11, all such pieces have
the same length and we let $\delta_{e}$ denote the length of the interval in
such piece. For technical reasons, if $n_{e}=0$, we let $\delta_{e}=0$. For
any agent $a$ that gets a piece fully inside the edge $e$ we get

$u_{a}(\pi_{\mathrm{SOL}}(a))=\delta_{e}\cdot u_{a}(e).$

Observe that in one of our branches we guessed precisely same numbers of
agents per edge and $|A_{V}|+\sum_{e\in E(G)}n_{e}=|A|$, so we did not reject
this branch. Moreover, since $\pi_{\mathrm{SOL}}$ is envy-free assignment and
every agent values the whole graph $1$, then each agent gets a non-trivial
piece. Hence, the given assignment of $x^{i}_{e}$’s and $\delta_{e}$’s satisfy
all constraints of type (4). Since $\pi_{\mathrm{SOL}}(A)$ is a partition of
$G$, we get also that the constraint (5) is satisfied for every edge $e$.
Since $\pi_{\mathrm{SOL}}(A)$ is envy-free, we get that all constraints of
types (6) and (7) are satisfied. Now for an ordered pair of edges $(e,f)$, if
$n_{e}\geq 1$, then there is an agent $a_{(e,f)}$ that minimizes the value of
the fraction $\frac{u_{a_{(e,f)}}(e)}{u_{a_{(e,f)}}(f)}$ among all the agents
assigned a piece fully inside $e$. Note that this agent might not be unique as
several agents might have the same value of the fraction, however in one of
the branches we guessed the agents $a_{(e,f)}$ among the ones that minimizes
the fraction. Since $\pi_{\mathrm{SOL}}$ is envy-free, all constraints of type
(8) are satisfied. Moreover, in a correct branch we also satisfy all
inequalities of type (A), so we do not reject this branch because of some
inequality of type (A). Finally, the $x^{i}_{e}$’s define a point in
$\mathbb{R}^{2k}$ that belong to some cell of $\mathcal{P}=\bigcup_{e\in
E(G),a\in A_{V},a_{1},a_{2}\in A}\\{P^{(e,a)}_{a_{1},a_{2}}\\}$ over
$\mathbb{R}^{2k}$. The algorithm branches over all cells of $\mathcal{P}$ that
contain a point and hence we branch on some point defined by $y^{i}_{e}$’s
from the same cell as $x^{i}_{e}$. It follows that for each agent $a\in
A_{V}$, every edge $e\in E(G)$ and every pair of agents $a_{1},a_{2}$ we get

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{1}}(f)\cdot
x^{i}_{f}}{u_{a_{1}}(e)}\geq\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{2}}(f)\cdot
x^{i}_{f}}{u_{a_{2}}(e)}$

if and only if

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{1}}(f)\cdot
y^{i}_{f}}{u_{a_{1}}(e)}\geq\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{2}}(f)\cdot
y^{i}_{f}}{u_{a_{2}}(e)}.$

Now, for each edge $e\in E(G)$ such that $n_{e}\geq 1$ and each agent $a\in
A_{V}$, there is an agent $a_{e,a}$ that maximizes the fraction

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{e,a}}(f)\cdot
x^{i}_{f}}{u_{a_{e,a}}(e)}$

among all the agents that are assigned a piece fully inside $e$. Since agent
$a_{e,a}$ is assigned a piece fully inside $e$ by $\pi_{\mathrm{SOL}}$, we get
that

$u_{a_{e,a}}(e)\cdot\delta_{e}\geq\sum_{(f,i)\in\operatorname{Pieces}_{a}}u_{a_{e,a}}(f)\cdot
x^{i}_{f}.$

It follows that in the branch where we guessed $a_{e,a}$ correctly all agents
that satisfy the inequality (B) also satisfy the constraint (9) and all
constraints of type (9) are satisfied. Moreover, in the correct branch, we do
not reject the branch because of inequalities of types (A) and (B). It follows
that the branch of our algorithm described above is not rejected and the LP we
obtain in branch has a solution.

Now let us take any solution to the LP obtained in the branch described above
and define the assignment $\pi$ as in our algorithm. It remains to show that
the matching instance admits a perfect matching. Since, it is a solution, it
is easy to see that under this assignment the agents in $A_{V}$ do not envy
any other agent. Similarly, all the agents that we guessed in our branching do
not envy any other piece. Note that all agents assigned the piece so far get
the same ”kind” of a piece as they get by $\pi_{\mathrm{SOL}}$. It remains to
show that if agent $a\in A$ gets a piece fully inside an edge $e\in E(G)$
according to $\pi_{\mathrm{SOL}}$, then the auxiliary bipartite graph
$H=(X\uplus Y,F)$ that our algorithm constructs contains an edge between $a$
and all pieces fully inside $e$. That is we need to check that assigning the
agent $a$ to the piece fully inside $e$ does not cause envy. First note for
every $a^{\prime}\in A_{V}$, the agent $a$ satisfies the inequality

$\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a^{\prime}}}u_{a_{e,a^{\prime}}}(f)\cdot
y^{i}_{f}}{u_{a_{e,a^{\prime}}}(e)}\geq\frac{\sum_{(f,i)\in\operatorname{Pieces}_{a^{\prime}}}u_{a}(f)\cdot
y^{i}_{f}}{u_{a}(e)},$

by the choice of the agent $a_{e,a^{\prime}}$ and hence the LP instance
contains the constraint

$u_{a}(e)\cdot\delta_{e}\geq\sum_{(f,i)\in\operatorname{Pieces}_{a^{\prime}}}u_{a}(f)\cdot
x^{i}_{f},$

therefore, $a$ does not envy any piece of an agent in $A_{V}$. Now, for an
edge $f$, we know that

$\frac{u_{a}(e)}{u_{a}(f)}\geq\frac{u_{a_{(e,f)}}(e)}{u_{a_{(e,f)}}(f)},$

by the choice of the agent $a_{(e,f)}$, and that the LP instance contains a
constraint

$u_{a_{(e,f)}}(e)\cdot\delta_{e}\geq u_{a_{(e,f)}}(f)\cdot\delta_{f}.$

Therefore,

$u_{a}(e)\cdot\delta_{e}\geq u_{a}(f)\cdot\delta_{f}$

and $a$ would not envy a piece inside $f$. It follows that an agent $a$ that
is assigned a piece fully inside $e$ by $\pi_{\mathrm{SOL}}$ can be assigned a
piece fully inside $e$ by $\pi$ as well and $H$ admits a perfect matching. ∎

######  Lemma 15.

The runtime of the above algorithm is $|A|^{\mathcal{O}(k^{2})}$.

###### Proof.

All operations such as adding a constraints in LP instance, checking the
consistency of the instance, solving LP, creating the auxiliary graph $H$ and
finding maximum size matching in $H$ can be done in polynomial time. Moreover,
we can enumerate points in all cells of $\mathcal{P}$ over $\mathbb{R}^{2k}$
in $|A|^{\mathcal{O}(k)}$ time. Hence, to get running time
$|A|^{\mathcal{O}(k^{2})}$, it suffices to upper bound the number of branches
by $|A|^{\mathcal{O}(k^{2})}$. We first branch for each endpoint of an edge
for the agent that gets this endpoints. This is $|A|^{2k}$ many branches. For
each branch we then branch for each edge on the number of agents that are
assigned a piece fully inside the edge. This is $(|A|+1)^{k}$ many branches.
Afterwards, we branch for each pair of edges $e,f$ on the agent $a_{(e,f)}$.
This is $|A|^{k^{2}}$ many branches. In each branch we run the algorithm from
Proposition 2 and branch on $|A|^{\mathcal{O}(k)}$ many points in
$\mathbb{R}^{2k}$. This is $|A|^{\mathcal{O}(k)}$ many branches. Finally in
each branch, we branch on agents $a_{e,a}$, this is at most $|A|^{2k^{2}}$
many branches (as $|A_{V}|\leq 2k$). Therefore, the total number of branches
is

$|A|^{2k}\cdot(|A|+1)^{k}\cdot|A|^{k^{2}}\cdot|A|^{\mathcal{O}(k)}\cdot|A|^{2k^{2}}=|A|^{\mathcal{O}(k^{2})}.\qed$

The proof of Theorem 10 follows immediately from Lemmas 13-15.

##  5 Concluding Remarks

Our results provide a significantly improved understanding of the classical
complexity of envy-free graph cutting. One direction that may be of interest
for future work is to analyze the complexity of this problem through the more
refined _parameterized complexity_ paradigm. Indeed, in that setting the
algorithmic results presented here can be viewed as algorithms. An immediate
question in this context is whether these results can be strengthened to show
fixed-parameter tractability. Most prominently, is there a fixed-parameter
algorithm for EF-GC parameterized by the number of edges?

For the special case where the underlying graph is a path, the complexity of
the problem is an even more intriguing question. As EF-GC on a path is a
special case of EF Contiguous Cake Cutting, we know that it always admits a
solution and hence the decision version of the problem cannot be [1]-hard (for
any parameterization). If the problem of computing an envy-free solution does
not admit a fixed-parameter algorithm, would showing this require a variation
of the -hierarchy tailored specifically to TFNP problems Megiddo and
Papadimitriou (1991)?

## Acknowledgements

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

## References

  * Abebe et al. [2017] Rediet Abebe, Jon Kleinberg, and David C. Parkes.  Fair division via social comparison.  In AAMAS, page 281–289, 2017.
  * Alman and Williams [2021] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539, 2021.
  * Arunachaleswaran et al. [2019] Eshwar Ram Arunachaleswaran, Siddharth Barman, Rachitesh Kumar, and Nidhi Rathi.  Fair and efficient cake division with connected pieces.  In WINE, pages 57–70, 2019.
  * Aumann and Dombb [2015] Yonatan Aumann and Yair Dombb.  The efficiency of fair division with connected pieces.  ACM TEAC, 3(4):1–16, 2015.
  * Aziz et al. [2018] Haris Aziz, Sylvain Bouveret, Ioannis Caragiannis, Ira Giagkousi, and Jérôme Lang.  Knowledge, fairness, and social constraints.  In AAAI, number 1, 2018.
  * Balkanski et al. [2014] E. Balkanski, S. Brânzei, D. Kurokawa, and A. Procaccia.  Simultaneous cake cutting.  In AAAI, pages 566–572, 2014.
  * Basu et al. [2006] Saugata Basu, Richard Pollack, and Marie-Françoise Roy.  Algorithms in Real Algebraic Geometry.  Springer-Verlag, 2006.
  * Bei and Suksompong [2021] Xiaohui Bei and Warut Suksompong.  Dividing a graphical cake.  In AAAI, pages 5159–5166, 2021.
  * Bei et al. [2017] Xiaohui Bei, Youming Qiao, and Shengyu Zhang.  Networked fairness in cake cutting.  In IJCAI, pages 3632–3638, 2017.
  * Bei et al. [2019] Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong.  Connected fair allocation of indivisible goods.  arXiv preprint arXiv:1908.05433, 2019.
  * Bei et al. [2020] Xiaohui Bei, Xiaoming Sun, Hao Wu, Jialin Zhang, Zhijie Zhang, and Wei Zi.  Cake cutting on graphs: A discrete and bounded proportional protocol.  In SODA, pages 2114–2123, 2020.
  * Bei et al. [2021] Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong.  The price of connectivity in fair division.  In AAAI, pages 5151–5158, 2021.
  * Bilò et al. [2021] Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S Zwicker.  Almost envy-free allocations with connected bundles.  Games and Economic Behavior, 2021.
  * Bouveret et al. [2017] Sylvain Bouveret, Katarína Cechlárová, Edith Elkind, Ayumi Igarashi, and Dominik Peters.  Fair division of a graph.  In IJCAI, pages 135–141, 2017.
  * Brams and Taylor [1996] Steven J Brams and Alan D Taylor.  Fair Division: From cake-cutting to dispute resolution.  Cambridge University Press, 1996.
  * Brânzei and Miltersen [2015] Simina Brânzei and Peter Bro Miltersen.  A dictatorship theorem for cake cutting.  In IJCAI, pages 482–488, 2015.
  * Brânzei and Nisan [2017] Simina Brânzei and Noam Nisan.  Communication complexity of cake cutting.  arXiv preprint arXiv:1709.09876, 2017.
  * Brânzei and Nisan [2019] Simina Brânzei and Noam Nisan.  Communication complexity of cake cutting.  In EC, page 525, 2019.
  * Caragiannis et al. [2011] Ioannis Caragiannis, John K. Lai, and Ariel D. Procaccia.  Towards more expressive cake cutting.  In IJCAI, pages 127–132, 2011.
  * Chevaleyre et al. [2017] Yann Chevaleyre, Ulle Endriss, and Nicolas Maudet.  Distributed fair allocation of indivisible goods.  Artificial Intelligence, 242:1–22, 2017.
  * Cohen et al. [2019] Michael B. Cohen, Yin Tat Lee, and Zhao Song.  Solving linear programs in the current matrix multiplication time.  In STOC, pages 938–942, 2019.
  * Cohler et al. [2011] Yuga J. Cohler, John K. Lai, David C. Parkes, and Ariel D. Procaccia.  Optimal envy-free cake cutting.  In AAAI, 2011.
  * Deligkas et al. [2021] Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak.  The parameterized complexity of connected fair division.  In IJCAI, pages 139–145, 2021.
  * Deng et al. [2012] Xiaotie Deng, Qi Qi, and Amin Saberi.  Algorithmic solutions for envy-free cake cutting.  Operations Research, 60(6):1461–1476, 2012.
  * Diestel [2012] Reinhard Diestel.  Graph Theory, 4th Edition.  Graduate texts in mathematics. Springer, 2012.
  * Dubins and Spanier [1961] Lester E Dubins and Edwin H Spanier.  How to cut a cake fairly.  The American Mathematical Monthly, 68(1P1):1–17, 1961.
  * Eiben et al. [2020] Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak.  Parameterized complexity of envy-free resource allocation in social networks.  In AAAI, pages 7135–7142, 2020.
  * Elkind et al. [2021a] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong.  Graphical cake cutting via maximin share.  In IJCAI, pages 161–167, 2021.
  * Elkind et al. [2021b] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong.  Keep your distance: Land division with separation.  In IJCAI, pages 168–174, 2021.
  * Elkind et al. [2021c] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong.  Mind the gap: Cake cutting with separation.  In AAAI, pages 5330–5338, 2021.
  * Goldberg et al. [2020] Paul Goldberg, Alexandros Hollender, and Warut Suksompong.  Contiguous cake cutting: Hardness results and approximation algorithms.  Journal of Artificial Intelligence Research, 69:109–141, 2020.
  * Hosseini et al. [2020] Hadi Hosseini, Ayumi Igarashi, and Andrew Searns.  Fair division of time: Multi-layered cake cutting.  In IJCAI, pages 182–188, 2020.
  * Igarashi and Meunier [2021] Ayumi Igarashi and Frédéric Meunier.  Envy-free division of multi-layered cakes.  CoRR, abs/2106.02262, 2021.
  * Igarashi and Peters [2019] Ayumi Igarashi and Dominik Peters.  Pareto-optimal allocation of indivisible goods with connectivity constraints.  In AAAI, pages 2045–2052, 2019.
  * Kurokawa et al. [2013] David Kurokawa, John K. Lai, and Ariel D. Procaccia.  How to cut a cake before the party ends.  In AAAI, 2013.
  * Lipton et al. [2004] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In EC, pages 125–131, 2004.
  * Marenco and Tetzlaff [2014] Javier Marenco and Tomás Tetzlaff.  Envy-free division of discrete cakes.  Discrete Applied Mathematics, 164:527–531, 2014.
  * Megiddo and Papadimitriou [1991] Nimrod Megiddo and Christos H. Papadimitriou.  On total functions, existence theorems and computational complexity.  Theor. Comput. Sci., 81(2):317–324, 1991.
  * Menon and Larson [2017] Vijay Menon and Kate Larson.  Deterministic, strategyproof, and fair cake cutting.  In IJCAI, pages 352–358, 2017.
  * Moulin [2004] Hervé Moulin.  Fair division and collective welfare.  MIT press, 2004.
  * Procaccia [2013] Ariel D Procaccia.  Cake cutting: Not just child’s play.  Commun. of the ACM, 56(7):78–87, 2013.
  * Robertson and Webb [1998] Jack Robertson and William Webb.  Cake-cutting algorithms: Be fair if you can.  CRC Press, 1998.
  * Seddighin et al. [2019] Masoud Seddighin, Majid Farhadi, Mohammad Ghodsi, Reza Alijani, and Ahmad S Tajik.  Expand the shares together: Envy-free mechanisms with a small number of cuts.  Algorithmica, 81(4):1728–1755, 2019.
  * Segal-Halevi and Suksompong [2021] Erel Segal-Halevi and Warut Suksompong.  How to cut a cake fairly: A generalization to groups.  Am. Math. Mon., 128(1):79–83, 2021.
  * Segal-Halevi et al. [2016] Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann.  Waste makes haste: bounded time algorithms for envy-free cake cutting with free disposal.  Transactions on Algorithms, 13(1):1–32, 2016.
  * Simonov et al. [2019] Kirill Simonov, Fedor V. Fomin, Petr A. Golovach, and Fahad Panolan.  Refined complexity of PCA with outliers.  In ICML, pages 5818–5826, 2019.
  * Stromquist [1980] Walter Stromquist.  How to cut a cake fairly.  Am. Math. Mon., 87(8):640–644, 1980.
  * Su [1999] Francis Edward Su.  Rental harmony: Sperner’s lemma in fair division.  Am. Math. Mon., 106(10):930–942, 1999.
  * Suksompong [2019] Warut Suksompong.  Fairly allocating contiguous blocks of indivisible items.  Discrete Applied Mathematics, 260:227–236, 2019.
  * Warren [1968] Hugh E. Warren.  Lower bounds for approximation by nonlinear manifolds.  Transactions of the American Mathematical Society, 133(1):167–178, 1968.