11institutetext: Institute of Mathematical Sciences, HBNI, Chennai 11email:
<EMAIL_ADDRESS>
22institutetext: Indian Institute of Technology Jodhpur 22email:
<EMAIL_ADDRESS>
33institutetext: University of Bergen, Norway

# How to assign volunteers to tasks compatibly ? A graph theoretic and
parameterized approach

Sushmita Gupta 11 Pallavi Jain 22 Saket Saurabh 1133

###### Abstract

In this paper we study a resource allocation problem that encodes correlation
between items in terms of conflict and maximizes the minimum utility of the
agents under a conflict free allocation. Admittedly, the problem is
computationally hard even under stringent restrictions because it encodes a
variant of the Maximum Weight Independent Set problem which is one of the
canonical hard problems in both classical and parameterized complexity.
Recently, this subject was explored by Chiarelli et al. [Algorithmica’22] from
the classical complexity perspective to draw the boundary between NP-hardness
and tractability for a constant number of agents. The problem was shown to be
hard even for small constant number of agents and various other restrictions
on the underlying graph. Notwithstanding this computational barrier, we notice
that there are several parameters that are worth studying: number of agents,
number of items, combinatorial structure that defines the conflict among the
items, all of which could well be small under specific circumstancs. Our
search rules out several parameters (even when taken together) and takes us
towards a characterization of families of input instances that are amenable to
polynomial time algorithms when the parameters are constant. In addition to
this we give a superior $2^{m}|I|^{\mathcal{O}(1)}$ algorithm for our problem
where $m$ denotes the number of items that significantly beats the exhaustive
$\mathcal{O}(m^{m})$ algorithm by cleverly using ideas from FFT based fast
polynomial multiplication; and we identify simple graph classes relevant to
our problem’s motivation that admit efficient algorithms.

###### Keywords:

Conflict free allocation fair allocation job scheduling independent set
parameterized complexity.

##  1 Introduction

Imagine a situation where we are running a non-profit organization that
specialises in volunteer work. Specifically, our objective is to bundle the
tasks that need to be completed and pair them with the available volunteer
workers in some meaningful way. Naturally, the volunteer workers have some
preference over the available tasks and the tasks may have some inherent
compatibility issues in that a person may only be assigned to at most one of
the tasks that are mutually incompatible. The incompatibility among the tasks
could be due to something as simple as the time interval in which they have to
be performed. While it would be ideal to assign all the tasks, it may not
actually be possible due to the above compatibility issues and the number of
available workers. Moreover, this being a volunteer operation, the workers are
"paid" by the satisfaction they derive from completing the bundle of tasks
assigned to them. Thus, we want to ensure that the assignment is done in way
that gives every volunteer worker the highest level of satisfaction possible.
This is the setting of the job assignment problem studied in this article.

The above described scenario falls under the more general topic of resource
allocation which is a central topic in economics and computation. Resource
allocation is an umbrella term that captures a plethora of well-known problem
settings where resources are matched to agents in a meaningful way that
respects the preferences/choices of agents, and when relevant, resources as
well. Stable matching, generalized assignment, fair division, are some well-
known problems that fall under the purview of resource allocation. These
topics are extensively studied in economics, (computational) social choice
theory, game theory, and computer science, to name a few; and are incredibly
versatile and adaptable to a wide variety of terminology, techniques and
traditions.

A well-known framework within which resource allocation is studied is in the
world of Job Scheduling problems on non-identical machines. In this scenario,
the machines are acting as agents and the jobs are the tasks such that certain
machines are better suited for some jobs than others and this variation is
captured by the "satisfaction level" of the machine towards the assigned jobs.
Moreover, the jobs have specific time intervals within which they have to be
performed and only one job can be scheduled on a machine at a time. Thus, the
subset of jobs assigned to a single machine must respect these constraints,
and the objective can be both maximization and minimization as well as to
simply test feasibility. Results on the computational aspect of resource
allocation that incorporate interactions and dependencies between the
resources is relatively few. This is the backdrop of our work in this article.
A rather inexhaustive but representative list of papers that take a
combinatorial approach in analysing a resource allocation problem and are
aligned with our work in this paper is [6, 4, 27, 15, 3, 1, 7, 31, 32]. In
particular, we can point to the decades old work of Deuermeyer et. al [12]
that studies a variant of Job Scheduling in which they goal is to assign a set
of independent jobs to identical machines in order to maximize the minimal
completion time of the jobs. Their NP-hardness result for two machines (i.e
two agents in our setting) is an early work with similar flavor. They analyse
a well-known heuristic called the LPT-algoirthm to capture best-case
performance and show that its worst case performance is 4/3-factor removed
from optimum. The more recent work of Chiarelli et. al [7] that studies "fair
allocation" of indivisible items into pairwise disjoint subsets items that
maximimizes the minimum satisfaction of the agents is the work that is closest
to ours. They too consider various graph classes that capture compatibilities
among items and explore the classical complexity boundary between strong NP-
hardness and pseudo-polynomial tractability for a constant number of agents.
Our analysis probes beyond the NP-hardness of these problems and explores this
world from the lens of parameterized complexity, thereby drawing out the
suitability of natural parameters–such as the number of agents, the number of
jobs, the maximum size of each allocated "bundle", and the structural
parameters of the underlying graph–towards yielding polynomial time algorithms
when the parameters take on constant values.

We formally model our setting by viewing it is a two-sided matching market
where each worker (i.e an agent) has a utility function defined over the set
of available tasks (call them jobs) such that their satisfaction for a bundle
of jobs is the sum of the agents’ utilities for each individual job in the
bundle. The incompatibilities among the jobs is captured by a graph
$\mathcal{H}$ defined on the set of jobs such that an edge represents
conflict. The overall objective is to assign bundles–pairwise disjoint subset
of jobs that induce an independent set in $\mathcal{H}$ (i.e have no edges
among each other)–to agents such that the minimum satisfaction of the agents
is maximized. To make our discussion concrete, we formally define the
computational problem under study.

Conflict free Fair Allocation (CFFA) Input: A set of agents $\mathcal{A}$, a
set of jobs $\mathcal{I}$, utility function ${\rm
u}_{a}\colon\mathcal{I}\rightarrow\mathbb{N}$, for each agent
$a\in\mathcal{A}$, a positive integer $\eta\in\mathbb{N}$; and a graph
$\mathcal{H}$ with vertex set $\mathcal{I}$. Question: Does there exist a
function $\phi\colon\mathcal{A}\rightarrow 2^{\mathcal{I}}$ such that for
every $a\in\mathcal{A}$, $\phi(a)$ is an independent set in $\mathcal{H}$,
$\sum_{x\in\phi(a)}{\rm u}_{a}(x)\geq\eta$, and
$\phi(a)\cap\phi(a^{\prime})=\emptyset$ for all
$\\{a,a^{\prime}\\}\subseteq\mathcal{A}$?

For each $a\in\mathcal{A}$, we call $\phi(a)$ a bundle assigned to the agent
$a$. We call graph $\mathcal{H}$ the conflict graph.

As alluded to earlier, Deurmeyer et al. [12] studied CFFA with a different
name and showed that the problem is NP-complete even for $2$ agents and even
when $\mathcal{H}$ is edgeless (that is, no conflict). Since the problem
statement has a conflict graph and we need the subsets of allocated resources
to be an independent set in $\mathcal{H}$, naturally, the classical Maximum
Weight Independent Set (MWIS) problem comes into play. In this problem given a
graph $G$, a weight function $w:V(G)\rightarrow\mathbb{N}$, and an integer
$\eta$, the objective is to test whether there exists an independent set $S$
such that $w(S)=\sum_{v\in S}w(v)\geq\eta$. Let $\mathcal{G}$ be a family of
graphs. Chiarelli et al. [7] showed that if MWIS is NP-complete on
$\mathcal{G}$, then CFFA is NP-complete, when $\mathcal{H}$ belongs to the
graph class $\mathcal{G}$, even when there is one agent. Consequently, it is
natural to focus on graph classes in which MWIS is polynomial-time solvable.
However, [7] proves that CFFA remains NP-complete even for bipartite graphs
and their line graphs. Some polynomial time algorithms for special instances
of the problem and polynomial time approximation algorithms are known for the
problem [12, 24]. Some papers that have used conflict graphs to capture
various constraints on items/jobs that are related to compatibility are [11,
16, 17, 5].

###  1.1 Our Results and Methods

As described above we formulate our question in graph theoretic terms and
analyze the problem in the realm of parameterized complexity. We note that
this is a natural choice of algorithmic toolkit for our problem because CFFAis
naturally governed by several parameters such as the number of agents
(${\sf\\#agents}$), the number of jobs (${\sf\\#{jobs}}$), the maximum size of
a bundle (${\sf bundleSize}$) in the solution, and the utility of any agent
$\eta$. This makes it a natural candidate for a study from the viewpoint of
parameterized complexity. Moreover, we also note that for certain specific
situations the job graph may have special structures that can be exploited for
designing efficient algorithms. In what follows, we describe certain scenarios
where the “small-ness" of the parameters and the underlying graph structure
comes into focus and allows us to discuss our results more concretely.

Input/Output Parameters. The first set of parameters, that we study, consists
of $n={\sf\\#agents}$, $m={\sf\\#{jobs}}$, $s={\sf bundleSize}$, and $\eta$.
With this set of parameters, we obtain the following set of results.

Brief overview of parameterized complexity: The goal of parameterized
complexity is to find ways of solving NP-hard problems more efficiently than
exhaustive search: the aim is to restrict the combinatorial explosion to a
parameter that is likely to much smaller than the input size in families of
input instances. Formally, a parameterization of a problem is assigning an
integer $k$ to each input instance of the problem. We say that a parameterized
problem is fixed-parameter tractable (FPT) if there is an algorithm that
solves the problem in time $f(k)\cdot|I|^{\mathcal{O}(1)}$, where $|I|$ is the
size of the input and $f$ is an arbitrary computable function depending on the
parameter $k$ only. A more general class of parameterized algorithm is the XP
algorithms where a parameterized problem is slicewise poly (XP) if there is an
algorithm that solves the problem in time $|I|^{f(k)}$, where $|I|$ is the
size of the input and $f$ is an arbitrary computable function depending on the
parameter $k$ only. Moreover, we will refer to such algorithms as an FPT
(resp. XP) algorithm and the problem to have an ${\sf FPT}(k)$ (resp. ${\sf
XP}(k)$) algorithm. For more details on the subject, we refer to the textbooks
[8, 18, 14].

Graph classes under investigation: We begin our discussion describing the
simple graph classes that bookend our parameterized study: the two extremes
are utopia and chaos and in between we have potentially an infinite
possibility of graph classes in which to study our problem. In Section 1.2 we
delve deeper into what parameters are meaningful for further study and draw
out the connections between the graph classes and fruitful parameterization.

  1. 1.

Utopia: when there are no incompatibilities, and the conflict graph
$\mathcal{H}$ is edgeless. In this scenario the problem is hard even when
bundle size is a small constant, Theorem 3.1.

  2. 2.

Chaos: when every job is incompatible with every other job, and so conflict
graph $\mathcal{H}$ is complete. In this scenario, the problem becomes rather
easy to solve since each bundle can only be of size at most one, Theorem 1.3.

  3. 3.

Incompatibilities are highly localized: $\mathcal{H}$ is a cluster graph, a
graph that is compromised of vertex disjoint cliques. Such a situation may
occur quite naturally such as in the following scenario.

In the example of the assignment of volunteers to tasks, consider the
situation where the tasks can only be completed on specific days and specific
times. Consequently, all the tasks that can be completed on day 1 form a
clique, the ones for day 2 form another clique and so on. Moreover, the
volunteers are working after hours for say two hours each day and it has been
decided that each worker can only work for the same number of hours each day
to manage their work load. In this scenario a worker can be assigned at most
task per day. This is the intuitive basis for the algorithm described in
Theorems 1.4 and 1.5 and Proposition 1.

  4. 4.

“distance” $t$ away from chaos: $\mathcal{H}$ has at least ${m\choose 2}-t$
edges, Theorems 1.6, 1.7 and 1.8.

If not a constant, it is reasonable to expect these parameters to be fairly
small compared to the input.

###  1.2 Closer look at the parameters and search for fruitful graph families

I. (Superior) ${\sf FPT}(m)$ algorithm exists:

We note that CFFA admits a trivial FPT algorithm parameterized by $m$ by
enumerating all possible $(n+1)^{m}$ ways of assigning the jobs to the agents,
where each job has $(n+1)$ choices of agents to choose from. Since $m\geq n$,
we get a running time of $\mathcal{O}(m^{m})$. However, in Section 2 we
present an algorithm with running time $2^{m}(n+m)^{\mathcal{O}(1)}$, which is
clearly far superior. It is an algebraic algorithm that recasts the problem as
that of of polynomial multiplication that mimics subset convolution. This
suggests, in contrast to no ${\sf FPT}(n)$ algorithm, that the larger
parameter $m$ is sufficient in constraining the (exponential growth in the)
time complexity as function of itself.

II. No ${\sf XP}(n)$ algorithm exists:

We first note that since CFFA is NP-complete even for one agent (due to the
reduction from MWIS by Chiarelli et. al [7]), hence, we cannot even hope for
an $(n+m)^{f(n)}$ time algorithm for any function $f$, unless P=NP. Thus,
there is no hope for an FPT algorithm with respect to $n$. This appears to be
a confirmation that the number of agents (volunteers) which is likely to
smaller than the number of jobs (tasks) is inadequate in terms of expressing
the (exponential growth in the) time complexity as a function of itself.

III. No ${\sf XP}(s)$ algorithm when $\mathcal{H}$ is edgeless:

In Section 3 we show that CFFA is NP-complete when $\mathcal{H}$ is edgeless
and $s=3$. This implies that we cannot even hope for an $(n+m)^{g(s)}$ time
algorithm for any function $g$, unless P=NP.

Therefore, $n$ and $s$ are inadequate parameters individually, hence it is
natural to consider them together.

IV. When both $n$ and $s$ are small:

We note that $n$ and $s$ being small valued compared to $m$ is quite realistic
because there are likely to be far too many tasks at hand but relatively fewer
volunteers; and the assignment should not overburden any of them and thus the
number of assigned tasks should be small. This motivates us to consider the
parameter $n+s$.

However, hoping that CFFA is FPT parameterized by $n+s$ in general graphs is
futile because the problem generalizes the MWIS problem. Hence, we can only
expect to obtain an ${\sf FPT}(n+s)$ algorithm for special classes of graphs.
Consequently, our exploration moves towards identifying graph classes which
may admit such an algorithm.

Towards that we note that an ${\sf FPT}(n+s)$ algorithm for the underlying
decision problem that incorporates the bundle size $s$ (defined formally
below) yields an ${\sf FPT}(n+s)$ algorithm for CFFA.

Size bounded-Conflict free Fair Allocation (Sb-CFFA) Input: A set of agents
$\mathcal{A}$, a set of jobs $\mathcal{I}$, utility function ${\rm
u}_{a}\colon\mathcal{I}\rightarrow\mathbb{N}$, for each agent
$a\in\mathcal{A}$, positive integers $s,\eta\in\mathbb{Z}_{>0}$, and a graph
$\mathcal{H}$ with vertex set $\mathcal{I}$. Question: Does there exist a
function $\phi\colon\mathcal{A}\rightarrow 2^{\mathcal{I}}$ such that for
every agent $a\in\mathcal{A}$, bundle $\phi(a)$ is an independent set in
$\mathcal{H}$, $|\phi(a)|\leq s$, $\sum_{x\in\phi(a)}{\rm u}_{a}(x)\geq\eta$,
and $\phi(a)\cap\phi(a^{\prime})=\emptyset$ for all
$\\{a,a^{\prime}\\}\subseteq\mathcal{A}$?

To elaborate further, an FPT algorithm for Sb-CFFA would imply an FPT
algorithm for CFFA, because $s\leq m$ and an algorithm that makes subroutine
calls to an ${\sf FPT}(n+s)$ algorithm for Sb-CFFA for increasing values of
$s$ (from $1$ to $m$) is an ${\sf FPT}(n+s)$ algorithm for CFFA. Hence, from
now we focus our attention towards an ${\sf FPT}(n+s)$ algorithm for Sb-CFFA
for reasonable graph classes.

$\star$ Two parameters $n$, $s$ in search of a graph family: A closer look at
the hardness proof of CFFA from MWIS by Chiarelli et. al [7] yields a hardness
result for Sb-CFFA from a size bounded version of MWIS, defined below. Note
that in this problem the size of the (independent set) solution is upper
bounded by the parameter and this distinguishes it from the (standard) maximum
weight independent set solution.

Size bounded-Maximum Weight Independent Set (Sb-MWIS) Input: A graph $G$,
positive integers $k$ and $\rho$, a weight function
$w:V(G)\rightarrow\mathbb{N}$. Parameter: $k$ Question: Does there exist an
independent set $S$ of size at most $k$ such that $\sum_{v\in S}w(v)\geq\rho$?

In that reduction, $s=k$ and $n=1$. Hence, we can deduce the following
connection: any ${\sf FPT}(n+s)$ algorithm for Sb-CFFA will yield an ${\sf
FPT}(k)$ algorithm for Sb-MWIS; and conversely, any hardness result that holds
for Sb-MWIS with respect to $k$ must also hold for Sb-CFFA with respect to
$n+s$. The latter condition allows us to narrow down the potential graph
classes that admit an ${\sf FPT}(n+s)$ algorithm for Sb-CFFA. Since Sb-MWIS is
a clear generalization (by setting $\rho=k$ and unit weight function) of the
Independent Set problem, a very well-studied problem in the realm of
parameterized complexity and indeed the wider field of graph algorithms. This
connection allows us to demarcate the tractability border of our problem Sb-
CFFA via the computational landscape of Independent Set. In the paragraphs to
follow we will flesh out the connection in more explicit terms and derive a
result, Theorem 1.1, that tightly characterises the tractability boundary of
Sb-CFFA with respect to $n+s$.

$\star$ Independent Set as the guiding light for Sb-CFFA: In the field of
parameterized complexity Independent Set has been extensively studied on
families of graphs that satisfy some structural properties. We take the same
exploration path for our problem Sb-CFFA. The graph classes in which
Independent Set has an ${\sf FPT}(k)$ algorithm is a potential field for an
FPT algorithms for Sb-CFFA. While this is not a guarantee, and we need to
argue the connection precisely.

Let $\mathcal{G}$ be a family of hereditary graphs. That is, if
$G\in{\mathcal{G}}$, then all induced subgraphs of $G$ belong to
$\mathcal{G}$. In other words, $\mathcal{G}$ is closed under taking induced
subgraphs.

For a hereditary family $\mathcal{G}$, ${\mathcal{G}}$-Sb-MWIS denotes the
restriction of Sb-MWIS where the input graph $G\in\mathcal{G}$. Thus, a
natural question is what happens when Sb-CFFA is restricted to a graph class
for which ${\mathcal{G}}$-Sb-MWIS is fixed parameter tractable with respect to
$k$? Given a hereditary family $\mathcal{G}$, we define ${\mathcal{G}}$-Sb-
CFFA similarly to Sb-CFFA such that the graph $\mathcal{H}$ belongs to the
family $\mathcal{G}$. Tthe tractability of ${\mathcal{G}}$-Sb-MWIS does not
immediately imply tractability of ${\mathcal{G}}$-Sb-CFFA. Indeed, even if
${\mathcal{G}}$-Sb-MWIS is FPT when parameterized by $k$, we cannot hope for
an $(n+m)^{f(n)}$ time algorithm for ${\mathcal{G}}$-Sb-CFFA for any function
$f$, unless P=NP, because the NP-hardness of Independent Set implies the NP-
hardness for CFFA even for one agent, i.e $n=1$. Due to Theorem 1.4 (explained
later), we also cannot hope for an $(n+m)^{f(s)}$ time algorithm for
${\mathcal{G}}$-Sb-CFFA for any function $f$, unless P=NP, even if
${\mathcal{G}}$-Sb-MWIS has an ${\sf FPT}(k)$ algorithm. These results imply
that we cannot even expect ${\mathcal{G}}$-Sb-CFFA to have an XP algorithm
with respect to either $n$ or $s$ individually, let alone an FPT algorithm.
However, the following result completely characterizes the parameterized
complexity of ${\mathcal{G}}$-Sb-CFFA with respect to $n+s$ vis-a-vis the
parameterized complexity of ${\mathcal{G}}$-Sb-MWIS with respect to $k$.

###### Theorem 1.1

Let $\mathcal{G}$ be a hereditary family of graphs. Then, ${\mathcal{G}}$-Sb-
CFFA is FPT parameterized by $n+s$ if and only if ${\mathcal{G}}$-Sb-MWIS is
FPT parameterized by $k$.

Theorem 1.1 implies that ${\mathcal{G}}$-Sb-CFFA is FPT when $\mathcal{G}$ is
the family of interval graphs, chordal graphs, perfect graphs, planar graphs,
bipartite graphs, graphs of bounded degeneracy, to name a few, [20].

Overview of Theorem 1.1. This is one of the main algorithmic results of this
article. The result is obtained by combining the classical color coding
technique of Alon-Yuster-Zwick [2], applied on the set of jobs, together with
a dynamic programming algorithm to find a “colorful solution”. In the dynamic
programming phase of the algorithm, we invoke an ${\sf FPT}(k)$ algorithm for
${\mathcal{G}}$-Sb-MWIS.

While there are papers that study hereditary graph classes to give FPT
algorithms for MWIS (the standard maximum weighted independent set) problem
[10], we are not aware of known classes of graphs for which Sb-MWIS (the size
bounded variant of maximum weighted independent set problem) is FPT
parameterized by $k$. Hence, we first identify some such graph classes.

We define an independence friendly class as follows. Let
$f\colon\mathbb{N}\to\mathbb{N}$ be a monotonically increasing function, that
is, invertible. A graph class $\mathcal{G}$ is called $f$-independence
friendly class ($f$-ifc) if $\mathcal{G}$ is hereditary and for every
$G\in\mathcal{G}$ of size $n$ has an independent set of size $f(n)$. Observe
that the families of bipartite graphs, planar graphs, graphs of bounded
degeneracy, graphs excluding some fixed clique as an induced subgraphs are
$f$-independence friendly classes with appropriate function $f$. For example,
for bipartite graphs $f(n)=\nicefrac{{n}}{{2}}$ and for $d$-degenerate graphs
$f(n)=\nicefrac{{n}}{{(d+1)}}$. For graphs excluding some fixed clique as an
induced subgraph, we can obtain the desired $f$ by looking at Ramsey numbers.
It is the minimum number of vertices, $n=R(r,s)$, such that all undirected
simple graphs of order $n$, contain a clique of size $r$, or an independent
set of size $s$. It is known to be upper bounded by
$R(r,s)\leq\binom{r+s-2}{r-1}$ [25]. We prove the following result for
${\mathcal{G}}$-Sb-MWIS when $\mathcal{G}$ is $f$-ifc.

###### Theorem 1.2

Let $\mathcal{G}$ be an $f$-independence friendly class. Then, there exists an
algorithm for ${\mathcal{G}}$-Sb-MWIS running in time
$\mathcal{O}((f^{-1}(k))^{k}\cdot(n+m)^{\mathcal{O}(1)})$.

We also give a polynomial-time algorithm for ${\mathcal{G}}$-Sb-MWIS when
$\mathcal{G}$ is a cluster graph. In contrast, CFFA is NP-hard when the
conflict graph is a cluster graph as proved in Theorem 1.4.

Finally, we show that Sb-CFFA is W$[1]$-hard with respect to $n+s+\eta$. We
reduce it from the Independent Set problem. Given an instance $(G,k)$ of the
Independent Set, we can construct an instance of CFFA with only one agent,
jobs as $V(G)$, unit utility function, $\mathcal{H}=G$, and $s=\eta=k$. Since
Independent Set is W$[1]$-hard [13], we get the following.

###### Observation 1

Sb-CFFA is W$[1]$-hard with respect to $n+s+\eta$.

Next, we move to our next set of parameters.

###  1.3 Structural Parameterization via graph classes.

Our next set of results is motivated by the following result whose proof is in
Section 4.

###### Theorem 1.3

There exists an algorithm that solves CFFA in polynomial time when the
conflict graph is a complete graph.

Contrastingly, we show that when conflict graph is edgeless, the problem is
computationally hard even when bundles are size at most three, Theorem 3.1.

This result leads us to asking if what happens if incompatibilities are highly
localized:

Does CFFA admit a polynomial time algorithm when $\mathcal{H}$ is a disjoint
union of cliques?

We answer this question negatively by proving the following result, which is
due to a reduction from Numerical 3-Dimensional Matching.

###### Theorem 1.4

CFFA is NP-complete even when $\mathcal{H}$ is a cluster graph comprising of
$3$ cliques.

Since, an edgeless graph is also a cluster graph, due to [12], we have the
following.

###### Proposition 1

CFFA is NP-complete even for $2$ agents when $\mathcal{H}$ is a cluster graph.

Next, we design a polynomial-time algorithm when a cluster graph contains $2$
cliques and the utility functions are _uniform_ , i.e., utility functions are
the same for all the agents. In particular, we prove the following result.

###### Theorem 1.5

There exists an algorithm that solves CFFA in polynomial time when the
conflict graph is a cluster graph comprising of $2$ cliques and the utility
functions are uniform.

Proofs of Theorems 1.4 and 1.5 are in Section 4.1. In light of Theorem 1.3,
the distance of a graph from a complete graph is a natural parameter to study
in parameterized complexity. The distance function can be defined in several
ways. We define it as follows: the number of edges, say $t$, whose addition
makes the graph a complete graph. We first show a result that gives a
subexponential time algorithm when the number of agents is constant.

###### Theorem 1.6

There exists an algorithm that solves CFFA in $\mathcal{O}((2t\cdot
2^{2\sqrt{t}}+1)^{n}(n+m)^{\mathcal{O}(1)})$ time, where
$t=\binom{m}{2}-|E(\mathcal{H})|$ denotes the number of edges when added to
$\mathcal{H}$ yields a complete graph.

Theorem 1.6 is obtained by showing that if a graph $G$ can be made into a
clique by adding at most $t$ edges then the number of independent sets of size
at least $2$ is upper bounded by $\mathcal{O}(2t\cdot 2^{2\sqrt{t}})$.
However, it is not an FPT algorithm parameterized by $t$ alone. To show that
the problem is FPT parameterized by $t$, we obtain the following result.

###### Theorem 1.7

There exists an algorithm that solves CFFA in
$\mathcal{O}((2t)^{t+1}(n+m)^{\mathcal{O}(1)})$ time.

In light of Theorem 1.3, we know that CFFA is polynomial-time solvable when
every vertex has degree $m-1$. Next, we show that the problem is also
polynomial-time solvable when every vertex has degree $m-2$ and the utility
functions are uniform.

###### Theorem 1.8

There exists an algorithm that solves CFFA in polynomial time when every
vertex in the conflict graph has degree $m-2$ and the utility functions are
uniform.

Proofs of Theorems 1.6, 1.7 and 1.8 are in Section 4.2.Table 1 summarises all
our results.

Utility Functions | Arbitrary | Uniform | Arbitrary
---|---|---|---
Parameters $\mathcal{G}$ | Arbitrary | Complete | Cluster | Cluster | Regular | ${\mathcal{G}}$-Sb-MWIS is
| 2 cliques | (degree $\\!m-2$) |  FPT wrt $k$
$n=$#agents | [12] | Thm. 1.3 | Obs. 1 | Thm. 1.5 | Thm. 1.8 | [12]
$s=$ bundleSize |  Thm. 3.1 |  |  Thm. 1.4 |  |  | Thm. 3.1
$\eta$ | Obs. 1 |  | ? |  |  | ?
${\sf\\#agents}+{\sf bundleSize}$ | Obs. 1 |  |  Thm.1.1 |  |  |  Thm. 1.1
${\sf\\#agents}+{\sf bundleSize}+\eta$ | Obs. 1 |  |  |  |  |
$m={\sf\\#{jobs}}$ | Thm. 2.1 |  |  |  |  |
$t={m\choose 2}-|E(\mathcal{H})|$ |  Thm. 1.7 |  |  |  |  |
Table 1: Summary of our results of CFFA, where the conflict graph belong to
the family $\mathcal{G}$. Lavender cells denote polynomial time complexity;
green cells and  pink cells denote that the problem is FPT and W-hard w.r.t.
the parameter in col 1, respectively; white cells with ? mark denote that the
complexity is open; and  yellow cells denote that the respective parameters
are not interesting as the problem is either FPT w.r.t. smaller parameter or
for more general graph class.

##  2 CFFA: A single exponential FPT parameterized by ${\sf\\#{jobs}}$

In this section, we will prove that CFFA is FPT when parameterized by the
number of jobs, $m$. The algorithm will use the technique of polynomial
multiplication and fast Fourier transformation. The idea is as follows. For
every agent $i\in\mathcal{A}$, we first construct a family of bundles that can
be assigned to the agent $i$ in an optimal solution. Let us denote this family
by $\mathcal{F}_{i}$. Then, our goal is to find $n$ disjoint bundles, one from
each set $\mathcal{F}_{i}$. To find these disjoint sets efficiently, we use
the technique of polynomial multiplication.

Before we discuss our algorithm, we have to introduce some notations and
terminologies. Let $\mathcal{I}$ be a set of size $m$, then we can associate
$\mathcal{I}$ with $[m]$. The characteristic vector of a subset
$S\subseteq[m]$, denoted by $\chi(S)$, is an $m$-length vector whose
$i^{\text{th}}$ bit is $1$ if and only if $i\in S$. Two binary strings of
length $m$ are said to be disjoint if for each $i\in[m]$, the $i^{th}$ bits in
the two strings are different. The Hamming weight of a binary string $S$,
denoted by $H(S)$, is defined to be the number of $1$s in the string $S$. A
monomial $y^{i}$ is said to have Hamming weight $w$, if the degree $i$ when
represented as a binary string has Hamming weight $w$.

We begin with the following observation.

###### Observation 2

Let $S_{1}$ and $S_{2}$ be two binary strings of same length. Let
$S=S_{1}+S_{2}$. If $H(S)=H(S_{1})+H(S_{2})$, then $S_{1}$ and $S_{2}$ are
disjoint binary vectors.

The following is due to Cygan et. al [9].

###### Proposition 2

Let $S=S_{1}\cup S_{2}$, where $S_{1}$ and $S_{2}$ are two disjoint subsets of
$[m]$. Then, $\chi(S)=\chi(S_{1})+\chi(S_{2})$ and
$H(\chi(S))=H(\chi(S_{1}))+H(\chi(S_{2}))=|S_{1}|+|S_{2}|$.

Observation 2 and Proposition 2 together yield the following.

###### Corollary 1

Subsets $S_{1},S_{2}\subseteq\mathcal{I}$ are disjoint if and only if Hamming
weight of the monomial $x^{\chi(S_{1})+\chi(S_{2})}$ is $|S_{1}|+|S_{2}|$.

The Hamming projection of a polynomial $p(y)$ to $h$, denoted by
$H_{h}(p(y))$, is the sum of all the monomials of $p(y)$ which have Hamming
weight $h$. We define the representative polynomial of $p(y)$, denoted by
$\mathcal{R}(p(y))$, as the sum of all the monomials that have non-zero
coefficient in $p(y)$ but have coefficient $1$ in $\mathcal{R}(p(y))$, i.e.,
it ignores the actual coefficients and only remembers whether the coefficient
is non-zero. We say that a polynomial $p(y)$ contains a monomial $y^{i}$ if
the coefficient of $y^{i}$ is non-zero. The zero polynomial is the one in
which the coefficient of each monomial is $0$.

Now, we are ready to discuss our algorithm.

###### Theorem 2.1

CFFA is solvable in $\mathcal{O}(2^{m}(n+m)^{\mathcal{O}(1)})$ time, where
$m={\sf\\#{jobs}}$ and $n={\sf\\#agents}$.

###### Proof

Let $\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},\eta)$ denote an instance of CFFA. We
start by defining a set family indexed by the agents. Let $\mathcal{A}=[n]$.
For an agent $i\in\mathcal{A}$, let $\mathcal{F}_{i}$ contain each of subsets
of $\mathcal{I}$ that can be feasibly allocated to $i$ as a bundle.
Specifically, a set $S\subseteq\mathcal{I}$ is in $\mathcal{F}_{i}$ if $S$ is
an independent set in $\mathcal{H}$ and the utility $\sum_{x\in S}{\rm
u}_{i}(x)\geq\eta$. We define the round inductively as follows.

For round $1$ and a positive integer $s$, we define a polynomial

$p^{1}_{s}(y)=\sum_{S\in\mathcal{F}_{1},\\\ |S|=s}y^{\chi(S)}$

For round $i\in[n]\setminus\\{1\\}$, and a positive integer $s$, we define a
polynomial by using the $\mathcal{R}(\cdot)$ operator

$p^{i}_{s}(y)=\sum_{\begin{subarray}{c}S\in\mathcal{F}_{i}\\\
s^{\prime}=s-|S|\end{subarray}}\mathcal{R}\left(H_{s}\left(p^{i-1}_{s^{\prime}}(y)\times
y^{\chi(S)}\right)\right)$

The algorithm returns “yes” if for any positive integer $s\in\mathbb{Z}_{\geq
0}$, $p^{n}_{s}(y)$ is non-zero. In fact, any non-zero monomial in the
polynomial “represents” a solution for the instance $\mathscr{J}$ such that we
can find the bundle to assign to each agent $i\in\mathcal{A}$ by backtracking
the process all the way to round 1.

Computing a solution (if it exists). We assume that for some positive integer
$s$, $p^{n}_{s}(y)$ is a non-zero polynomial. Thus, it contains a non-zero
monomial of the form $p^{n-1}_{s^{\prime}}(y)\times y^{\chi(S)}$, where
$S\in\mathcal{F}_{n}$. Note that $\chi(S)$ describes the bundle assigned to
agent $n$, the set $S$. Since the monomial $p^{n-1}_{s^{\prime}}(y)\times
y^{\chi(S)}$ exists in the polynomial $p^{n}_{s}(y)$ after applying
$H_{s}(\cdot)$ function, it must be that
$p^{n-1}_{s^{\prime}}(y)=y^{\chi(S^{\prime})}$ for some set
$S^{\prime}\subseteq\mathcal{I}$ such that $S^{\prime}\cap S=\emptyset$. By
recursively applying the same argument to the polynomial
$p^{n-1}_{s^{\prime}}(y)$, we can obtain the bundles that are allocated to the
agents $i=n-1,\ldots,1$.

###### Lemma 1

The above algorithm returns “yes” if and only if $\mathscr{J}$ is a yes-
instance of CFFA.

###### Proof

Suppose that $\mathscr{J}$ is a yes-instance of CFFA. Then, there is an
assignment, i.e., an injective function $\phi$ that maps $\mathcal{A}$ to
subsets of $\mathcal{I}$. For each agent $i\in\mathcal{A}$, we define
$S_{i}=\phi(i)$. We begin with the following claim that enables us to conclude
that the polynomial $p^{n}_{s}(y)$, where $s=\sum_{i\in[n]}|S_{i}|$, contains
the monomial $y^{\sum_{i\in[n]}\chi(S_{i})}$.

###### Claim 1

For each $j\in[n]$, the polynomial $p^{j}_{s}(y)$, where
$s=\sum_{i\in[j]}|S_{i}|$, contains the monomial
$y^{\sum_{i\in[j]}\chi(S_{i})}$.

###### Proof

The proof is by induction on $j$.

Base Case: $j=1$. We first note that $S_{1}$ is in the family
$\mathcal{F}_{1}$ as it is a feasible bundle for the agent $1$. Thus, due to
the construction of the polynomial $p^{1}_{s}(y)$, we know that
$p^{1}_{|S_{1}|}(y)$ contains the monomial $y^{\chi(S_{1})}$.

Induction Step: Suppose that the claim is true for $j=j^{\prime}-1$. We next
prove it for $j=j^{\prime}$. To construct the polynomial
$p^{j^{\prime}}_{s}(y)$, where $s=\sum_{i\in[j^{\prime}]}|S_{i}|$, we consider
the multiplication of polynomial $p^{j^{\prime}-1}_{s^{\prime}}(y)$, where
$s^{\prime}=\sum_{i\in[j^{\prime}-1]}|S_{i}|$, and $y^{\chi(S_{j^{\prime}})}$.
Due to the inductive hypothesis, $p^{j^{\prime}-1}_{s^{\prime}}(y)$, where
$s^{\prime}=\sum_{i\in[j^{\prime}-1]}|S_{i}|$, contains the monomial
$y^{\sum_{i\in[j^{\prime}-1]}\chi(S_{i})}$. Note that $S_{j^{\prime}}$ is in
the family $\mathcal{F}_{j^{\prime}}$ as it is a feasible bundle for the agent
$j^{\prime}$. Since $S_{j^{\prime}}$ is disjoint from $S_{1}\cup\ldots\cup
S_{j^{\prime}-1}$, due to Corollary 1, we can infer that
$p^{j^{\prime}}_{s}(y)$, where $s=\sum_{i\in[j^{\prime}]}|S_{i}|$, has the
monomial $y^{\sum_{i\in[j^{\prime}]}\chi(S_{i})}$.

Due to Claim 1, we can conclude that $p^{n}_{s}(y)$, where
$s=\sum_{i\in[n]}|S_{i}|$, contains the monomial
$y^{\sum_{i\in[n]}\chi(S_{i})}$. For the other direction, suppose that the
algorithm returns “yes”. Then, for some positive integer $s$, $p^{n}_{s}(y)$
is a non-zero polynomial. We need to show that there exists pairwise disjoint
sets $S_{1},\ldots,S_{n}$ such that $S_{i}\in\mathcal{F}_{i}$, where
$i\in[n]$. This will give us an assignment function $\phi$, where
$\phi(i)=S_{i}$. Since each $S\in\mathcal{F}_{i}$, where $i\in[n]$, is an
independent set and $\sum_{x\in S}{\rm u}_{i}(x)\geq\eta$, $\phi$ is a
feasible assignment. We next prove the following claim that enables us to
conclude the existence of pairwise disjoint sets.

###### Claim 2

For each $j\in[n]$, if the polynomial $p^{j}_{s}(y)$ is non-zero for some
$s\in[m]$, then there exists $j$ pairwise disjoint sets $S_{1},\ldots,S_{j}$
such that $S_{i}\in\mathcal{F}_{i}$, where $i\in[j]$.

###### Proof

We prove it by induction on $j$.

Base Case: $j=1$. Suppose $p^{1}_{s}(y)$ is non-zero for some $s\in[m]$. Then,
it contains a monomial $y^{\chi(S)}$, where $S\in\mathcal{F}_{1}$. Thus, the
claim is true.

Induction Step: Suppose that the claim is true for $j=j^{\prime}-1$. We next
prove it for $j=j^{\prime}$. Suppose that $p^{j^{\prime}}_{s}(y)$ is non-zero
for some $s\in[m]$. Then, it contains a monomial of the form
$p^{j-1}_{s^{\prime}}(y)\times y^{\chi(S)}$, where $|S|=s-s^{\prime}$ and
$S\in\mathcal{F}_{j^{\prime}}$. Due to induction hypothesis, since
$p^{j-1}_{s^{\prime}}(y)$ is a non-zero polynomial, there exists
$j^{\prime}-1$ pairwise disjoint sets $S_{1},\ldots,S_{j^{\prime}-1}$ such
that $S_{i}\in\mathcal{F}_{i}$, where $i\in[j^{\prime}-1]$. Furthermore, due
to Corollary 1, we have that $S_{j^{\prime}}$ is disjoint from
$S_{1}\cup\ldots\cup S_{j^{\prime}-1}$. Thus, we have $j^{\prime}$ pairwise
disjoint sets $S_{1},\ldots,S_{j^{\prime}}$ such that
$S_{i}\in\mathcal{F}_{i}$, where $i\in[j^{\prime}]$. ∎

This completes the proof. ∎

To claim the running time, we use the following well-known result about
polynomial multiplication.

######  Proposition 3 ([29])

There exists an algorithm that multiplies two polynomials of degree $d$ in
$\mathcal{O}(d\log d)$ time.

###### Lemma 2

This algorithm runs in $\mathcal{O}(2^{m}\cdot(n+m)^{\mathcal{O}(1)})$ time.

###### Proof

In the algorithm, we first construct a family of feasible bundles for each
agent $i\in\mathcal{A}$. Since we check all the subsets of $\mathcal{I}$, the
constructions of families takes
$\mathcal{O}(2^{m}\cdot(n+m)^{\mathcal{O}(1)})$ time. For $i=1$, we construct
$m$ polynomials that contains $\mathcal{O}(2^{m})$ terms. Thus, $p_{s}^{1}(y)$
can be constructed in $\mathcal{O}(2^{m}\cdot m)$ time. Then, we recursively
construct polynomials by polynomial multiplication. Since every polynomial has
degree at most $\mathcal{O}(2^{m})$, due to Proposition 3, every polynomial
multiplication takes $\mathcal{O}(2^{m}\cdot m)$ time. Hence, the algorithm
runs in $\mathcal{O}(2^{m}\cdot(n+m)^{\mathcal{O}(1)})$ time. ∎

Thus, the theorem is proved. ∎

##  3 CFFA: Parameterized by ${\sf\\#agents}$ and ${\sf bundleSize}$

In this section, we study CFFA parameterized by $n={\sf\\#agents}$, ${\sf
bundleSize}$, and their combinations. We first show some hardness results and
then complement it with our main algorithmic result.

###  3.1 NP-hardness when conflict graph is edgeless and bundle size is
bounded

Since CFFA is NP-hard for all the graph classes for which MWIS is NP-hard [7],
in this section, we first discuss the intractability of the problem for
special classes of graph when MWIS can be solved in polynomial time. In
particular, we show that the problem is NP-hard even when the conflict-graph
is edgeless and size of every bundle is at most $3$, which is due to the
reduction from the 3-Partition problem. In the 3-Partition problem, we are
given a set $X$ of $3\tilde{m}$ elements, a bound $B\in\mathbb{Z}_{+}$, and a
size $s(x)\in\mathbb{Z}_{+}$ for each $x\in X$ such that
$\nicefrac{{B}}{{4}}<s(x)<\nicefrac{{B}}{{2}}$ and $\sum_{x\in
X}s(x)=\tilde{m}B$. The goal is to decide whether there exists a partition of
$X$ into $\tilde{m}$ disjoint sets $X_{1},X_{2},\ldots,X_{\tilde{m}}$ such
that for each $1\leq i\leq\tilde{m}$, $\sum_{x\in X_{i}}s(x)=B$. Note that
each $X_{i}$ must contain three elements from $X$. To the best of our ability,
we could not find a citation for this result and hence we have included it
here for completeness.

###### Theorem 3.1

CFFA is NP-complete when $\mathcal{H}$ is edgeless and $s$ is three.

###### Proof

Given an instance $\mathscr{J}=(X,B,\\{s(x)\\}_{x\in X})$ of 3-Partition, we
create an instance $\mathscr{J^{\prime}}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},\eta=2B)$ of CFFA, where
$\mathcal{I}=X$ and $\mathcal{H}$ is an edgeless graph on the vertex set
$\mathcal{I}$. We define a set of agents
$\mathcal{A}=\\{a_{1},\ldots,a_{\tilde{m}}\\}$ and for each agent
$a_{i}\in\mathcal{A}$, we define the utility function ${\rm
u}_{a_{i}}(x)=B-s(x)$ for each job $x\in\mathcal{I}$. The intuition behind
this construction is that we want to create a bundle so that the utility
derived by an agent from that bundle is at least $2B$, which will be
attainable only if the bundle size is three.

Next, we prove the correctness of the reduction.

###### Lemma 3

$\mathscr{J}$ is a yes-instance of 3-Partition if and only if
$\mathscr{J}^{\prime}$ is a yes-instance of CFFA.

###### Proof

If $\mathscr{J}$ is a yes-instance of 3-Partition, then there is a solution
$X_{1},\ldots,X_{\tilde{m}}$ that satisfies the desired properties, i.e., for
each $1\leq i\leq\tilde{m}$, $\sum_{x\in X_{i}}s(x)=B$. Note that $\sum_{x\in
X_{i}}u_{a_{i}}(x)=3B-B=2B$. Thus, the assignment function $\phi$, where
$\phi(a_{i})=X_{i}$, yields a solution for $\mathscr{J}^{\prime}$.

For the other direction, let $\phi$ be a solution for $\mathscr{J}^{\prime}$.
That is, for each agent $a\in\mathcal{A}$, $\phi(a)$ is the bundle assigned to
the agent $a$. Thus, $\sum_{x\in\phi(a)}{\rm u}_{a}(x)\geq 2B$.

We claim that for each agent $a\in\mathcal{A}$, the bundle size $|\phi(a)|=3$.
If the size is at most two, then ${\rm u}_{a}(\phi(a))\leq
2B-\sum_{x\in\phi(a)}s(x)<2B$, since $\phi(a)$ is non-empty and for each
object $x\in\phi(a)$, $s(x)$ is positive by definition. This is a
contradiction. Hence, the only possibility is that for each agent
$a\in\mathcal{A}$, $|\phi(a)|\geq 3$. If for some agent $a\in\mathcal{A}$,
bundle $\phi(a)$ has more than three jobs, then for some agent $a^{\prime}\neq
a$, bundle $\phi(a^{\prime})$ will contain at most two jobs, and thus will not
attain the target. Hence, for each agent, the bundle size is exactly three.

Next, we claim that for each agent the utility of its bundle is exactly
$\eta$. Suppose that there is an agent $a\in\mathcal{A}$, such that utility of
its bundle, $\sum_{x\in\phi(a)}{\rm u}_{a}(x)>2B$. By definition,
$\sum_{x\in\phi(a)}{\rm u}_{a}(x)=3B-\sum_{x\in\phi(a)}s(x)$. Thus, it follows
that $\sum_{x\in\phi(a)}s(x)<B$. Since $\sum_{x\in X}s(x)=\tilde{m}B$, it must
be that $\sum_{x\in\mathcal{I}\setminus\phi(a)}s(x)>(\tilde{m}-1)B$. Moreover,
each bundle has size exactly three, and $\mathcal{I}\setminus\phi(a)$ has
$3(\tilde{m}-1)$ jobs, so there must exist a bundle $\phi(a^{\prime})$ for
some agent $a^{\prime}\neq a$ such that $\sum_{x\in\phi(a^{\prime})}s(x)>B$,
and so that agent’s utility ${\rm
u}_{a^{\prime}}(\phi(a^{\prime}))=3B-\sum_{x\in\phi(a^{\prime})}s(x)<2B$.
Hence, we have reached a contradiction. Thus, for every agent
$a\in\mathcal{A}$, the utility of its bundle is exactly $2B$.

We now note that we can form a solution for the instance $\mathscr{J}$ of
3-Partition by taking each of the three-set jobs constituting each bundle.
More specifically, for each $i\in[\tilde{m}]$, we define $X_{i}=\\{x\colon
x\in\phi(a_{i})\\}$. For each $i\in[\tilde{m}]$, since ${\rm
u}_{a_{i}}(x)=B-s(x)$, we have

$\begin{split}\sum_{x\in X_{i}}s(x)&=\sum_{x\in\phi(i)}(B-{\rm
u}_{a_{i}}(x))=3B-\sum_{x\in\phi(i)}{\rm u}_{a_{i}}(x)\\\
&=3B-2B=B\end{split}$

Hence, $\mathscr{J}$ is a yes-instance of 3-Partition. ∎

Thus, the theorem is proved. ∎

###  3.2 Proof of Theorem 1.1

In this section, we give the proof of Theorem 1.1. Let
$\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},s,\eta)$ be an instance of
${\mathcal{G}}$-Sb-CFFA, and let $|{\mathscr{J}}|$ denote the size of the
instance. We first prove the first part of Theorem 1.1, which is the easier
direction of the proof. In particular, let $\mathbb{A}$ be an FPT algorithm
for ${\mathcal{G}}$-Sb-CFFA, running in time
$f(n,s)|{\mathscr{J}}|^{\mathcal{O}(1)}$. Given an instance $(G,k,\rho,w)$ of
${\mathcal{G}}$-Sb-MWIS, we construct an instance
$\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},s,\eta)$ of ${\mathcal{G}}$-Sb-CFFA as
follows. The set of agents $\mathcal{A}$ has only one agent $a^{\star}$.
Further, $\mathcal{I}=V(G)$, ${\rm u}_{a^{\star}}=w$, $\mathcal{H}=G$, $s=k$,
and $\eta=\rho$. It is easy to see that $(G,k,\rho,w)$ is a yes-instance of
${\mathcal{G}}$-Sb-MWIS if and only if $\mathscr{J}$ is a yes-instance of
${\mathcal{G}}$-Sb-CFFA. Thus, by invoking algorithm $\mathbb{A}$ on instance
$\mathscr{J}$ of ${\mathcal{G}}$-Sb-CFFA, we get an FPT algorithm for
${\mathcal{G}}$-Sb-MWIS that runs in $f(k)|{\mathscr{J}}|^{\mathcal{O}(1)}$
time. This completes the proof in the forward direction. In the rest of the
section, we prove the reverse direction of the proof. That is, given an FPT
algorithm for ${\mathcal{G}}$-Sb-MWIS, we design an FPT algorithm for
${\mathcal{G}}$-Sb-CFFA. For ease of explanation, we first present a
randomized algorithm which will be derandomized later using the known tool of
$(p,q)$-perfect hash family [2, 19].

####  3.2.1 Randomized Algorithm

In this section, we design a randomized algorithm with the following
specification. If the input, $\mathscr{J}$, is a no-instance then the
algorithm always returns “no”. However, if the input, $\mathscr{J}$, is a yes-
instance then the algorithm returns “yes” with probability at least $1/2$.

Throughout this section, we assume that we have been given a yes-instance.
This implies that there exists a hypothetical solution
$\phi\colon\mathcal{A}\rightarrow 2^{\mathcal{I}}$. We define everything with
respect to $\phi$. That is, $\phi\colon\mathcal{A}\rightarrow 2^{\mathcal{I}}$
is an injective function satisfying all the requirements. Let
$S=\phi(\mathcal{A})=\cup_{a\in\mathcal{A}}\phi(a)$, i.e., the set of jobs
that are assigned to some agent. Further, note that $|S|\leq ns$, as the size
of each bundle is upper bounded by $s$. Our main idea is to first highlight
all the jobs in the set $S$, that are assigned to some agent, using color
coding.

Separation of jobs: Color the vertices of $\mathcal{H}$ uniformly and
independently at random using $ns$ colors, say $\\{1,\ldots,ns\\}$.

The goal of the coloring is that “with high probability”, we color the jobs
assigned to agents in a solution using distinct colors. The following
proposition bounds the success probability.

###### Proposition 4

[8, Lemma 5.4] Let $U$ be a universe and $X\subseteq U$. Let $\chi\colon
U\rightarrow[|X|]$ be a function that colors each element of $U$ with one of
$|X|$ colors uniformly and independently at random. Then, the probability that
the elements of $X$ are colored with pairwise distinct colors is at least
$e^{-|X|}$.

Due to Proposition 4, the coloring step of the algorithm colors the jobs in
$\phi(\mathcal{A})$ using distinct colors with probability at least $e^{-ns}$.
We call an assignment $\phi\colon\mathcal{A}\rightarrow 2^{\mathcal{I}}$ as
colorful if every two jobs $\\{i,i^{\prime}\\}\in\phi(A)$ get distinct color.
Moreover, for each $a$, $|\phi(a)|\leq s$.

Next, we find a colorful feasible assignment in the following lemma. Further,
let us assume that we have an FPT algorithm, $\mathbb{B}$, for
${\mathcal{G}}$-Sb-MWIS running in time $h(k)n^{\mathcal{O}(1)}$.

###### Lemma 4

Let $\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},s,\eta)$ be an instance of
${\mathcal{G}}$-Sb-CFFA and $\chi\colon V(\mathcal{H})\rightarrow[ns]$ be a
coloring function. Then, there exists a dynamic programming algorithm that
finds a colorful feasible assignment $\phi\colon\mathcal{A}\rightarrow
2^{\mathcal{I}}$ in $\mathcal{O}(3^{ns}\cdot h(s)\cdot(n+m)^{\mathcal{O}(1)})$
time, if it exists, otherwise, return “no”.

###### Proof

Let $\mathsf{colors}=\\{1,\ldots,ns\\}$ be the set of colors and let
$a_{1},\ldots,a_{n}$ be an arbitrary ordering of the agents. We apply dynamic
programming: for a non-empty set $S\subseteq\mathsf{colors}$ and $i\in[n]$, we
define the table entry $T[i,S]$ as $1$ if there is a colorful feasible
assignment of jobs (that are colored by the function $\chi$) using colors in
$S$ to agents $\\{a_{1},\ldots,a_{i}\\}$; otherwise it is $0$. For an agent
$a\in\mathcal{A}$ and $S\subseteq\mathsf{colors}$, let $\mathcal{H}_{a,S}$ be
a vertex-weighted graph constructed as follows. Let $V_{S}$ be the subset of
vertices in $\mathcal{H}$ that are colored using the colors in $S$. Then,
$\mathcal{H}_{a,S}=\mathcal{H}[V_{S}]$. The weight of every vertex
$x\in\mathcal{H}_{a,S}$ is ${\rm u}_{a}(x)$. For a vertex-weighted graph $G$,
let $\mathbb{I}(G)\in\\{0,1\\}$, where $\mathbb{I}(G)=1$ if there exists an
independent set of size at most $s$ and weight at least $\eta$ in $G$,
otherwise $0$. We compute $\mathbb{I}(G)$ using algorithm $\mathbb{B}$. We
compute the table entries as follows.

Base Case:  For $i=1$ and non-empty set $S$, we compute as follows:

$T[1,S]=\mathbb{I}(\mathcal{H}_{a_{1},S})$ (1)

Recursive Step:  For $i>1$ and non-empty set $S$, we compute as follows:

$T[i,S]=\bigvee_{\emptyset\neq S^{\prime}\subset
S}T[i-1,S^{\prime}]\wedge\mathbb{I}(\mathcal{H}_{a_{i},S\setminus
S^{\prime}})$ (2)

We return “yes” if $T[n,S]=1$ for some $S\subseteq\mathsf{colors}$, otherwise
“no”. Next, we prove the correctness of the algorithm. Towards this, we prove
the following result.

###### Claim 3

Equation 1 and Equation 2 correctly compute $T[i,S]$, for each $i\in[n]$ and
$\emptyset\neq S\subseteq\mathsf{colors}$.

###### Proof

We will prove it by induction on $i$. For $i=1$, we are looking for any
feasible assignment of jobs colored using the colors in $S$ to the agent
$a_{1}$. Thus, Equation 1 computes $T[1,S]$ correctly due to the construction
of the graph $\mathcal{H}_{a_{1},S}$ and the correctness of algorithm
$\mathbb{B}$.

Now, consider the recursive step. For $i>1$ and $\emptyset\neq
S\subseteq\mathsf{colors}$, we compute $T[i,S]$ using Equation 2. We show that
the recursive formula is correct. Suppose that Equation 2 computes
$T[i^{\prime},S]$ correctly, for all $i^{\prime}<i$ and $\emptyset\neq
S\subseteq\mathsf{colors}$. First, we show that $T[i,S]$ is at most the R.H.S.
of Equation 2. If $T[i,S]=0$, then the claim trivially holds. Suppose that
$T[i,S]=1$. Let $\psi$ be a colorful feasible assignment to agents
$\\{a_{1},\ldots,a_{i}\\}$ using jobs that are colored using colors in $S$.
Let $S_{j}\subseteq S$ be the set of colors of jobs in $\psi(a_{j})$, where
$j\in[i]$. Since $\psi(a_{i})$ uses the colors from the set $S_{i}$ and
$\sum_{x\in\psi(a_{i})}{\rm u}_{a_{i}}(x)\geq\eta$, due to the construction of
$\mathcal{H}_{a_{i},S_{i}}$, we have that
$\mathbb{I}(\mathcal{H}_{a_{i},S_{i}})=1$. Consider the assignment
$\psi^{\prime}=\psi|_{\\{a_{1},\ldots,a_{i-1}\\}}$ (restrict the domain to
$\\{a_{1},\ldots,a_{i-1}\\}$). Since $S_{i}$ is disjoint from
$S_{1}\cup\ldots\cup S_{i-1}$ due to the definition of colorful assignment,
$\psi^{\prime}$ is a feasible assignment for the agents
$\\{a_{1},\ldots,a_{i-1}\\}$ such that the color of all the jobs in
$\psi^{\prime}(\\{a_{1},\ldots,a_{i-1}\\})$ is in $S\setminus S_{i}$.
Furthermore, since $\psi$ is colorful, $\psi^{\prime}$ is also colorful.
Hence, $T[i-1,S\setminus S_{i}]=1$ due to induction hypothesis. Hence, R.H.S.
of Equation 2 is $1$. Thus, $T[i,S]$ is at most R.H.S. of Equation 2.

For the other direction, we show that $T[i,S]$ is at least R.H.S. of Equation
2. If R.H.S. is $0$, then the claim trivially holds. Suppose R.H.S. is $1$.
That is, there exists $S^{\prime}\subseteq S$ such that $T[i-1,S^{\prime}]=1$
and $\mathbb{I}(\mathcal{H}_{a_{i},S\setminus S^{\prime}})=1$. Let $\psi$ be a
colorful feasible assignment to agents $\\{a_{1},\ldots,a_{i-1}\\}$ using jobs
that are colored using colors in $S^{\prime}$. Since
$\mathbb{I}(\mathcal{H}_{a_{i},S\setminus S^{\prime}})=1$, there exists a
subset $X\subseteq V_{S\setminus S^{\prime}}$ such that $\sum_{x\in X}{\rm
u}_{a_{i}}(x)\geq\eta$. Thus, construct an assignment $\psi^{\prime}$ as
follows: $\psi^{\prime}(a)=\psi(a)$, if $a\in\\{a_{1},\ldots,a_{i-1}\\}$ and
$\psi^{\prime}(a_{i})=X$. Since $\psi^{\prime}$ is a feasible assignment and
$\mathbb{I}(\mathcal{H}_{a_{i},S\setminus S^{\prime}})=1$, $\psi$ is a
feasible assignment. Furthermore, since $\psi$ is colorful and
$\psi(\\{a_{1},\ldots,a_{i-1}\\})$ only uses colors from the set $S^{\prime}$,
$\psi^{\prime}$ is also colorful. Hence, $T[i,S]=1$. ∎

Due to Claim 3, $T[n,S]=1$ for some $S\subseteq\mathsf{colors}$ if and only if
$\mathscr{J}$ is a yes-instance of ${\mathcal{G}}$-Sb-CFFA. This completes the
proof of the lemma. ∎

Due to Proposition 4 and Lemma 4, we obtain an $\mathcal{O}(3^{ns}\cdot
h(s)\cdot(n+m)^{\mathcal{O}(1)})$ time randomized algorithm for
${\mathcal{G}}$-Sb-CFFA which succeeds with probability $e^{-ns}$. Thus, by
repeating the algorithm independently $e^{ns}$ times, we obtain the following
result.

###### Theorem 3.2

There exists a randomized algorithm that given an instance
$\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},s,\eta)$ of ${\mathcal{G}}$-Sb-CFFA
either reports a failure or finds a feasible assignment in
$\mathcal{O}((3e)^{ns}\cdot h(s)\cdot(n+m)^{\mathcal{O}(1)})$ time. Moreover,
if the algorithm is given a yes-instance, the algorithm returns “yes” with
probability at least $1/2$, and if the algorithm is given a no-instance, the
algorithm returns “no” with probability $1$.

###### Proof

Let $\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},s,\eta)$ be an instance of
${\mathcal{G}}$-Sb-CFFA. We color the jobs uniformly at random with colors
$[ns]$. Let $\chi\colon V(\mathcal{H})\rightarrow[ns]$ be this coloring
function. We run the algorithm in Lemma 4 on the instance $\mathscr{J}$ with
coloring function $\chi$. If the algorithm returns “yes”, then we return
“yes”. Otherwise, we report failure.

Let $\mathscr{J}$ be a yes-instance of ${\mathcal{G}}$-Sb-CFFA and $\phi$ be a
hypothetical solution. Due to Proposition 4, all the jobs in
$\phi(\mathcal{A})$ are colored using distinct colors with probability at
least $e^{-ns}$. Thus, the algorithm in Lemma 4 returns yes with probability
at least $e^{-ns}$. Thus, to boost the success probability to a constant, we
repeat the algorithm independently $e^{ns}$ times. Thus, the success
probability is at least

$1-\Big{(}1-\frac{1}{e^{ns}}\Big{)}^{ns}\geq 1-\frac{1}{e}\geq\frac{1}{2}$

If the algorithm returns “yes”, then clearly $\mathscr{J}$ is a yes-instance
of ${\mathcal{G}}$-Sb-CFFA due to Lemma 4. ∎

####  3.2.2 Deterministic Algorithm

We derandomize the algorithm using $(p,q)$-perfect hash family to obtain a
deterministic algorithm for our problem.

######  Definition 1 ($(p,q)$-perfect hash family)

([2]) For non-negative integers $p$ and $q$, a family of functions
$f_{1},\ldots,f_{t}$ from a universe $U$ of size $p$ to a universe of size $q$
is called a $(p,q)$-perfect hash family, if for any subset $S\subseteq U$ of
size at most $q$, there exists $i\in[t]$ such that $f_{i}$ is injective on
$S$.

We can construct a $(p,q)$-perfect hash family using the following result.

######  Proposition 5 ([30, 8])

There is an algorithm that given $p,q\geq 1$ constructs a $(p,q)$-perfect hash
family of size $e^{q}q^{\mathcal{O}(\log q)}\log p$ in time
$e^{q}q^{\mathcal{O}(\log q)}p\log p$.

Let $\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},s,\eta)$ be an instance of
${\mathcal{G}}$-Sb-CFFA. Instead of taking a random coloring $\chi$, we
construct an $(m,ns)$-perfect hash family $\mathcal{F}$ using Proposition 5.
Then, for each function $f\in\mathcal{F}$, we invoke the algorithm in Lemma 4
with the coloring function $\chi=f$. If there exists a feasible assignment
$\phi\colon\mathcal{A}\rightarrow 2^{\mathcal{I}}$ such that $|\phi(a)|\leq
s$, for all $a\in\mathcal{A}$, then there exists a function $f\in\mathcal{F}$
that is injective on $\phi(\mathcal{A})$, since $\mathcal{F}$ is an
$(m,ns)$-perfect hash family. Consequently, due to Lemma 4, the algorithm
return “yes”. Hence, we obtain the following deterministic algorithm.

###### Theorem 3.3

There exists a deterministic algorithm for ${\mathcal{G}}$-Sb-CFFA running in
time $\mathcal{O}((3e)^{ns}\cdot(ns)^{\log ns}\cdot
h(s)\cdot(n+m)^{\mathcal{O}(1)})$.

Due to Theorem 3.3, we can conclude the following.

###### Corollary 2

If ${\mathcal{G}}$-Sb-MWIS is solvable in polynomial time, then there exists a
deterministic algorithm for ${\mathcal{G}}$-Sb-CFFA running in time
$\mathcal{O}((3e)^{ns}\cdot(ns)^{\log ns}\cdot(n+m)^{\mathcal{O}(1)})$.

It is possible that MWIS is polynomial-time solvable on $\mathcal{G}$, but
${\mathcal{G}}$-Sb-MWIS is NP-complete, as any $k$-sized solution of Sb-MWIS
need not satisfy the weight constraint in the ${\mathcal{G}}$-Sb-MWIS problem.
However, when we use an algorithm $\mathbb{B}$ for ${\mathcal{G}}$-Sb-MWIS in
our algorithm, we could have simply used an algorithm for MWIS. Though this
will not result in a size bound of $s$ on the size of an independent set of
weight at least $\eta$ that we found, however, this is sufficient to solve
CFFA. However, we need to use ${\mathcal{G}}$-Sb-MWIS, when MWIS is NP-
complete and we wish to use FPT algorithm with respect to $k$. Due to Theorem
3.3 and this observation, CFFA is FPT when parameterized by $n+s$ for several
graph classes, such as chordal graphs [22], bipartite graphs [22],
$P_{6}$-free graphs [23], outerstring graph [26], and fork-free graph [28].

###### Remark 1

Our algorithm for chordal graphs is an improvement over the known algorithm
that runs in $\mathcal{O}(m^{n+2}(Q+1)^{2n})$ time, where
$Q=\max_{a\in\mathcal{A}}\sum_{i\in\mathcal{I}}p_{a}(i)$ [7].

###  3.3 FPT Algorithms for ${\mathcal{G}}$-Sb-MWIS when $\mathcal{G}$ is
$f$-ifc

In this section, we prove Theorem 1.2. Let $(G,k,\rho,w)$ be a given instance
of ${\mathcal{G}}$-Sb-MWIS. Further, $\mathcal{G}$ is $f$-ifc. Let ${\sf
HighWeight}=\\{v\in V(G)\colon w(v)\geq\nicefrac{{\rho}}{{k}}\\}$. Note that
if there exists an independent set of $G[{\sf HighWeight}]$ of size $k$, then
it is the solution of our problem. Since, $G$ belongs to $f$-ifc, $G[{\sf
HighWeight}]$ is also $f$-ifc. Thus, there exists an independent set in
$G[{\sf HighWeight}]$ of size at least $f(|{\sf HighWeight}|)$. If $f(|{\sf
HighWeight}|)\geq k$, then there exists a desired solution. To find a solution
we do as follow. Consider an arbitrary set $X\subseteq{\sf HighWeight}$ of
size $f^{-1}(k)$. The size of $X$ guarantees that the set $X$ also has a
desired solution. Now we enumerate subsets of size $k$ of $X$ one by one, and
check whether it is independent; and if independent return it. This concludes
the proof. Otherwise, $|{\sf HighWeight}|<f^{-1}(k)$. Note that the solution
contains at least one vertex of ${\sf HighWeight}$. Thus, we guess a vertex,
say $v$, in the set ${\sf HighWeight}$ which is in the solution, delete $v$
and its neighbors from $G$, and decrease $k$ by $1$. Repeat the algorithm on
the instance $(G-N[v],k-1,\rho-w(v),w\lvert_{V(G-N[v])})$.

Since the number of guesses at any step of the algorithm is at most
$f^{-1}(k)$ and the algorithm repeats at most $k$ times, the running time of
the algorithm is $\mathcal{O}((f^{-1}(k))^{k}\cdot(n+m)^{\mathcal{O}(1)})$.

###### Corollary 3

There exists an algorithm that solves ${\mathcal{G}}$-Sb-MWIS in
$\mathcal{O}((2k)^{k}\cdot(n+m)^{\mathcal{O}(1)})$,
$\mathcal{O}((4k^{2})^{k}\cdot(n+m)^{\mathcal{O}(1)})$,
$\mathcal{O}((4k)^{k}\cdot(n+m)^{\mathcal{O}(1)})$,
$\mathcal{O}((dk+k)^{k}\cdot(n+m)^{\mathcal{O}(1)})$,
$\mathcal{O}(R(\ell,k)^{k}\cdot(n+m)^{\mathcal{O}(1)})$ time, when
$\mathcal{G}$ is a family of bipartite graphs, triangle free graphs, planar
graphs, $d$-degenerate graphs, graphs excluding $K_{\ell}$ as an induced
graphs, respectively. Here, $R(\ell,k)$ is an upper bound on Ramsey number.

###  3.4 A polynomial time algorithm for ${\mathcal{G}}$-Sb-MWIS when
$\mathcal{G}$ is a cluster graph

In this section, we design a polynomial time algorithm. Let
$\mathscr{J}=(G,k,\rho,w)$ be a given instance of ${\mathcal{G}}$-Sb-MWIS.
From each clique, we pick a vertex of highest weight. Let $X$ be the set of
these vertices. Let $S\subseteq X$ be a set of $k$ vertices of $X$ that has
highest weight. We return “yes” if $w(S)\geq\eta$, otherwise, “no”. Next, we
argue the correctness of the algorithm. If we return “yes”, then, clearly, $S$
is an independent set of size at most $k$ and weight at least $\eta$. In the
other direction, suppose that $Z$ is a solution to $\mathscr{J}$. Suppose that
$Z$ picks elements from the cliques $C_{1},C_{2},\ldots,C_{\ell}$, $\ell\leq
k$. If $Z$ does not pick highest weight vertex from $C_{j}$, for some $j\leq
l$, then we can replace the vertex $v=Z\cap C_{j}$ with highest weight vertex
of $C_{j}$ in $Z$, and it is still a solution. Note that if $S\cap
C_{j}=\emptyset$, where $j\leq\ell$, then $S$ contains a vertex whose weight
is at least the weight of $v=S\cap C_{j}$ due to the construction of $S$.
Since $|S|\geq|Z|$, we have a unique vertex for every such $j$. Thus,
$w(S)\geq w(Z)\geq\eta$, and hence, the algorithm returns “yes”.

##  4 Distance From Chaos: Examining possible structures of the conflict graph

Starting point of our results in this section is the polynomial-time algorithm
for CFFA when conflict graph is a complete graph (there is an edge between
every pair of vertices). We give proof of Theorem 1.3. We begin with a simple
observation, which follows due to the fact that the maximum size of an
independent set in clique is $1$.

###### Observation 3

If the conflict graph is a complete graph, then the bundle size is $1$.

######  Proof (of Theorem 1.3)

Let $\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},\eta)$ be a given instance of CFFA. In
light of Observation 3, we construct the following auxiliary bipartite graph
$G=(L,R)$ as follows: for every agent $a\in\mathcal{A}$, we add a vertex $a$
in $L$ and for every job $x\in\mathcal{I}$, we add a vertex $x$ in $R$. If
$p_{a}(x)\geq\eta$, then add an edge $ax$ in $G$. Next, we find a maximum
matching $M$ in $G$. If $M$ does not saturate $L$, then return “no”, otherwise
return the following function $\phi\colon\mathcal{A}\rightarrow
2^{\mathcal{I}}$, $\phi(a)=M(a)$.

Next, we prove the correctness of the algorithm. Clearly, if we return the
function $\phi$, then it is a solution as we have an edge $ax$ if and only if
$p_{a}(x)\geq\eta$ and $M$ is a matching in $G$ saturating $L$. Next, we prove
that if $\mathscr{J}$ is a yes-instance of CFFA, then the algorithm returns a
function. Let $\phi$ be a solution to $\mathscr{J}$. Since
$p_{a}(\phi(a))\geq\eta$, we have an edge $a\phi(a)$ in $G$. Thus, there
exists a matching in $G$ saturating $L$. Hence, the maximum matching $M$ in
$G$ saturates $L$ and the algorithm returns a function. ∎

###  4.1 When conflict is highly localized: conflict graph is a cluster graph

As discussed in the Introduction, there can be scenarios, where the
incompatibilities are highly localized in a way that the set of jobs can be
decomposed into these small chunks where there is incompatibilities between
all jobs in the same chunk and none between jobs in different chunks. Such a
scenario is captured by a cluster graph

We show that the problem is intractable for cluster graph even when it
consists of $3$ cliques. This is in contrast to Theorem 1.3. To show the NP-
hardness, we give a polynomial time reduction from Numerical 3-dimensional
Matching problem, which is known to be NP-hard [21]. In Numerical
3-Dimensional Matching problem, we are given three disjoint sets $X$, $Y$, and
$Z$, each containing $\tilde{m}$ elements, a size $s(a)\in\mathbb{Z}_{+}$ for
each element $a\in X\cup Y\cup Z$, and a bound $B\in\mathbb{Z}_{+}$. The goal
is to partition $X\cup Y\cup Z$ into $\tilde{m}$ disjoint sets
$A_{1},\ldots,A_{\tilde{m}}$ such that (i) each $A_{i}$, where
$i\in[\tilde{m}]$, contains exactly one element from each of $X$, $Y$, and
$Z$, and (ii) for each $i\in[\tilde{m}]$, $\sum_{a\in A_{i}}s(a)=B$. Note that
it follows that $\sum_{i\in[\tilde{m}]}\sum_{a\in A_{i}}s(a)=\tilde{m}B$.
Next, we give the desired reduction.

######  Proof (of Theorem 1.4)

Given an instance $\mathscr{J}=(X,Y,Z,\\{s_{a}\\}_{a\in X\cup Y\cup Z},B)$ of
the Numerical 3-Dimensional Matching problem, we create an instance
$\mathscr{J^{\prime}}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},\eta=B)$ of CFFA, where
$\mathcal{I}=X\cup Y\cup Z$ and $\mathcal{H}$ is a cluster graph on the vertex
set $\mathcal{I}$ with induced cliques on the vertices in the set $X$, $Y$,
and $Z$. We define a set of agents
$\mathcal{A}=\\{a_{1},\ldots,a_{\tilde{m}}\\}$ and for each agent
$a_{i}\in\mathcal{A}$, we define the utility function ${\rm
u}_{a_{i}}(j)=s(j)$ for each job $j\in\mathcal{I}$.

###### Claim 4

$\mathscr{J}$ is a yes-instance of Numerical 3-Dimensional Matching if and
only if $\mathscr{J^{\prime}}$ is a yes-instance of CFFA

###### Proof

Suppose that $\mathscr{J}$ is a yes-instance of Numerical 3-Dimensional
Matching. Then, there is a solution $A_{i},i\in[\tilde{m}]$, that satisfies
the desired properties. It follows then that for the agent
$a_{i}\in\mathcal{A}$, we have the condition that $\sum_{j\in A_{i}}{\rm
u}_{a_{i}}(j)=\sum_{j\in A_{i}}s(j)=B$. Thus, the assignment function $\phi$,
where $\phi(a_{i})=A_{i}$, yields a solution for $\mathscr{J^{\prime}}$ as
well due to the construction of $\mathcal{H}$.

Conversely, suppose that we have a solution for $\mathscr{J^{\prime}}$, i.e.,
an assignment function $\phi$ for which $\phi(a_{i})\cap\phi(a_{j})=\emptyset$
for every $\\{a_{i},a_{j}\\}\subseteq\mathcal{A}$, and for every
$a_{i}\in\mathcal{A}$, $\phi(a_{i})$ is an independent set and
$\sum_{j\in\phi(a_{i})}{\rm u}_{a_{i}}(j)\geq B$.

Suppose that there exists an agent $a_{i}$ whose bundle
$\sum_{j\in\phi(a_{i})}{\rm u}_{a_{i}}(j)>B$, then taking all the $\tilde{m}$
bundles together we note that
$\sum_{i\in[\tilde{m}]}\sum_{j\in\phi(a_{i})}{\rm u}_{a_{i}}(j)>\tilde{m}B$,
contradiction to the definition of the problem. Hence, we know that for each
agent $a_{i}\in\mathcal{A}$, $\sum_{j\in\phi(a_{i})}{\rm u}_{a_{i}}(j)=B$.
Since there are $\tilde{m}$ agents, every job is assigned to some agent.
Furthermore, since $\phi(a_{i})$ is an independent set in $\mathcal{H}$, for
each $i\in[\tilde{m}]$, we know that $\phi(a_{i})$ contains $3$ elements, one
from each clique. Hence, setting $A_{i}=\phi(a_{i})$ gives a solution to
$\mathscr{J}$. ∎

This completes the proof. ∎

Next, we show that when the cluster graph has only two cliques and the utility
functions are uniform, i.e., for any two agents $a,a^{\prime}$,
$u_{a}=u_{a^{\prime}}$, then CFFA can be solved in polynomial time. In
particular, we prove Theorem 1.5. For arbitrary utility functions, the
complexity is open. We begin by noting that due to the utility functions being
uniform, every bundle is valued equally by every agent. This allows us to look
at the problem purely from the perspective of partitioning the jobs into $n$
bundles of size at most two.

######  Proof (of Theorem 1.5)

Let $\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},\eta)$ be a given instance of CFFA.
Since the utility functions are uniform, we skip the agent identification from
the subscript of utility function, i.e., instead of writing ${\rm u}_{a}$ for
the utility function of agent $a$, we will only use ${\rm u}$.

We note that if there exists an job $z$ such that ${\rm u}(z)\geq\eta$, then
there exists a solution that assign it to some agent. Since the utility
functions are uniform, it can be assigned to any agent. Let $\mathcal{I}_{\sf
HighUtility}\subseteq\mathcal{I}$ be the set of jobs whose utility is at least
$\eta$, i.e., $\mathcal{I}_{\sf HighUtility}=\\{z\in\mathcal{I}\colon{\rm
u}(z)\geq\eta\\}$. Let $\mathcal{I}_{\sf
LowUtility}=\mathcal{I}\setminus\mathcal{I}_{\sf HighUtility}$. If
$|\mathcal{I}_{\sf HighUtility}|\geq n$, then every agent get an job from the
set $\mathcal{I}_{\sf HighUtility}$, and it is a solution. Otherwise, there
are $|\mathcal{A}|-|\mathcal{I}_{\sf HighUtility}|$ agents to whom we need to
assign bundles of size two. Let ${\sf IS}$ denote the set of all independent
sets of size two in $\mathcal{H}[\mathcal{I}_{\sf LowUtility}]$. Thus, ${\sf
IS}$ has size at most $m^{2}$.

Next, we construct a graph, denoted by $\mathcal{\widehat{H}}$, on the jobs in
$\mathcal{I}_{\sf LowUtility}$ where there is an edge between vertices $a$ and
$b$ if $\\{a,b\\}\in{\sf IS}$ and $u(a)+u(b)\geq\eta$. In this graph we
compute a maximum sized matching, denoted by $\mathcal{M}$. If its size is
less than $n-|\mathcal{I}_{\sf HighUtility}|$, then we return the answer “no”.
Otherwise, we return answer “yes” and create an assignment as follows: if
$(a,b)\in\mathcal{M}$, then we have a bundle containing $\\{a,b\\}$. We create
exactly $n-|\mathcal{I}_{\sf HighUtility}|$ such bundles of size two and
discard the others. These bundles along with the singleton bundles from
$\mathcal{I}_{\sf HighUtility}$ yield our assignment for $n$ agents.

Clearly, this graph has $m$ vertices and at most $m^{2}$ edges. Thus, the
maximum matching can be found in polynomial time. Next, we prove the
correctness of the algorithm.

Correctness: If the algorithm returns an assignment of jobs to the agents,
then clearly, for every agent the utility from the bundle is at least $\eta$.
Every bundle is also an independent set in $\mathcal{H}$. Moreover, if a
bundle is of size one, then the singleton job is clearly an element of the set
$\mathcal{I}_{\sf HighUtility}$; otherwise, the bundle represents an
independent set of size two in IS whose total utility is at least $\eta$.
There are $n$ bundles in total, exactly $|\mathcal{I}_{\sf HighUtility}|$
bundles of size one and at least $n-|\mathcal{I}_{\sf HighUtility}|$ bundles
of size two.

In the other direction, suppose that $\phi$ is a solution to $\mathscr{J}$.
Let $a$ be an agent whose bundle size is two and $\phi(a)$ contains at least
one job from $\mathcal{I}_{\sf HighUtility}$, say $z$. Update the assignment
$\phi$ as follows: $\phi(a)=\\{z\\}$. Note that $\phi$ is still a solution to
$\mathscr{J}$. Let $\mathcal{A}_{1}\subseteq\mathcal{A}$ be the set of agents
such that for every agent $a\in\mathcal{A}_{1}$, $|\phi(a)|=1$, i.e., the
bundle size assigned to every agent in $\mathcal{A}_{1}$ is $1$. Clearly,
$\phi(\mathcal{A}_{1})\subseteq\mathcal{I}_{\sf HighUtility}$. Let ${\sf
rem}=\mathcal{I}_{\sf HighUtility}\setminus\phi(\mathcal{A}_{1})$, the set of
unassigned “high value” jobs. Suppose that ${\sf rem}\neq\emptyset$.

Let $\mathcal{A}^{\prime\prime}\subseteq\mathcal{A}\setminus\mathcal{A}_{1}$
be a set of size $\min\\{|\mathcal{A}\setminus\mathcal{A}_{1}|,|{\sf
rem}|\\}$. Let $\mathcal{A}^{\prime\prime}=\\{a_{1},\ldots,a_{\ell}\\}$ and
${\sf rem}=\\{z_{1},\ldots,z_{q}\\}$, where clearly $\ell\leq q$. Update the
assignment $\phi$ as follows: for every $i\in[\ell]$,
$\phi(a_{i})=\\{z_{i}\\}$. Clearly, $\phi$ is still a solution of
$\mathscr{J}$. We note that there are only two cases: either
$\mathcal{A}=\mathcal{A}_{1}\cup\mathcal{A}^{\prime\prime}$ or
$\mathcal{\tilde{A}}=\mathcal{A}\setminus(\mathcal{A}_{1}\cup\mathcal{A}^{\prime\prime})$
is non-empty.

If $\mathcal{A}=\mathcal{A}_{1}\cup\mathcal{A}^{\prime\prime}$, then we have
that the disjoint union of $\phi(\mathcal{A}_{1})\cup\phi({\sf
rem})\subseteq\mathcal{I}_{\sf HighUtility}$. In other words,
$|\mathcal{I}_{\sf HighUtility}|\geq n$, and so there exists a solution in
which every bundle is of size one and contains an element from
$\mathcal{I}_{\sf HighUtility}$.

Otherwise, let
$\mathcal{\tilde{A}}=\mathcal{A}\setminus(\mathcal{A}_{1}\cup\mathcal{A}^{\prime\prime})$.
Clearly, each of the jobs in $\mathcal{I}_{\sf HighUtility}$ are assigned to
agents in $\mathcal{A}_{1}\cup\mathcal{A}^{\prime\prime}$ and subsets of jobs
in $\mathcal{I}_{\sf LowUtility}$ are assigned to agents in
$\mathcal{\tilde{A}}$. In other words, there exist $|\mathcal{I}_{\sf
HighUtility}|$ bundles of size one and $n-|\mathcal{I}_{\sf HighUtility}|$
bundles of size two. Specifically for the latter, we know that each of the
bundles is an independent set, they are pairwise disjoint and the total
utility within each bundle is at least $\eta$. Thus, the members of each
bundle share an edge in the graph $\mathcal{\widehat{H}}$ and the bundles
themselves form a matching in the graph. Thus, our algorithm that computes a
maximum matching in $\mathcal{\widehat{H}}$ would find a matching of size at
least $n-|\mathcal{I}_{\sf HighUtility}|$. Hence, given the construction of
the assignment from such a matching, we can conclude that our algorithm would
return an assignment with the desired properties. ∎

###  4.2 Distance from chaos: parameterization by #missing edges from complete
graph

In this section, we will prove that CFFA is FPT with respect to the parameter
$t$, the number of edges missing from $\mathcal{H}$ being a complete graph.
Further, we will present a polynomial time algorithm when the degree of every
vertex in $\mathcal{H}$ is $m-2$ (one less than the degree in complete graph)
and the utility functions are uniform.

We first show a result that gives a subexponential time algorithm when the
number of agents is constant.

######  Proof (of Theorem 1.6)

We observe that the complement graph $\mathcal{H}$, denoted by
$\overline{\mathcal{H}}$, contains all the vertices of $\mathcal{H}$ but $t$
edges only. Moreover, each clique in this graph constitutes a conflict-free
bundle in the instance of CFFA. Conversely, we claim that any conflict-free
bundle in the instance of CFFA must form a clique in $\overline{\mathcal{H}}$
since for every pair of jobs $x_{1},x_{2}$ in a bundle, there exists an edge
in $\overline{\mathcal{H}}$.

Thus, enumerating all possible cliques (not just maximal ones) in
$\overline{\mathcal{H}}$ allows us to check for possible allocations to
agents. To show that this is doable in the claimed time, we will count the
number of cliques in $\overline{\mathcal{H}}$. Since $\overline{\mathcal{H}}$
has $t$ edges, there can be at most $2t$ vertices that are not isolated.
Vertices that are isolated constitute a clique of size $1$, and are called
trivial cliques. They are upper bounded by the number of jobs ($m$), and will
be counted separately. A clique is said to be non-trivial if it does not
contain an isolated vertex. Next, we will upper bound the non-trivial cliques.
Towards this, we first show that $\overline{\mathcal{H}}$ is a
$2\sqrt{t}$-degenerate graph by a simple counting argument. Note that if there
exists a subgraph $H$ with minimum degree at least $2\sqrt{t}$, then the graph
must have more than $t$ edges. Let $H$ be the subgraph of $\mathcal{H}$
induced on the non-isolated vertices of $\mathcal{H}$. Since $H$ has at most
$t$ edges, every subgraph of $H$ has a vertex of degree at most $2\sqrt{t}$.
Thus, $H$ is a $2\sqrt{t}$-degenerate graph, and hence has a
$2\sqrt{t}$-degeneracy sequence.

Let $\mathcal{D}=v_{1},\ldots,v_{2t}$ denote a $2\sqrt{t}$-degenerate degree
sequence of $H$. Notice that for any $i\in[2t]$, $v_{i}$ has at most
$2\sqrt{t}$ neighbors among $\\{v_{j}\colon j>i\\}$. Consider the $2\sqrt{t}$
neighbors of $v_{1}$ and among them there can be at most $2^{2\sqrt{t}}$
cliques and can be enumerated in time $\mathcal{O}(2^{2\sqrt{t}})$. By
iterating over $v_{i}$, we can enumerate all the non-trivial cliques in
$\overline{\mathcal{H}}$ in $\mathcal{O}(2t\cdot 2^{2\sqrt{t}})$ time. Indeed,
for a non-trivial clique $C$, if $v_{i}$ is the first vertex in $C$ with
respect to $\mathcal{D}$, that is all other vertices in $C$ appear after
$v_{i}$ in $\mathcal{D}$, then $C$ is enumerated when we enumerate all the
cliques with respect to $v_{i}$ in our process. This implies that the number
of independent sets in $\mathcal{H}$ is upper bounded by $\mathcal{O}(2t\cdot
2^{2\sqrt{t}}+m)$ and the number of independent sets of size at least $2$ in
$\mathcal{H}$ is upper bounded by $\mathcal{O}(2t\cdot 2^{2\sqrt{t}})$. Let
$\mathbb{I}_{\geq 2}$ denote the family of independent sets of $\mathcal{H}$
that have size at least $2$ – the family of non-trivial independent sets.

Thus, one potential algorithm is as follows. We first guess which agents are
assigned non-trivial independent sets and which independent set. That is, for
each agent $a\in\mathcal{A}$, we guess an independent set
$I_{a}\in\mathbb{I}_{\geq 2}\cup\gamma$ ($\gamma$ is just to capture that the
agent will not get non-trivial bundle). Let
$\mathcal{A}^{\prime}\subseteq\mathcal{A}$ be the set of agents for whom the
guess is not $\gamma$. Let
$(\mathcal{A}^{\prime},\\{I_{a}\\}_{a\in\mathcal{A}^{\prime}})$ denote the
corresponding guess for the agents in $\mathcal{A}^{\prime}$. We first check
that the guess for $\mathcal{A}^{\prime}$ is correct. Towards that we check
that for each $a_{1},a_{2}\in\mathcal{A}^{\prime}$, $I_{a_{1}}\cap
I_{a_{2}}=\emptyset$ and for each $a\in\mathcal{A}^{\prime}$, we have that
$\sum_{i\in I_{a}}{\rm u}_{a}(i)\geq\eta$. Since, $|\mathbb{I}_{\geq 2}|$ is
upper bounded by $\mathcal{O}(2t\cdot 2^{2\sqrt{t}})$, the number of guess are
upper bounded by $\mathcal{O}((2t\cdot 2^{2\sqrt{t}}+1)^{n})$. For each
correct guess $(\mathcal{A}^{\prime},\\{I_{a}\\}_{a\in\mathcal{A}^{\prime}})$,
we solve the remaining problem by invoking Theorem 1.3. Let
$\mathcal{A}^{\star}=\mathcal{A}\setminus\mathcal{A}^{\prime}$ and
$\mathcal{I}^{\star}=\mathcal{I}\setminus(\bigcup_{a\in\mathcal{A}^{\prime}}I_{a})$.
Then, we apply Theorem 1.3 on the following instance:
$(\mathcal{A}^{\star},\mathcal{I}^{\star},(p_{a})_{a\in\mathcal{A}^{\star}},\eta,\mathcal{H}[\mathcal{I}^{\star}])$,
here $\mathcal{H}[\mathcal{I}^{\star}]$ is a clique. This implies that the
total running time of the algorithm is upper bounded by $\mathcal{O}((2t\cdot
2^{2\sqrt{t}}+1)^{n}(n+m)^{\mathcal{O}(1)})$.

However, Theorem 1.6 is not an FPT algorithm parameterized by $t$ alone. In
what follows we design such an algorithm.

######  Proof (of Theorem 1.7)

Let $\mathscr{J}=(\mathcal{A},\mathcal{I},\\{{\rm
u}_{a}\\}_{a\in\mathcal{A}},\mathcal{H},\eta)$ be a given instance of CFFA.
Let $V_{>1}$ be the set of vertices which are part of independent sets of size
at least $2$. As argued in the proof of Theorem 1.6, $|V_{>1}|\leq 2t$. Thus,
there are at most $t$ bundles that contains more than one job. We guess
partition of the jobs in $V_{>1}$ into at most $t+1$ sets,
$\mathsf{notLarge,Large_{1},\ldots,Large_{\ell}}$, where $\ell\leq t$, such
that each set is an independent set in $\mathcal{H}$. The set
$\mathsf{notLarge}$ might be empty. This contains the set of jobs in $V_{>1}$
which will not be part of any bundle of size at least $2$. The size of
$\mathsf{Large}_{i}$ is at least $2$, for every $i\in[\ell]$, and each
$\mathsf{Large}_{i}$ will be assigned to distinct agents in the solution.
Next, we construct a complete graph $\mathcal{H}^{\prime}$ as follows. For
each $\mathsf{Large}_{i}$, where $i\in[\ell]$, we have a vertex
$\mathsf{Large}_{i}$ in $\mathcal{H}^{\prime}$, and ${\rm
u}^{\prime}_{a}(\mathsf{Large}_{i})=\sum_{x\in\mathsf{Large}_{i}}{\rm
u}_{a}(x)$, where $a\in\mathcal{A}$. If a vertex $v\in\mathcal{H}$ does not
belong to any $\mathsf{Large}_{i}$, where $i\in[\ell]$, then add the vertex
$v$ to $\mathcal{H}^{\prime}$, and ${\rm u}^{\prime}_{a}(v)={\rm u}_{a}(v)$.
Let $\mathscr{J}^{\prime}=(\mathcal{A},\mathcal{I},\\{{\rm
u}^{\prime}_{a}\\}_{a\in\mathcal{A}},\mathcal{H}^{\prime},\eta)$ be the new
instance of CFFA where $\mathcal{H}^{\prime}$ is a complete graph. Using
Theorem 1.3, we find the assignment of bundles to the agents for the instance
$\mathscr{J}^{\prime}$, if it exists, and return “yes”. If the algorithm does
not find the assignment for any guessed partition, then we return “no”. The
running time follows from Theorem 1.3 and the fact that there are at most
$(2t)^{t+1}$ possible partitions.

Next, we prove the correctness of the algorithm. Suppose that $\mathscr{J}$ is
a yes-instance of CFFA and $\phi$ be one of its solution. Let
$\mathcal{B}=\\{\phi(a)\colon a\in\mathcal{A}\text{ and }|\phi(a)|\geq 2\\}$.
Clearly, sets in $\mathcal{B}$ are disjoint subsets of $V_{>1}$. Let
$\mathcal{B}=\\{B_{1},\ldots,B_{\ell}\\}$. Let $X\subseteq V_{>1}$ contains
all the jobs that do not belong to any set in $\mathcal{B}$. Since we try all
possible partitions of $V_{>1}$, we also tried $B_{1},\ldots,B_{\ell},X$.
Without loss of generality, let $B_{i}$ is assigned to $a_{i}$ under $\phi$.
Thus, in the graph $\mathcal{H}^{\prime}$, there is a matching
$M=\\{a_{i}B_{i}\in i\in[\ell]\\}\cup\\{a\phi(a)\colon|\phi(a)|=1\\}$ that
saturates $L$ in the proof of Theorem 1.3. Thus, the algorithm returns “yes”.
The correctness of the other direction follows from the correctness of Theorem
1.3 and the construction of the instance $\mathcal{J}^{\prime}$.

Next, we give our claimed polynomial-time algorithm.

######  Proof (of Theorem 1.8)

The algorithm is same as in Theorem 1.5. Here, the size of ${\sf IS}$ is
bounded by $\nicefrac{{n}}{{2}}$.

##  5 Outlook

In this article, we studied conflict-free fair allocation problem under the
paradigm of parameterized complexity with respect to several natural input
parameters. We hope that this will lead to the new set of results for the
problem. The following question eludes so far: (i) the computation complexity
of CFFA when the cluster graph contains only $2$ cliques with arbitrary
utility functions, (ii) the computational complexity when the degree of every
vertex in the conflict graph is $n-2$ with arbitrary utility functions.

Another direction of research is to consider various other fairness notions
known in the literature, such as envy-freeness, proportional fair-share, min-
max fair-share, etc., under the conflict constraint.

## References

  * [1] M. M. Ahmadian, M. Khatami, A. Salehipour, and T. C. E. Cheng.  Four decades of research on the open-shop scheduling problem to minimize the makespan.  European Journal of Operational Research, 295(2):399–426, 2021\.
  * [2] N. Alon, R. Yuster, and U. Zwick.  Color-coding.  Journal of the ACM (JACM), 42(4):844–856, 1995.
  * [3] S. Barman and P. Verma.  Existence and computation of maximin fair allocations under matroid-rank valuations.  In AAMAS ’21, pages 169–177, 2021.
  * [4] I. Bezáková and V. Dani.  Allocating indivisible goods.  ACM SIGecom Exchanges, 5(3):11–18, 2005.
  * [5] Sylvain Bouveret, Katarína Cechlárová, Edith Elkind, Ayumi Igarashi, and Dominik Peters.  Fair division of a graph.  In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pages 135–141, 2017.
  * [6] S. Cheng and Y. Mao.  Restricted max-min allocation: Integrality gap and approximation algorithm.  Algorithmica, pages 1–40, 2022.
  * [7] N. Chiarelli, M. Krnc, M. Milanic, U. Pferschy, N. Pivac, and J. Schauer.  Fair packing of independent sets.  In IWOCA 2020, volume 12126 of Lecture Notes in Computer Science, pages 154–165, 2020.
  * [8] M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [9] M. Cygan and M. Pilipczuk.  Exact and approximate bandwidth.  Theor. Comput. Sci., 411(40-42):3701–3713, 2010.
  * [10] K. Dabrowski, V. V. Lozin, H. Müller, and D. Rautenbach.  Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number.  J. Discrete Algorithms, 14:207–213, 2012.
  * [11] Andreas Darmann, Ulrich Pferschy, Joachim Schauer, and Gerhard J. Woeginger.  Paths, trees and matchings under disjunctive constraints.  Discrete Applied Mathematics, 159(16):1726–1735, 2011.
  * [12] B. L. Deuermeyer, D. K. Friesen, and M. A. Langston.  Scheduling to maximize the minimum processor finish time in a multiprocessor system.  SIAM Journal on Algebraic Discrete Methods, 3(2):190–196, 1982\.
  * [13] R. G. Downey and M. R. Fellows.  Fixed-parameter tractability and completeness ii: On completeness for w [1].  Theoretical Computer Science, 141(1-2):109–131, 1995.
  * [14] R. G. Downey and M. R. Fellows.  Fundamentals of Parameterized Complexity.  Springer-Verlag, 2013.
  * [15] S. Ebadian, D. Peters, and N. Shah.  How to fairly allocate easy and difficult chores.  In AAMAS 2022, pages 372–380. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022.
  * [16] G Even, M. M. Halldórsson, L. Kaplan, and D. Ron.  Scheduling with conflicts: Online and offline algorithms.  J. Sched., 12(2):199–224, 2009.
  * [17] Pablo Factorovich, Isabel Méndez-Díaz, and Paula Zabala.  Pickup and delivery problem with incompatibility constraints.  Comput. Oper. Res., 113:17, 2020.  Id/No 104805.
  * [18] J. Flum and M. Grohe.  Parameterized Complexity Theory.  Springer-Verlag, 2006.
  * [19] F. V. Fomin, D. Lokshtanov, and S. Saurabh.  Efficient computation of representative sets with applications in parameterized and exact algorithms.  In SODA, pages 142–151, 2014.
  * [20] F. V. Fomin, I. Todinca, and Y. Villanger.  Large induced subgraphs via triangulations and CMSO.  SIAM J. Comput., 44(1):54–87, 2015.
  * [21] M.R. Garey and D.S. Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [22] Martin Charles Golumbic.  Algorithmic graph theory and perfect graphs.  2004\.
  * [23] A. Grzesik, T. Klimošová, M. Pilipczuk, and Michał Pilipczuk.  Polynomial-time algorithm for maximum weight independent set on p6-free graphs.  ACM Trans. Algorithms, 18(1), 2022.
  * [24] H. Hummel and M. L. Hetland.  Fair allocation of conflicting items.  Autonomous Agents and Multi-Agent Systems, 36(1):1–33, 2022.
  * [25] S. Jukna.  Extremal combinatorics: with applications in computer science, volume 571.  Springer, 2011.
  * [26] J. M. Keil, J. SB Mitchell, D. Pradhan, and M. Vatshelle.  An algorithm for the maximum weight independent set problem on outerstring graphs.  Computational Geometry, 60:19–25, 2017.
  * [27] D. Kurokawa, A. D. Procaccia, and J. Wang.  Fair enough: Guaranteeing approximate maximin shares.  Journal of the ACM (JACM), 65(2):1–27, 2018.
  * [28] Vadim V. Lozin and Martin Milanič.  A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.  Journal of Discrete Algorithms, 6(4):595–604, 2008.
  * [29] R. T. Moenck.  Practical fast polynomial multiplication.  In Proceedings of SYMSAC’76, pages 136–148, 1976.
  * [30] M. Naor, L. J. Schulman, and A. Srinivasan.  Splitters and near-optimal derandomization.  In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 182–191, 1995.
  * [31] W. Suksompong.  Constraints in fair division.  SIGecom Exch., 19(2):46–61, 2021.
  * [32] G. J. Woeginger.  A polynomial-time approximation scheme for maximizing the minimum machine completion time.  Operations Research Letters, 20(4):149–154, 1997.