11institutetext: University of Groningen, the Netherlands, 11email:
<EMAIL_ADDRESS>22institutetext: Utrecht University, the Netherlands
22email: {j.nederlof<EMAIL_ADDRESS>
# Parameterized Algorithms for Covering by Arithmetic Progressions ††thanks:
Supported by the project CRACKNP that has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No 853234).

Ivan Bliznets 11 0000-0003-2291-2556 Jesper Nedelof 22 0000-0003-1848-0076
Krisztina Szilágyi 22 0000-0003-3570-0528

###### Abstract

An _arithmetic progression_ is a sequence of integers in which the difference
between any two consecutive elements is the same. We investigate the
parameterized complexity of two problems related to arithmetic progressions,
called Cover by Arithmetic Progressions (CAP) and Exact Cover by Arithmetic
Progressions (XCAP). In both problems, we are given a set $X$ consisting of
$n$ integers along with an integer $k$, and our goal is to find $k$ arithmetic
progressions whose union is $X$. In XCAP we additionally require the
arithmetic progressions to be disjoint. Both problems were shown to be NP-
complete by Heath [IPL’90].

We present a $2^{O(k^{2})}poly(n)$ time algorithm for CAP and a
$2^{O(k^{3})}poly(n)$ time algorithm for XCAP. We also give a fixed parameter
tractable algorithm for CAP parameterized below some guaranteed solution size.
We complement these findings by proving that CAP is Strongly NP-complete in
the field $\mathbb{Z}_{p}$, if $p$ is a prime number part of the input.

###### Keywords:

Arithmetic Progressions Set Cover Parameterized Complexity Number Theory

##  1 Introduction

In the Set Cover problem one is given a universe $U$ and a set system
$\mathcal{S}\subseteq 2^{U}$ of subsets of $U$, along with an integer $k$. The
challenge is to detect whether there exist sets
$S_{1},\ldots,S_{k}\in\mathcal{S}$ such that $\bigcup_{i=1}^{k}S_{i}=U$.
Unfortunately, the problem is $W[2]$-hard parameterized by $k$ [11, Theorem
13.28], and thus we do not expect an algorithm with Fixed Parameter Tractable
(FPT) runtime, i.e. runtime $f(k)|x|^{O(1)}$ for some function $f$ and input
size $|x|$.

However, Set Cover is incredibly expressive, and it contains many well-studied
parameterized problems such as $d$-Hitting Set (for a constant $d$), Vertex
Cover and Feedback Vertex Set (see [11]), albeit the last problem requires an
exponential number of elements. While all these mentioned special cases are
FPT parameterized by $k$, many other special cases of Set Cover remain
$W[1]$-hard, and the boundary between special cases that are solvable in FPT
and $W[1]$-hard has been thoroughly studied already (see e.g. Table 1 in [6]).
An especially famous special case is the Point Line Cover problem, in which
one is given points $U\subseteq\mathbb{Z}^{2}$ and asked to cover them with at
most $k$ line segments. While it is a beautiful and commonly used exercise to
show this problem is FPT parameterized by $k$,111A crucial insight is that any
line containing at least $k+1$ points must be in a solution. many slight
geometric generalizations (such as generalizing it to arbitrary set systems of
VC-dimension $2$ [6]) are already $W[1]$-hard.

In this paper we study another special case of Set Cover, related to
_Arithmetic Progressions (APs)_. Recall that an AP is a sequence of integers
of the form $a,a+d,a+2d,\ldots,a+xd$, for some integers $x$, _start value_ $a$
and _difference_ $d$. We study two computational problems: Cover by APs
(abbreviated with CAP) and Exact Cover by APs (abbreviated with XCAP). In both
problems we are given a set of integers $X=\\{x_{1},x_{2},\dots,x_{n}\\}$, and
our goal is to find the smallest number of APs $s_{1},s_{2},\dots,s_{k}$
consisting of only elements in $X$ such that their union covers222We
frequently interpret APs as sets by omitting the order, and ”covers” can be
read as ”contains”. exactly the set $X$. In the XCAP problem, we additionally
require that the APs do not have common elements. While CAP and XCAP are
already known to be weakly NP-complete since the 90’s [14], the problems have
been surprisingly little studied since then.

The study of the parameterized complexity of CAP and XCAP can be motivated
from several perspectives.

  * •

The Set Cover perspective:  CAP and XCAP are natural special cases of Set
Cover for which the parameterized complexity is unclear. While the problem
looks somewhat similar to Point Line Cover, the crucial insight1 towards
showing it is FPT in $k$ does not apply since an AP can be covered with 2
other AP’s. In order to understand the jump in complexity from FPT to
$W[1]$-hardness of restricted Set Cover problems better, it is natural to
wonder whether properties weaker than the one of Point Line Cover1 also are
sufficient for getting FPT algorithms.

  * •

The practical perspective: There is a connection between these problems and
some problems that arise during the manufacture of VLSI chips [13]. The
connection implies the NP-hardness of the latter problems. Bast and Storandt
[3, 4] used heuristics for these problems to compress bus timetables and speed
up the process of finding the shortest routes in public transportation
networks.

  * •

The additive number theory perspective: The extremal combinatorics of covers
with (generalized) APs is a very well studied in the field of additive
combinatorics. This study already started in the 50’s with conjectures made by
among others Erdös (see [9] and the references therein), and recently results
in spirit of covering sets of integers with sets of low additive energy (of
which APs are a canonical example) such as Freiman’s Theorem and the Balog-
Szemerédi-Gowers Theorem also found algorithmic applications [7, 8].

  * •

The "not about graphs" perspective: Initially, applications of FPT algorithms
were mostly limited to graph problems.333There has even been a series of
workshops titled ”Parameterized Complexity: Not-About-Graphs” (link) to extend
the FPT framework to other fields. More recently, FPT algorithms have
significantly expanded the realm of their applicability. It now includes
geometry, computational social choice, scheduling, constraint satisfiability,
and many other application domains. However, at this stage the interaction of
number theory and FPT algorithms seems to be very limited.

### Our Contributions.

Our main results are FPT algorithms for CAP and XCAP:

######  Theorem 1.1 ().

CAP admits an algorithm running in time $2^{O(k^{2})}poly(n)$.

On a high level, this theorem is proved with a bounded search tree technique
(similar to Point Line Cover): In each recursive call we branch on which AP to
use. Since $k$ is the number of APs in any solution the recursion depth is at
most $k$. The difficulty however, is to narrow down the number of recursive
calls made by each recursive call. As mentioned earlier, the crucial insight1
does not apply since an AP can be covered with 2 other AP’s. We achieve this
by relying non-trivially on a result (stated in Theorem 2.1) by Crittenden and
Vanden Eynden [9] about covering an interval of integers with APs, originally
conjectured by Erdös. The proof of this theorem is outlined in Section 3.

######  Theorem 1.2 ().

XCAP admits an algorithm running in time $2^{O(k^{3})}poly(n)$.

On a high level, the proof of this theorem follows the proof of Theorem 1.1.
However, to accomodate the requirement that the selected APs are disjoint we
need a more refined recursion strategy. The proof of this theorem is outlined
in Section 4.

We complement these algorithms with a new hardness result. Already in the
1990s, the following was written in the paper that proved weak NP-hardness of
CAP and XCAP:

  * “

Because the integers used in our proofs are exponentially larger than $|X|$,
we have not shown our problems to be NP-complete in the strong sense [..].
Therefore, there is hope for a pseudopolynomial time algorithm for each
problem.

”

— Heath [14]

While we do not directly make progress on this question, we show that two
closely related problems _are_ strongly NP-hard. Specifically, if $p$ is an
integer, we define an AP in $\mathbb{Z}_{p}$ as a sequence of the form

$a,a+d\ (\mathrm{mod}\ p),a+2d\ (\mathrm{mod}\ p),\ldots,a+xd\ (\mathrm{mod}\
p).$

In the Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ problem one is
given as input an integer $p$ and a set $X\subseteq\mathbb{Z}_{p}$ and asked
to cover $X$ with APs in $\mathbb{Z}_{p}$ that are contained in $X$ that cover
$X$. In Exact Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ we
additionally require the APs to be disjoint. We show the following:

######  Theorem 1.3 ().

Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ and Exact Cover by
Arithmetic Progressions in $\mathbb{Z}_{p}$ are strongly NP-complete.

While this may hint at strong NP-completeness for CAP and XCAP as well, since
often introducing a (big) modulus does not incur big jumps in complexity in
number theoretic computational problems (confer e.g. $k$-SUM, Partition,
etc.), we also show that our strategy cannot directly be used to prove CAP and
XCAP to be strongly-NP. Thus this still leaves the mentioned question of Heath
[14] open. This result is proven in Section 5.

Finally, we illustrate that CAP is generalized by a variant of Set Cover that
allows an FPT algorithm for a certain below guarantee parameterization. In
particular, CAP always has a solution consisting of $|X|/2$ APs that cover all
sets.

######  Theorem 1.4 ().

There is an $2^{O(k)}n^{O(1)}$ time algorithm that detects if a given set $X$
of integers can be covered with at most $|X|/2-k$ APs.

This result is proved in Section 6.

##  2 Preliminaries

For integers $a,b$ we denote by $[a,b]$ a set $\\{a,a+1,\dots,b\\}$, for $a=1$
instead of $[1,b]$ we use a shorthand $[b]$, i.e. $[b]=\\{1,2,\dots,b\\}$. For
integers $a,b$ we write $a|b$ to show that $a$ divides $b$. For integers
$a_{1},\dots,a_{n}$ we denote their greatest common divisor by
$gcd(a_{1},\dots,a_{n})$.

An _arithmetic progression_ (AP) is a sequence of numbers such that the
difference of two consecutive elements is the same. While AP is a sequence, we
will often identify an AP with the set of its elements. We say an AP _stops in
between_ $l$ and $r$ if it largest element is in between $l$ and $r$. We say
it _covers_ a set $A$ if all integers in $A$ occur in it. Given an AP
$a,a+d,a+2d,\dots$ we call $d$ the _difference_. We record the following easy
observation:

######  Observation.

The intersection of two APs is an AP.

If $X$ is a set of integers, we denote

$\displaystyle X^{>c}$ $\displaystyle=\\{x|x\in X,x>c\\},\quad X^{\geq c}$
$\displaystyle=\\{x|x\in X,x\geq c\\},$ $\displaystyle\quad X^{<c}$
$\displaystyle=\\{x|x\in X,x<c\\},\quad X^{\leq c}$ $\displaystyle=\\{x|x\in
X,x\leq c\\}.$

Given a set $X$ and an AP $A=\\{a,a+d,a+2d,\dots\\}$, we denote by $A\sqcap X$
the longest prefix of $A$ that is contained in $X$. In other words, $X\sqcap
A=\\{a,a+d,\dots,a+\ell d\\}$, where $\ell$ is the largest integer such that
$a+\ell^{\prime}d\in X$ for all $\ell^{\prime}\in\\{0,\dots,\ell\\}$.

For a set of integers $X$ and integer $p$ we denote by $X_{p}=\langle x\bmod
p|x\in X\rangle$. Here the $\langle\rangle$ symbols indicate that we build a
_multiset_ instead of a set (so each number is replaced with its residual
class mod $p$ and we do not eliminate copies).

We call an AP $s$ _infinite_ if there are integers $a,d$ such that
$s=(a,a+d,a+2d,\dots)$. Note that under this definition, the constant AP
containing only one number and difference $0$ is also infinite.

The following result by Crittenden and Vanden Eynden will be crucial for many
of our results:

######  Theorem 2.1 ([9]).

Any $k$ infinite APs that cover the integers $\\{1,\ldots,2^{k}\\}$ cover the
whole set of positive integers.

##  3 Algorithm for Cover by Arithmetic Progressions (CAP)

Before describing the algorithm, we introduce an auxiliary lemma. This lemma
will be crucially used to narrow down the number of candidates for an AP to
include in the solution to at most $2^{k}$.

######  Lemma 1 ().

Let $s_{0}$ be an AP with at least $t+1$ elements. Let $s_{1},\dots,s_{k}$ be
APs that cover the elements $s_{0}(0),\dots,s_{0}(t-1)$, but not $s_{0}(t)$.
The APs $s_{1},\dots,s_{k}$ may contain other elements. Suppose that each AP
$s_{1},\dots,s_{k}$ has an element larger than $s_{0}(t)$. Then we have
$t<2^{k}$.

###### Proof.

Suppose for contradiction that $t\geq 2^{k}$. Let $t_{i}$ be the intersection
of $s_{i}$ and $s_{0}$ for $i\in[k]$. Note that by Observation Observation,
$t_{1},\dots,t_{k}$ are APs as well. For $i\in[k]$, we define
$T_{i}=\\{j\in\\{0,\dots,t-1\\}:\>s_{0}(j)\in t_{i}\\}$.

We claim each $T_{i}$ is an AP: To see this, let $a<b<c$ be consecutive (with
respect to the sorted order) elements of $T_{i}$ (if $|T_{i}|\leq 2$, it is
trivially an AP). The elements $s_{0}(a),s_{0}(b),s_{0}(c)$ are consecutive
elements of $t_{i}$. Thus $s_{0}(b)-s_{0}(a)=s_{0}(c)-s_{0}(b)=d_{0}$, where
$d_{0}$ is the difference of $s_{0}$. The above equality can be written as

$(s_{0}(0)+bd_{0})-(s_{0}(0)+ad_{0})=(s_{0}(0)+cd_{0})-(s_{0}(0)+bd_{0}).$

Thus we get $b-a=c-b$, as required.

Note that the APs $T_{1},\dots,T_{k}$ cover $\\{0,\ldots,t-1\\}$. For
$i\in[k]$, denote by $T_{i}^{\prime}$ the infinite extension of $T_{i}$ (that
is, $T_{i}^{\prime}$ contains all integers whose difference with an entry of
$T_{i}$ is a multiple of the difference of $T_{i}$, if $T_{i}$ has only one
element then $T_{i}^{\prime}$ is constant infinite AP). By Theorem 2.1,
$T_{1}^{\prime},\dots,T_{k}^{\prime}$ cover the whole set $\mathbb{N}$. In
particular, $t\in T_{i}^{\prime}$ for some $i$. By assumption, $s_{i}$ has an
element larger than $s_{0}(t)$, so $s_{0}(t)$ is covered by $s_{i}$, which
leads to a contradiction. ∎

Equipped with Lemma 1 we are ready to prove our first main theorem:

See 1.1

###### Proof.

Denote the set of integers given in the input by $X$. Without loss of
generality we can consider only solutions where all APs are inclusion-maximal,
i.e. solutions where none of the APs can be extended by an element of $X$. In
particular, given an element $a$ and difference $d$, the AP is uniquely
determined: it is equal to $\\{a-\ell d,\dots,a-d,a,a+d,\dots,a+rd\\}$, where
$\ell,r$ are largest integers such that $a-\ell^{\prime}d\in X$ for all
$\ell^{\prime}\in[\ell]$ and $a+r^{\prime}d\in X$ for all $r^{\prime}\in[r]$.

Our algorithm consists of a recursive function
$\textsc{Covering}(C,k_{1},k_{2})$. The algorithm takes as input a set $C$ of
elements and assumes there are APs $s_{1},\ldots,s_{k_{1}}$ whose union equals
$C$, so the elements of $C$ are ‘covered’ already. With this assumption, it
will detect correctly whether there exist $k_{2}$ additional APs that cover
all remaining elements $X\setminus C$ from the input. Thus
$\textsc{Covering}(\emptyset,0,k)$ indicates whether the instance is a Yes-
instance. At Line 4 we solve the subproblem, in which set $C$ is already
covered, in $2^{k^{2}}poly(n)$ time if $|X\setminus C|\leq k^{2}$. This can be
easily done by writing the subproblem as an equivalent instance of Set Cover
(with universe $U=X\setminus C$ and a set for each AP in $U$) and run the
$2^{|U|}poly(n)=2^{k^{2}}poly(n)$ time algorithm for Set Cover from [5].

For larger instances, we consider the $k^{2}+1$ smallest uncovered elements
$u_{1},\dots,u_{k^{2}+1}$ in Line 6, and guess (i.e. go over all
possibilities) $u_{i}$ and $u_{j}$ such that $u_{i}$ and $u_{j}$ both belong
to some AP $s$ in a solution and none of the AP’s $s_{1},\ldots,s_{k_{1}}$
stops (i.e., has its last element) in between $u_{i}$ and $u_{j}$. In order to
prove correctness of the algorithm, we will show later in Claim 1 such $u_{i}$
and $u_{j}$ exist.

Note that $u_{i}$ and $u_{j}$ are not necessarily consecutive in $s$, so we
can only conclude that the difference of $s$ divides $u_{j}-u_{i}$. We use
Lemma 1 to lower bound the difference of $s$ with $(u_{j}-u_{i})/2^{k}$, and
after we guessed the difference we recurse with the unique maximal AP with the
guessed difference containing $u_{i}$ (and $u_{j}$). In pseudocode, the
algorithm works as follows:

Algorithm 1 Algorithm for CAP

1:Algorithm $\textsc{Covering}(C,k_{1},k_{2})$

2:Let $k=k_{1}+k_{2}$

3:if $|X\setminus C|\leq k^{2}$ then

4: Use the algorithm for Set Cover from [5]

5:else

6: Let $u_{1},\dots,u_{k^{2}}$ be the $k^{2}+1$ smallest elements of
$X\setminus C$

7: for $i=1\dots k^{2}$ do

8: for $j=i+1\dots k^{2}+1$ do

9: Let $D=u_{j}-u_{i}$

10: for $\ell=1\dots 2^{k}$ do

11: if $\ell$ divides $D$ then

12: Let $s=\textsc{MakeAP}(u_{i},D/\ell)$

13: if $\textsc{Covering}(C\cup s,k_{1}+1,k_{2}-1)$ then

14: return true

15: return false

The procedure $\textsc{MakeAP}(a,d)$ returns the AP
$\\{a-\ell_{1}d,\dots,a-d,a,a+d,\dots,a+\ell_{2}d\\}$, where $\ell_{1}$
(respectively, $\ell_{2}$) are the largest numbers such that
$a-\ell^{\prime}d\in X$ for all $\ell^{\prime}\leq\ell_{1}$ (respectively,
$a+\ell^{\prime}d\in X$ for all $\ell^{\prime}\leq\ell_{2}$). It is easy to
see that if Algorithm 1 outputs true, we indeed have a covering of size $k$:
Since we only add elements to $C$ if they are indeed covered by an AP, and
each time we add elements to $C$ because of an AP we decrease our budget
$k_{2}$.

For the other direction of correctness, we first claim that our algorithm will
indeed at some moment consider an AP of the solution.

######  Claim 1.

Suppose there exist an AP-covering $s_{1},\dots,s_{k}$, and let
$k_{1}\in\\{0,\ldots,k\\}$ be an integer and let $\cup_{i=1}^{k_{1}}s_{i}=C$.
Then in the recursive call Covering$(C,k_{1},k-k_{1})$ we have in some
iteration of the for-loops $s=s_{h}$ at Line 12, for some
$h\in\\{k_{1}+1,\dots,k\\}$.

######  Proof of Claim.

Consider the set $B$ consisting of the $k^{2}+1$ smallest elements of
$X\setminus C$. By the pigeonhole principle, there is an
$h\in\\{j+1,\dots,k\\}$ such that $s_{h}$ covers at least $k+1$ elements of
$B$. Thus, there are two consecutive elements of $B\cap s_{h}$,
$s_{h}(\alpha)$ and $s_{h}(\beta)$, between which no AP
$s_{1},\ldots,s_{k_{1}}$ ends. Without loss of generality, we may assume that
$s_{h}(\alpha)$ and $s_{h}(\beta)$ are the closest such pair (i.e. the pair
such that $|s_{h}(\alpha)-s_{h}(\beta)|$ is minimal). By applying Lemma 1, we
conclude that there are at most $2^{k}-1$ elements of $s_{h}$ between
$s_{h}(\alpha)$ and $s_{h}(\beta)$. In other words, the difference of $s_{h}$
is a divisor of $s_{h}(\beta)-s_{h}(\alpha)$ and at least
$(s_{h}(\beta)-s_{h}(\alpha))/2^{k}$. Therefore, in some iteration of the for-
loops we get $s=s_{h}$.∎

Using the above claim, it directly follows by induction on $k_{2}=0,\ldots,k$
that if there is a covering $s_{1},\ldots,s_{k}$ of $X$ such that
$\cup_{i=1}^{k_{1}}s_{i}=C$, then the function
$\textsc{Covering}(C,k-k_{2},k_{2})$ returns true.

Let us now analyse the running time of the above algorithm. The recursion tree
has height $k$ (since we reduce $k$ by one on every level). The maximum degree
is $2^{k}k^{4}$, so the total number of nodes is $2^{O(k^{2})}$. The running
time at each node is at most $2^{O(k^{2})}poly(n)$. Therefore, the overall
running time is $2^{O(k^{2})}poly(n)$. ∎

##  4 FPT Algorithm for Exact Cover by Arithmetic Progressions

Now we show that XCAP is Fixed Parameter Tractable as well. Note that this
problem is quite different in character than CAP. For example, as opposed to
CAP, in XCAP we cannot describe an AP with only one element and its
difference. Namely, it is not always optimal to take the longest possible AP:
for example, if $X=\\{0,4,6,7,8,9\\}$, the optimal solution uses the
progression $0,4$ rather than $0,4,8$. While we still apply a recursive
algorithm, we significantly need to modify our structure lemma (shown below in
Lemma 2) and the recursive strategy.

Before we proceed with presenting the FPT algorithm for Exact Cover by
Arithmetic Progressions (XCAP) we state an auxiliary lemma.

######  Lemma 2 ().

Let $s_{1},s_{2},\dots,s_{k}$ be a solution of an instance of XCAP with input
set $X$. Let $s$ be an AP that is contained in $X$. For each $i\in[k]$, we
denote by $t_{i}$ the intersection of $s$ and $s_{i}$. Suppose that for some
$i$, $t_{i}$ has at least $k+1$ elements. Then there are at most $2^{k-1}-1$
elements of $s$ between any two consecutive elements of $t_{i}$.

###### Proof.

Without loss of generality, we may assume that $i=1$. Note that $t_{1}$ is a
subset of $s$ and AP. Hence between any two consecutive members of $t_{1}$ we
have the same number of elements of $s$. Let us consider the first $k+1$
members of $t_{1}$, denoted by $t_{1}(0),t_{1}(1),\dots,t_{1}(k)$. For any
$j\in[0,k-1]$ all elements of $s$ between $t_{1}(j)$ and $t_{1}(j+1)$ must be
covered by $s_{2},s_{3},\dots,s_{k}$. Therefore, by Lemma 1 one of the
arithmetic progressions $s_{2},s_{3},\dots,s_{k}$ must stop before $t_{1}(1)$.
Similarly, another AP from $s_{2},s_{3},\dots,s_{k}$ must stop before
$t_{1}(2)$. By repeatedly applying this argument, we conclude that all APs
$s_{2},s_{3},\dots,s_{k}$ must stop before $t_{1}(k-1)$. Hence, the elements
of $s$ between $t_{1}(k-1)$ and $t_{1}(k)$ are uncovered which leads to a
contradiction. ∎

Now we have all ingredients to prove the main theorem of this section.

See 1.2

###### Proof.

Let $X=\\{a_{1},\dots,a_{n}\\}$ be the input set. Without loss of generality,
we may assume that $a_{1}<\dots<a_{n}$. Assume that the input instance has a
solution with $k$ APs: $o_{1},\dots,o_{k}$. Let $d^{\prime}_{i}$ be the
difference of $o_{i}$. Our algorithm partition recursively calls itself and is
described in Algorithm 2. The algorithm has the following parameters:
$T_{1},\dots,T_{k},P_{1},\dots,P_{k},d_{1},d_{2},\dots,d_{k}$. The sets
$T_{i}$ describe the elements that are in $o_{i}$ (i.e. the elements that are
definitely covered by $o_{i}$). The integer $d_{i}$ is either $0$ or equal to
the guessed value of the difference of the AP $o_{i}$. Once we assign a non-
zero value to $d_{i}$, we never change it within future recursive calls. We
denote by $P_{i}$ the set of "potentially covered" elements. Informally,
$P_{i}$ consists of elements that could be covered by $o_{i}$ unless $o_{i}$
is interrupted by another AP. Formally, if for an AP $o_{i}$ we know two
elements $a,b\in o_{i}$ ($a<b$), and the difference $d_{i}$ then
$P_{i}=\\{b+d_{i},b+2d_{i},\dots b+\ell d_{i}\\}$ where $\ell$ is the largest
number such that: $\\{b+d_{i},b+2d_{i},\dots b+\ell d_{i}\\}\subset X$ and
none of the elements of the set $\\{b+d_{i},b+2d_{i},\dots b+\ell d_{i}\\}$
belong to $T_{j}$ for some $j\neq i$, $j\in[k]$.

Algorithm 2 Algorithm for XCAP

1:Algorithm $\textsc{Partition}(X,T_{1},\dots
T_{k},P_{1},\dots,P_{k},d_{1},\dots,d_{k})$

2:if there are $i,j\in[k]$ s.t. $i\neq j$ and $P_{i}\cap P_{j}\neq\emptyset$
then

3: Let $c$ be the smallest element s.t. $\exists i,j$, $c\in P_{i}\cap P_{j}$,
and $i<j$

4:
$\textsc{Partition}(X,T_{1},\dots,T_{k},P_{1},\dots,P_{i-1},P_{i}^{<c},P_{i+1},\dots,P_{k},d_{1},\dots,d_{k})$

5:
$\textsc{Partition}(X,T_{1},\dots,T_{k},P_{1},\dots,P_{j-1},P_{j}^{<c},P_{j+1},\dots,P_{k},d_{1},\dots,d_{k})$

6:else if there is an $i$ such that $T_{i}=\\{a_{\alpha},a_{\beta}\\}$ and
$d_{i}=0$ then

7: for $(b_{1},\dots,b_{k})\in\\{0,1,\dots,2^{k}+1\\}^{k}$ do

8: $g\leftarrow gcd(a_{\beta}-a_{\alpha},b_{1}d_{1},\dots b_{k}d_{k})$

9: $D_{i}\leftarrow\\{g,\frac{g}{2},\dots,\frac{g}{k(k+1)}\\}$

10: for $d\in D_{i}$ and $d$ is integer do

11: $d_{i}\leftarrow d$

12: $T_{i}\leftarrow\\{a_{\alpha},a_{\alpha}+d_{i},\dots,a_{\beta}\\}$

13: $C^{\infty}\leftarrow\\{a_{\beta}+d_{i},a_{\beta}+2d_{i},\dots\\}$

14: $P_{i}\leftarrow C^{\infty}\sqcap X$

15: if for all $j\in[k]\setminus\\{i\\}$ we have $T_{i}\cap T_{j}=\emptyset$
then

16: for $j\in[k]\setminus\\{i\\}$ do

17: $P_{j}\leftarrow\textsc{Update}(P_{j},T_{i})$ $\triangleright$ remove ints
larger than min($P_{j}\cap T_{i}$)

18:
$\textsc{Partition}(X,T_{1},\dots,T_{k},P_{1},\dots,P_{k},d_{1},\dots,d_{k})$

19:else if $X\setminus(P\cup T)=\emptyset$ then

20: return $o_{1}=T_{1}\cup P_{1},\dots,o_{k}=T_{k}\cup P_{k}$

21:else

22: $a_{\beta}\leftarrow min(X\setminus(T\cup P))$

23: if there is an $i$ such that $|T_{i}|<2$ then

24: $J\leftarrow\\{i|i\in[k]\text{ and }|T_{i}|<2\\}$

25: for $i\in J$ do

26: $T_{i}\leftarrow T_{i}\cup\\{a_{\beta}\\}$

27:
$\textsc{Partition}(X,T_{1},\dots,T_{k},P_{1},\dots,P_{k},d_{1},\dots,d_{k})$

28: else

29: abort $\triangleright$ this branch does not generate a solution

Initially, we call the algorithm partition with parameters
$T_{1}=\\{a_{1}\\}$,
$T_{2}=\dots=T_{k}=P_{1}=\dots=P_{k}=\emptyset,d_{1}=d_{2}=\dots=d_{k}=0$. We
denote by $T=\cup_{i}T_{i}$ and $P=\cup_{i}P_{i}$. Let $a_{\beta}$ be the
smallest element of the input sequence that does not belong to $T\cup P$. For
each $i\in[k]$ such that $|T_{i}|\leq 1$, we recursively call
$\textsc{partition}(T_{1},\dots,T_{i-1},T_{i}^{\prime},T_{i+1},\dots,T_{k},P_{1},\dots,P_{k})$,
where $T_{i}^{\prime}=T_{i}\cup\\{a_{\beta}\\}$. In other words, we consider
all possible APs that cover $a_{\beta}$. We do not assign $a_{\beta}$ to
$i$-th AP with $|T_{i}|\geq 2$ as for such APs we know that $a_{\beta}\not\in
o_{i}$ (since $a_{\beta}\not\in P_{i}$).

If in the input for some $i$ we have $|T_{i}|=2$ and $d_{i}=0$ then we branch
on the value of the difference of the $i$-th AP. Let
$T_{i}=\\{a_{\alpha},a_{\beta}\\}$, where $a_{\beta}>a_{\alpha}$. By
construction (specifically, by the choice of $a_{\beta}$), all elements of the
sequence $B=\\{a_{\alpha+1},a_{\alpha+2},\dots,a_{\beta-1}\\}$ belong to
$P\cup T$, i.e. can be covered by at most $k$ APs. Note that purely based on
the knowledge of two elements $a_{\alpha},a_{\beta}\in o_{i}$ we cannot
determine immediately the difference of $o_{i}$, because
$a_{\alpha},a_{\beta}$ might not be consecutive elements of $o_{i}$. In other
words, it could happen that some elements of $B$ belong to $o_{i}$. Therefore
we need to consider cases when potentially covered elements from some $P_{j}$
actually belong to $o_{i}$ instead of $o_{j}$. We note that the number of
elements between $a_{\alpha}$ and $a_{\beta}$ can be very large, so a simple
consideration of all cases where the difference of $o_{i}$ is a divisor of
$a_{\beta}-a_{\alpha}$ will not provide an FPT-algorithm.

Instead of considering all divisors we use Lemma 2 and bound the number of
candidates for value of the difference of $o_{i}$. Note that we allow integers
to be $0$ here, and define that all integers are a divisor of $0$. Hence $a|0$
is always true and $gcd(0,y_{1},y_{2},\dots)=gcd(y_{1},y_{2},\dots)$.

Informally, for all known differences $d_{j}$ up to this point (i.e. all
$d_{j}\neq 0$) we branch on the smallest positive value $b_{j}$ such that
$d^{\prime}_{i}|b_{j}d_{j}$, where $d^{\prime}_{i}$ is the difference of the
$i$-th AP in the solution that we want to find. We treat all cases when
$b_{j}>2^{k}+1$ at once, and instead of the actual value we assign $0$ to a
variable responsible for storing value of $b_{j}$. Intuitively, $b_{j}$
describes the number of elements of $o_{j}$ between two consecutive
interruptions by $o_{i}$. By Lemma 2, if $b_{j}$ is large (larger than
$2^{k}+1$), each of these interruptions implies that an AP stops.

Formally, for each $k$-tuple
$(b_{1},\dots,b_{k})\in\\{0,\dots,2^{k}+1\\}^{k}$, we do the following. Let
$g=gcd(a_{\beta}-a_{\alpha},b_{1}d_{1},\dots,b_{k}d_{k})$. From the definition
of $b_{j}$ it follows that $d^{\prime}_{i}|g$.

######  Claim 2.

If all previous branchings are consistent with a solution $o_{1},\dots,o_{k}$
then $d^{\prime}_{i}\geq\frac{g}{k(k+1)}.$

######  Proof of Claim.

Indeed, if $d^{\prime}_{i}=g/t$ and $t>k(k+1)$ then between $a_{\alpha}$ and
$a_{\alpha}+g$ there are at least $k(k+1)$ elements from $o_{i}$. All these
elements are covered by sets $P_{1},\dots,P_{i-1},P_{i+1},\dots,P_{k}$.
Therefore, by the pigeonhole principle there is an index $q$ such that $P_{q}$
contains at least $k+1$ elements. This means that $P_{q}$ and $o_{i}$ have at
least $k+1$ common elements ($P_{q}$ is intersected by $o_{i}$ at least $k+1$
times). Denote these common elements by $c_{1},\dots,c_{t}$ and let $e$ be the
number of elements of $P_{q}$ between $c_{\ell}$ and $c_{\ell+1}$ ($e$ does
not depend on $\ell$ as $P_{q}$ and $o_{i}$ are APs). First of all, recall
that $c_{\ell},c_{\ell+1}$ are from interval $(a_{\alpha},a_{\alpha}+g)$.
Therefore, $(e+1)d_{q}=c_{\ell+1}-c_{\ell}<g$. Moreover, by Lemma 2 (applied
with $s=P_{q}$ and $s_{i}=o_{i}$), we have $e\leq 2^{k-1}-1$. Taking into
account that $d^{\prime}_{i}|(e+1)d_{q}$ and $e\leq 2^{k-1}-1$ we have that
$g$ divides $(e+1)d_{q}$ which contradicts $(e+1)d_{q}<g$.∎

From the previous claim it follows that
$d^{\prime}_{i}\in\\{g,g/2,\dots,g/k(k+1)\\}$ and we have the desired bound on
the number of candidates for the value of the difference of $o_{i}$. We branch
on the value of $d^{\prime}_{i}$, i.e. in each branch we assign to $d_{i}$
some integer value from the set $\\{g,g/2,\dots,g/k(k+1)\\}$. In other words,
for each $d\in\\{g,g/2,\dots,g/k(k+1)\\}$ we call

$\textsc{partition}(T_{1},\dots,T_{i}^{\prime},\dots,T_{k},P_{1}^{\prime},\dots,P_{k}^{\prime},d_{1},\dots,d_{i-1},d,d_{i+1},\dots,d_{k}),$

where $C_{d}=\\{a_{\alpha},a_{\alpha}+d,\dots,a_{\beta}-d,a_{\beta}\\}$,
$C_{d}^{\infty}=\\{a_{\beta}+t,a_{\beta}+2t,\dots\\}$,
$T_{i}^{\prime}=T_{i}\cup C_{d}$, $P^{\prime}_{i}=C_{d}^{\infty}\sqcap X$ and
for $j\neq i$ we set $P_{j}^{\prime}=\textsc{Update}(P_{j},T_{i})$. The
function $\textsc{Update}(A,B)$ returns $A^{<x}$, where $x=\min(A\cap B)$ (if
$A\cap B=\emptyset$, it returns $A$). If in some branch the sequence
$a_{\alpha},a_{\alpha}+d_{i},\dots,a_{\beta}-d_{i},a_{\beta}$ intersects $T$,
we abort this branch. Overall, in order to determine the difference of $o_{i}$
after discovering $a_{\alpha},a_{\beta}\in o_{i}$ we create at most
$(2^{k}+2)^{k}\cdot k(k+1)=2^{O(k^{2})}$ branches.

Let us now compute the number of nodes in the recursion tree. Observe that we
never remove elements from $T$. Consider a path from the root of the tree to a
leaf. It contains at most $2k$ nodes of degree at most $k$ (adding two first
elements to $T_{i}$), at most $k^{2}$ nodes of degree 2 (resolving the
intersections of two APs, lines 2-5 in pseudocode) and at most $k$ nodes of
degree $2^{O(k^{2})}$ (determining the difference of an AP that contains two
elements). Hence, the tree has at most $k^{2k}\cdot
2^{k^{2}}\cdot(2^{O(k^{2})})^{k}=2^{O(k^{3})}$ leaves. Therefore, the overall
number of nodes in the recursion tree and the running time of the algorithm is
$2^{O(k^{3})}poly(n)$.

Claim 2 proves that we iterate over all possibilities. Hence, our algorithm is
correct. ∎

##  5 Strong NP-hardness of Cover by Arithmetic Progressions in
$\mathbb{Z}_{p}$

A natural question to ask, in order to prove Strong NP-hardness for CAP, is
whether we can replace an input set $X$ with an equivalent set which has
smaller elements. Specifically, could we replace the input number with numbers
polynomial in $|X|$, while preserving the set of APs? This intuition can be
further supported by result on Simultaneous Diophantine approximation that
exactly achieve results in this spirit (though with more general properties
and larger upper bounds) [12]. However, it turns out that this is not always
the case, as we show in Lemma 3. This means that one of the natural approaches
for proving strong NP-hardness of CAP does not work: namely, not all sets $X$
can be replaced with set $X^{\prime}$ of polynomial size which preserves all
APs in $X$.

######  Lemma 3 ().

Let $x_{1}=0$, $x_{i}=2^{i-2}$ for $i\geq 2$ and
$X_{n}=\\{x_{1},\dots,x_{n+2}\\}$. Then for any polynomial $p$ there exists an
integer $n$ such that there is no set $A_{n}=\\{a_{1},\dots,a_{n+2}\\}$ that
satisfies the following criteria:

  * •

$a_{i}\leq p(n)$ for all $i\in[n+2]$,

  * •

For all $i,j,k\in[n+2]$, the set $\\{x_{i},x_{j},x_{k}\\}$ forms an AP if and
only if $\\{a_{i},a_{j},a_{k}\\}$ forms an AP.

###### Proof.

Assume for contradiction that there is a polynomial $p$ such that for any $n$,
we can construct a set $A_{n}$ with elements smaller than $p(n)$ which
preserves the APs of size 3 in $X_{n}$. Without loss of generality, we may
assume that $a_{1}=0$ (by subtracting $a_{1}$ from all elements of $A_{n}$ and
using $2p$ instead of $p$).

Clearly if $|X_{n}|\geq 4$ we must have $a_{2}\neq 0$. If a set $\\{0,a,b\\}$
generates an AP, then $b\in\\{2a,-a,\frac{a}{2}\\}$. We know that
$x_{1},x_{j},x_{j+1}$ generate an AP for each $j\in[2,n-1]$, which implies
that for $i\geq 3$, $a_{i}$ is equal to $a_{i-1}$ multiplied by $2,-1$ or
$\frac{1}{2}$. Note that we cannot have $q_{1}<q_{2}$ such that
$a_{q_{1}}=a_{q_{2}}$. Indeed, if $q_{2}>q_{1}+1$ then
$a_{1},a_{q_{1}},a_{q_{2}}$ generates an AP while $x_{1},x_{q_{1}},x_{q_{2}}$
does not. It is left to consider case $q_{2}=q_{1}+1$. If $q_{2}<n$, $X_{n}$
contains the AP $x_{1},x_{q_{2}},x_{q_{2}+1}$, so
$\\{a_{1},a_{q_{2}},a_{q_{2}+1}\\}$ is an AP. Since $a_{q_{2}}=a_{q_{1}}$, we
have that $\\{a_{1},a_{q_{1}},a_{q_{2}+1}\\}$ also generates an AP which
contradicts the fact that $x_{1},x_{q_{1}},x_{q_{2}+1}$ is not an AP. If
$q_{2}=n$, then instead of the triple $\\{a_{1},a_{q_{2}},a_{q_{2}+1}\\}$ we
consider the triple $\\{a_{1},a_{q_{1}-1},a_{q_{1}}\\}$ and instead of
$x_{1},x_{q_{1}},x_{q_{2}+1}$ we consider $x_{1},x_{q_{1}-1},x_{q_{2}}$ and
get the contradiction as $n\geq 4$. Therefore all numbers
$a_{1},a_{2},\dots,a_{n}$ must be different.

Recall that for each $j>1$ we have either $a_{j}=2^{p_{j}}a_{2}$ or
$a_{j}=-2^{p_{j}}a_{2}$ for some integer $p_{j}$. As all numbers in the set
$\\{a_{1},a_{2},\dots,a_{n}\\}$ are different, we have that there is an index
$j$ such that $p_{j}>\frac{n}{8}$ or $p_{j}<-\frac{n}{8}$. Since all numbers
in $A$ must be integers we conclude that either $a_{2}>2^{\frac{n}{8}}$ or
$a_{p_{j}}>2^{\frac{n}{8}}$. Therefore we must have $p(n)\geq
2^{\frac{n}{8}}$, which is not true if we take $n$ sufficiently large. ∎

Unfortunately, we do not know how to directly circumvent this issue and
improve the weak NP-hardness proof of Heath [14] to _strong_ NP-hardness.
Instead, we work with a small variant of the problem in which we work in
$\mathbb{Z}_{p}$. The definition of APs naturally carries over to
$\mathbb{Z}_{p}$. It is easy to see that APs are preserved:

######  Claim 3.

Let $p$ be a prime and let $X$ be a set of integers that forms an AP. Then the
multiset $X_{p}$ generates AP in the field $\mathbb{Z}_{p}$.

######  Proof of Claim.

Note that $y-x=z-y$ implies $(y\bmod p)-(x\bmod p)\equiv_{p}(z\bmod p)-(y\bmod
p)$. Therefore, we have that $X_{p}$ is an AP in $\mathbb{Z}_{p}$.

However, the converse does not hold. Formally, if for some $p$ the multiset
$X_{p}$ is an AP in $\mathbb{Z}_{p}$ it is not necessarily true that $X$ is an
AP in $\mathbb{Z}$. For example, consider $X=\\{3,6,18\\}$ and $p=3$: we have
$X_{p}=\\{0,0,0\\}$ which is a (trivial) AP, while $X$ is not an AP.

We now show strong NP-completeness for the modular variants of CAP and XCAP.
In the Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ problem one is
given as input an integer $p$ and a set $X\subseteq\mathbb{Z}_{p}$ and asked
to cover $X$ with APs in $\mathbb{Z}_{p}$ that are contained in $X$ that cover
$X$. In Exact Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ we
additionally require the APS to be disjoint.

See 1.3

###### Proof.

We recall that Heath [14] showed that CAP and XCAP are weakly NP-complete via
reduction from Set Cover. Moreover, the instances of CAP and XCAP, obtained
after reduction from Set Cover, consist of numbers that are bounded by
$2^{q(n)}$ for some polynomial $q(n)$. To show that Cover by Arithmetic
Progressions in $\mathbb{Z}_{p}$ and Exact Cover by Arithmetic Progressions in
$\mathbb{Z}_{p}$ are strongly NP-complete we take a prime $p$ and convert
instances of CAP and XCAP with set $S$ into instances of Cover by Arithmetic
Progressions in $\mathbb{Z}_{p}$ and Exact Cover by Arithmetic Progressions in
$\mathbb{Z}_{p}$ respectively with a set $S_{p}$ (we can guarantee that the
multiset $S_{p}$ contains no equal numbers) and modulo $p$.

As shown in Claim 3, under such transformation a Yes-instance is converted
into a Yes-instance. However, if we take an arbitrary $p$ then a No-instance
can be mapped to a Yes-instance or $S_{p}$ can become a multiset instead of a
set. In order to prevent this, we carefully pick the value of $p$.

We need to guarantee that if $X$ is not an AP then $X_{p}$ also does not
generate an AP in $\mathbb{Z}_{p}$. Suppose
$X_{p}=\\{y_{1},y_{2},\dots,y_{k}\\}$ generates an AP in $\mathbb{Z}_{p}$
exactly in this order. We assume that $x_{i}$ maps into $y_{i}$, i.e.
$x_{i}\equiv_{p}y_{i}$. Since $X_{p}$ is an AP in $\mathbb{Z}_{p}$, we have

$y_{2}-y_{1}\equiv_{p}y_{3}-y_{2}\equiv_{p}\dots\equiv_{p}y_{k}-y_{k-1}.$

Since $X$ is not an AP there exists an index $j$ such that $x_{j}-x_{j-1}\neq
x_{j+1}-x_{j}$. Therefore, we have that $2x_{j}-x_{j-1}-x_{j+1}\neq 0$ and
$2y_{j}-y_{j-1}-y_{j+1}\equiv_{p}0$. Since $x_{i}\equiv_{p}y_{i}$ we conclude
that $p$ divides $2x_{j}-x_{j-1}-x_{j+1}$. Hence if we want to choose $p$ that
does not transform a No-instance into a Yes-instance, it is enough to choose
$p$ such that $p$ is not a divisor of $2x-y-z$ where $x,y,z$ are any numbers
from the input and $2x-y-z\neq 0$. Similarly, if we want $S_{p}$ to be a set
instead of a multiset, then for any different $x,y$ the prime $p$ should not
be a divisor of $x-y$. Note that the number of different non-zero values of
$2x-y-z$ and $x-y$ is at most $O(n^{3})$. Since all numbers are bounded by
$2^{q(n)}$ the values of $2x-y-z\neq 0$ and $x-y$ are bounded by $2^{q(n)+2}$.
Note that any integer $N$ has at most $\log N$ different prime divisors.
Therefore at most $O(n^{3})(q(n)+2)$ prime numbers are not suitable for our
reduction. In order to find a suitable prime number we do the following:

  * •

for each number from $2$ to $n^{6}(q(n)+2)^{2}$ check if it is prime (it can
be done in polynomial time [1]),

  * •

for each prime number $p^{\prime}\leq n^{6}(q(n)+2)^{2}$ check if there are
integers $x,y,z$ from the input such that ($2x-y-z\neq 0$ and
$2x-y-z\equiv_{p}0$) or $x\equiv_{p}y$ if such $x,y,z$ exist go to the next
prime number,

  * •

when the desired prime $p^{\prime}$ is found output instance $S_{p^{\prime}}$
with modulo $p^{\prime}$.

Note that number of primes not exceeding $N$ is at least $\frac{N}{2\log N}$
for large enough $N$. Hence by pigeonhole principle we must find the desired
$p^{\prime}$ as we consider all numbers smaller than $n^{6}(q(n)+2)^{2}$ and
$\frac{n^{6}(q(n)+2)^{2}}{\log({n^{6}(q(n)+2)^{2}})}>O(n^{3})(q(n)+2)$ for
sufficiently large $n$.

Therefore, in polynomial time we can find $p^{\prime}$ that is polynomially
bounded by $n$ and Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ with
input $(S_{p^{\prime}},p^{\prime})$ is equivalent to CAP with input $S$
(similarly for Exact Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ and
XCAP). Hence, Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ and Exact
Cover by Arithmetic Progressions in $\mathbb{Z}_{p}$ are strongly NP-complete.

∎

##  6 Parameterization Below Guarantee

In this section we present an FPT algorithm parameterized below guarantee for
a problem that generalizes CAP, namely $t$-Uniform Set Cover. The $t$-Uniform
Set Cover is a special case of the Set Cover problem in which all instances
$\mathcal{S},U$ satisfy the property that $\\{A\subseteq U:|A|=t\
\\}\subseteq\mathcal{S}$. Clearly the solution for the $t$-Uniform Set Cover
problem is at most $\lceil\frac{n}{t}\rceil$ where $n$ is the size of
universe. Note that CAP is a special case of $2$-Uniform Set Cover since any
pair of element forms an AP. Thus we focus on presenting a fixed parameter
tractable algorithm for the $t$-Uniform Set Cover problem parameterized below
$\lceil\frac{n}{t}\rceil$ (we consider $t$ to be a fixed constant). We note
that for a special case with $t=1$ the problem was considered in works [2,
10].

We will use the deterministic version of color-coding, which uses the
following standard tools:

######  Definition 1.

For integers $n,k$ a _$(n,k)$ -perfect hash family_ is a family $\mathcal{F}$
of functions from $[n]$ to $[k]$ such that for each set $S\subseteq[n]$ of
size $k$ there exists a function $f\in\mathcal{F}$ such that $\\{f(v):v\in
S\\}=[k]$.

######  Lemma 4 ([15]).

For any $n,k\geq 1$, one can construct an $(n,k)$-perfect hash family of size
$e^{k}k^{O(\log k)}\log n$ in time $e^{k}k^{O(\log k)}n\log n$.

Now we are ready to state and prove the main result of this section:

######  Theorem 6.1.

There is an $2^{O(k)}poly(n)$-time algorithm that for constant $t$ and a given
instance of $t$-Uniform Set Cover determines the existence of a set cover of
size at most $\lceil\frac{n}{t}\rceil-k$ where $k$ is an integer parameter and
$n$ is the size of the universe.

###### Proof.

In the first stage of our algorithm we start picking sets greedily (i.e. in
each step, we pick the set that covers the largest number of previously
uncovered elements) until there are no sets that cover at least $t+1$
previously uncovered elements. If during this stage we pick $s$ sets and cover
at least $st+tk$ elements then our instance is a Yes-instance. Indeed, we can
cover the remaining elements using $\lceil\frac{n-st-tk}{t}\rceil$ sets. In
total, such a covering has at most $\lceil\frac{n-st-
tk}{t}\rceil+s=\lceil\frac{n}{t}\rceil-k$ subsets. Intuitively, each set
picked during this greedy stage covers at least one additional element.
Therefore, if we pick more than $tk$ subsets then our input instance is a Yes-
instance. This means that after the greedy stage we either immediately
conclude that our input is a Yes-instance or we have used at most $tk$ subsets
and covered at most $tk\cdot t+tk=O(k)$ elements, for a fixed $t$. Let us
denote the subset of all covered elements by $G$. Note that there is no subset
that covers more than $t$ elements from $U\setminus G$.

If there is a covering of size $\lceil\frac{n}{t}\rceil-k$ then there are
$s^{\prime}\leq|G|\leq tk\cdot t+tk$ subsets that cover $G$ and at least
$s^{\prime}t+tk-|G|$ elements of $U\setminus G$. Moreover, if such subsets
exist then our input is a Yes-instance.

Hence, it is enough to find $s^{\prime}$ such subsets. For each
$s^{\prime\prime}\in[|G|]$ we attempt to find subsets
$S_{1},S_{2},\dots,S_{s^{\prime\prime}}$ such that $G\subset S_{1}\cup
S_{2}\cup\dots\cup S_{s^{\prime\prime}}$ and $S_{1}\cup S_{2}\cup\dots\cup
S_{s^{\prime\prime}}$ contains at least $s^{\prime\prime}t+tk-|G|$ elements
from $U\setminus G$. Assume that for some $s^{\prime\prime}$ such sets exist.
Let $H$ be an arbitrary subset of $(S_{1}\cup S_{2}\cup\dots\cup
S_{s^{\prime\prime}})\setminus G$ of size $s^{\prime\prime}t+tk-|G|$. Note
that we do not know the set $H$. However, we employ the color-coding
technique, and construct a $(n,|H|)$-perfect hash family $\mathcal{F}$. We
iterate over all $f\in\mathcal{F}$. Recall that
$|H|=s^{\prime\prime}t+tk-|G|$. Now using dynamic programming we can find $H$
in time $2^{O(k)}$ in a standard way. In order to do that, we consider a new
universe $U^{\prime}$ which contains elements from the set $G$ and elements
corresponding to $|H|$ colors corresponding to values assigned by $f$ to
$U\setminus G$. Moreover, if a subset $P$ was a subset that can be used for
covering in $t$-Uniform Set Cover then we replace it with $(P\cap
G)\cup\\{\text{ all values $f$ assign to elements in }P\cap(U\setminus G)\\}$.
We replace our $t$-Uniform Set Cover instance with an instance of Set Cover
with a universe of size $|G|+|H|\leq|G|+s^{\prime\prime}t+tk-|G|\leq|G|\cdot
t+tk\leq(tk\cdot t+tk)\cdot t+tk=O(k)$. It is easy to see that our original
instance is a Yes-instance if and only if the constructed instance of Set
Cover admits a covering by at most $s^{\prime\prime}$ sets (under the
assumption that $f$ indeed assigns distinct values to elements of $H$). If $f$
does not assign distinct values then a Yes-instance can be become a No-
instance. However, a No-instance cannot become a Yes-instance. Since
$|H|=O(k)$, the overall running time is $2^{O(k)}poly(n)$. ∎

As a corollary of the previous theorem we get the following result. See 1.4

###### Proof.

The result immediately follows from Theorem 6.1 with $t=2$. ∎

## References

  * [1] Agrawal, M., Kayal, N., Saxena, N.: Primes is in p. Annals of mathematics pp. 781–793 (2004)
  * [2] Basavaraju, M., Francis, M.C., Ramanujan, M., Saurabh, S.: Partially polynomial kernels for set cover and test cover. SIAM Journal on Discrete Mathematics 30(3), 1401–1423 (2016)
  * [3] Bast, H., Storandt, S.: Frequency data compression for public transportation network algorithms. In: Proceedings of the International Symposium on Combinatorial Search. vol. 4, pp. 205–206 (2013)
  * [4] Bast, H., Storandt, S.: Frequency-based search for public transit. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. pp. 13–22 (2014)
  * [5] Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546–563 (2009). https://doi.org/10.1137/070683933, https://doi.org/10.1137/070683933
  * [6] Bringmann, K., Kozma, L., Moran, S., Narayanaswamy, N.S.: Hitting set in hypergraphs of low vc-dimension. CoRR abs/1512.00481 (2015), http://arxiv.org/abs/1512.00481
  * [7] Bringmann, K., Nakos, V.: Top-k-convolution and the quest for near-linear output-sensitive subset sum. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. pp. 982–995. ACM (2020). https://doi.org/10.1145/3357713.3384308, https://doi.org/10.1145/3357713.3384308
  * [8] Chan, T.M., Lewenstein, M.: Clustered integer 3sum via additive combinatorics. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. pp. 31–40. ACM (2015). https://doi.org/10.1145/2746539.2746568, https://doi.org/10.1145/2746539.2746568
  * [9] Crittenden, R.B., Vanden Eynden, C.: Any $n$ arithmetic progressions covering the first $2^{n}$ integers cover all integers. Proceedings of the American Mathematical Society 24(3), 475–481 (1970)
  * [10] Crowston, R., Gutin, G., Jones, M., Raman, V., Saurabh, S.: Parameterized complexity of maxsat above average. Theoretical Computer Science 511, 77–84 (2013)
  * [11] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015). https://doi.org/10.1007/978-3-319-21275-3, https://doi.org/10.1007/978-3-319-21275-3
  * [12] Frank, A., Tardos, E.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (jan 1987). https://doi.org/10.1007/BF02579200, https://doi.org/10.1007/BF02579200
  * [13] Grobman, W., Studwell, T.: Data compaction and vector scan e-beam system performance improvement using a novel algorithm for recognition of pattern step and repeats. Journal of Vacuum Science and Technology 16(6), 1803–1808 (1979)
  * [14] Heath, L.S.: Covering a set with arithmetic progressions is NP-complete. Information Processing Letters 34(6), 293–298 (1990). https://doi.org/https://doi.org/10.1016/0020-0190(90)90013-N, https://www.sciencedirect.com/science/article/pii/002001909090013N
  * [15] Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995. pp. 182–191. IEEE Computer Society (1995). https://doi.org/10.1109/SFCS.1995.492475, https://doi.org/10.1109/SFCS.1995.492475


# Multifunctionality in a Connectome-Based Reservoir Computer

Jacob Morra  Western University
London, ON Canada
<EMAIL_ADDRESS>Andrew Flynn  University College Cork
Cork, Ireland
<EMAIL_ADDRESS>Andreas Amann  University College Cork
Cork, Ireland
<EMAIL_ADDRESS>

Mark Daley  Western University
London, ON Canada
<EMAIL_ADDRESS>
###### Abstract

Multifunctionality describes the capacity for a neural network to perform
multiple mutually exclusive tasks without altering its network connections;
and is an emerging area of interest in the reservoir computing machine
learning paradigm. Multifunctionality has been observed in the brains of
humans and other animals: particularly, in the lateral horn of the fruit fly.
In this work, we transplant the connectome of the fruit fly lateral horn to a
reservoir computer (RC), and investigate the extent to which this ‘fruit fly
RC’ (FFRC) exhibits multifunctionality using the ‘seeing double’ problem as a
benchmark test. We furthermore explore the dynamics of how this FFRC achieves
multifunctionality while varying the network’s spectral radius. Compared to
the widely-used Erdös–Renyi Reservoir Computer (ERRC), we report that the FFRC
exhibits a greater capacity for multifunctionality; is multifunctional across
a broader hyperparameter range; and solves the seeing double problem far
beyond the previously observed spectral radius limit, wherein the ERRC’s
dynamics become chaotic.

###### Index Terms:

fruit fly, reservoir computing, dynamical systems, chaos, connectome, brain-
inspired machine learning

##  I Introduction

In the pursuit of developing artificially intelligent systems, there is much
to be gained from integrating further physiological features of biological
neural networks (BNNs) into machine learning (ML) environments. Inspired by
the ability of certain BNNs to exhibit ‘multifunctionality’, in this paper we
investigate whether a corresponding connectome maintains multifunctionality
when transplanted to the reservoir computing ML paradigm.

Multifunctionality describes the ability of a neural network to perform
multiple tasks without changing any network connections [1]. This neurological
phenomenon was first translated from biological to artificial neural networks
(ANNs) using a ‘reservoir computer’ (RC) in [2]. An RC is a dynamical system
which can be realised as an ANN. What distinguishes the RC amongst other ML
approaches is that network weights are trained at the readout layer only in
order to solve a given task. Multifunctional RCs, in particular, have the
capacity to reconstruct a coexistence of chaotic attractors from: a
multistable system [2]; two different systems [3]; and multiple copies of a
chaotic attractor from the same system [4]; all without re-training the
weights or re-tuning hyperparameters.

In the life sciences, multifunctionality is well-documented. For example, in
the land snail, the subesophageal ganglion complex has been shown to act as a
controller for maintaining homeostasis of respiratory, genital, and
cardiorenal functions [5]; in the turtle spinal cord, multifunctionality is
present in the interneurons, which contribute to the forward swimming,
flexion, and scratching reflexes [6] – analogous interneurons are also present
in the mammalian central nervous system [7]. In the fruit fly brain, there is
evidence supporting multifunctionality in multiple regions of interest (ROIs):
in the wing, for example, where neurons of the ventral nerve cord are
multifunctional for both song and flight [8]; and in the lateral horn, where
sleep and odour aversion coexist [9], and where olfactory and visual stimuli
are mediated simultaneously [10].

In this paper, we investigate whether a fruit fly connectome-based RC (FFRC)
exhibits multifunctionality as observed in its biological counterpart neural
network; specifically, by capturing the approximate – see Sec. III-A2 –
network topology of the lateral horn ROI from the hemibrain dataset [11] and
applying its RC analogue (as in [12, 13]) to the ‘seeing double’ problem. The
seeing double benchmark test for exploring the limits of multifunctionality
was first introduced in [3] and further explored in [14]; in this test, the RC
is tasked with having to reconstruct a coexistence of two circular orbits
($\mathcal{C}_{A}$ and $\mathcal{C}_{B}$) which rotate in opposing directions
(see Sec. II-B).

The rest of the paper is outlined as follows: In Sec. II we introduce the
particular RC formulation of interest, outline how it is trained to become
multifunctional, and describe the specifics of the seeing double problem.
Thereafter in Sec. III, we describe each of the RC network topologies used,
detail how they are constructed, and also propose four experiments which aim
to shed some light on the differences between how each achieves
multifunctionality (across varying hyperparameters of interest). Furthermore
in Sec. IV we discuss the results of all experiments. Finally, in Sec. V, we
summarize the major experimental findings, describe the project limitations
and caveats, and highlight future directions for investigation.

##  II Background

###  II-A Reservoir Computing

We use the continuous-time RC formulation devised in [15] which was shown in
[2, 4, 3, 14] to be capable of achieving multifunctionality and is expressed
in the following equation:

$\displaystyle\dot{\boldsymbol{r}}(t)=\gamma\left[-\boldsymbol{r}(t)+\tanh{\left(\,\,\textbf{M}\,\boldsymbol{r}(t)+\sigma\textbf{W}_{in}\,\boldsymbol{u}(t)\,\,\right)}\right].$
(1)

Here $\boldsymbol{r}(t)\in\mathbb{R}^{N}$ is the state of the RC at a given
time $t$ and $N$ is the number of neurons in the network. $\gamma$ is the
decay-rate parameter. $\textbf{M}\in\mathbb{R}^{N\times N}$ is the adjacency
matrix describing the internal layer of the RC. $\sigma$ is the input strength
parameter and $\textbf{W}_{in}\in\mathbb{R}^{N\times D}$ is the input matrix
(constructed as in [15]), when multiplied together this represents the weight
given to the $D$-dimensional input, $\boldsymbol{u}(t)\in\mathbb{R}^{D}$, as
it is projected into the RC. This input is taken from the particular attractor
or time series that one would like to either reconstruct or make future
predictions of. Solutions of Eq. (1) are computed using the 4th order Runge-
Kutta method with time step $\tau=0.01$.

In our numerical experiments we consider two different variations of M. The
first M is constructed with an Erdös-Renyi topology where each of the non-zero
elements are then replaced with a random number between $-1$ and $1$; the
matrix is subsequently scaled to a specific spectral radius, $\rho$. The
second M is constructed from the right lateral horn ROI from the hemibrain
connectome [11]: further details on this construction are outlined in Sec.
III-A2. The spectral radius, $\rho$, for each M is a key parameter involved in
the training: in particular, $\rho$ is associated with the RC’s memory as it
is used to tune the weight the RC places on its own internal dynamics.

To train the RC in Eq. (1), the system is first driven by the input
$\boldsymbol{u}(t)$ from $t=0$ to time $t=t_{listen}$ in order to remove any
dependency which $\boldsymbol{r}(t)$ has on its initial condition
$\boldsymbol{r}(0)=\left(0,0,\ldots,0\right)^{T}=\mathbf{0}^{T}$. The training
data is then generated by driving the RC with $\boldsymbol{u}(t)$ from
$t=t_{listen}$ to $t=t_{train}$.

A suitable readout layer needs to be calculated in order to train the RC and
replace the training input signal, $\boldsymbol{u}(t)$, in Eq. (1) with a
post-processing function, $\hat{\psi}\left(\cdot\right)$. If the training is
successful then we say that,

$\displaystyle\hat{\psi}\left(\boldsymbol{r}(t)\right)=\hat{\boldsymbol{u}}(t)\approx\boldsymbol{u}(t),\,\,\,\text{for}\,\,t>t_{train},$
(2)

where $\hat{\boldsymbol{u}}(t)$ denotes the predicted time-series. This layer
‘closes the loop’ of the nonautonomous system in Eq. (1) and provides a map
from the $N$-dimensional state space of the RC, $\mathbb{S}$, to the
$D$-dimensional ‘prediction state space’, $\mathbb{P}$.

In this work
$\hat{\psi}\left(\boldsymbol{r}(t)\right)=\textbf{W}_{out}\boldsymbol{q}(\boldsymbol{r}(t))$
– where $\textbf{W}_{out}$ is the readout matrix – and we use
$\boldsymbol{q}(\boldsymbol{r}(t))$ to break the symmetry in Eq. (1) using the
‘squaring technique’ described by

$\displaystyle\boldsymbol{q}(\boldsymbol{r}(t))=\left(\begin{array}[]{cc}\boldsymbol{r}(t),&\boldsymbol{r}^{2}(t)\end{array}\right)^{T}.$
(4)

We calculate $\textbf{W}_{out}$ using the ridge regression approach,

$\displaystyle\textbf{W}_{out}=\textbf{Y}\textbf{X}^{T}\left(\textbf{X}\textbf{X}^{T}+\beta\,\textbf{I}\right)^{-1},$
(5)

where

$\displaystyle\textbf{X}=\left[\begin{array}[]{@{}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{}}\left(\begin{array}[]{@{}c@{}}\boldsymbol{r}(t_{listen})\\\
\boldsymbol{r}^{2}(t_{listen})\end{array}\right)\hfil\hskip
2.84526pt&\left(\begin{array}[]{@{}c@{}}\boldsymbol{r}(t_{listen}+\tau)\\\
\boldsymbol{r}^{2}(t_{listen}+\tau)\end{array}\right)\hfil\hskip
2.84526pt&\cdots\hfil\hskip
2.84526pt&\left(\begin{array}[]{@{}c@{}}\boldsymbol{r}(t_{train})\\\
\boldsymbol{r}^{2}(t_{train})\end{array}\right)\end{array}\right]$ (13)

is the RC reservoir’s response to the input data, which is represented as

$\displaystyle\textbf{Y}=\left[\begin{array}[]{cccc}\boldsymbol{u}(t_{listen})&\boldsymbol{u}(t_{listen}+\tau)&\cdots&\boldsymbol{u}(t_{train})\end{array}\right].$
(15)

In Eq. 5$,\beta$ is the regularization parameter which is used to help prevent
overfitting. I is the identity matrix.

We write the ‘predicting RC’ as the following autonomous dynamical system:

$\displaystyle\dot{\hat{\boldsymbol{r}}}(t)=\gamma\Big{[}-\hat{\boldsymbol{r}}(t)+\tanh\Big{(}\textbf{M}\,$
$\displaystyle\hat{\boldsymbol{r}}(t)+\sigma\textbf{W}_{in}\textbf{W}_{out}^{(1)}\boldsymbol{q}(\hat{\boldsymbol{r}}(t))\Big{)}\Big{]},$
(16)

where $\hat{\boldsymbol{r}}$ denotes the state of the predicting RC at time
$t$ and $\hat{\boldsymbol{r}}(0)=\boldsymbol{r}(t_{train})$.

For the case of multifunctionality, Eq. (1) is driven by two different input
signals, $\boldsymbol{u}_{1}$ and $\boldsymbol{u}_{2}$, that describe
trajectories on two attractors $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$.
Following the above steps, this produces two corresponding RC response data
matrices, $\textbf{X}_{1}$ and $\textbf{X}_{2}$, and in accordance with the
input data matrices, $\textbf{Y}_{1}$ and $\textbf{Y}_{2}$. These
$\textbf{X}_{1}$ and $\textbf{X}_{2}$, and $\textbf{Y}_{1}$ and
$\textbf{Y}_{2}$ are ‘blended’ together according to the blending technique
featured in [2]. The resulting blended matrices are used to solve for
$\textbf{W}_{out}$ according to Eq. (5). The predicting RC in this case is
described as in Eq. (16); if multifunctionality is achieved, once Eq. (16) is
initialised with either $\hat{\boldsymbol{r}}_{1}(0)$ or
$\hat{\boldsymbol{r}}_{2}(0)$ then the predicting RC will reconstruct the
dynamics of either $\mathcal{A}_{1}$ or $\mathcal{A}_{2}$.

###  II-B The ‘Seeing Double’ task

The seeing double task was first introduced in [3] as a benchmark task to
compare how different RCs achieve multifunctionality. An illustration of the
basic setup which is used in this numerical experiment is provided in Fig. 1.

For this task we consider training the RC in Eq. (1) to reconstruct a
coexistence of attractors which describe trajectories on two (partially or
completely) overlapping circular orbits – $\mathcal{C}_{A}$ and
$\mathcal{C}_{B}$ – that rotate in opposite directions (see Fig. 1). The input
data to train the RC in Eq. (1) is generated by

$u(t)=\bigg{(}\begin{array}[]{c}x(t)\\\
y(t)\end{array}\bigg{)}=\bigg{(}\begin{array}[]{c}s_{x}\,\cos(t)+x_{cen}\\\
s_{y}\,\sin(t)+y_{cen}\end{array}\bigg{)}.$ (17)

In this paper, to train the RC in Eq. (1) to become multifunctional, $s_{x}$
and $s_{y}$ are assigned as $s_{x}=s_{y}=5$ to create $\mathcal{C}_{A}$ and
thus the training input signal $\boldsymbol{u}_{1}$; moreover, for
$\mathcal{C}_{B}$ we use $s_{x}=-5$ and $s_{y}=5$ to produce the corresponding
$\boldsymbol{u}_{2}$. In this case, the radius ($s$) of both $\mathcal{C}_{A}$
and $\mathcal{C}_{B}$ is equal to $5$.

$\mathcal{C}_{B}$$(-x_{cen},-y_{cen})$$\mathcal{C}_{A}$$(x_{cen},y_{cen})$$s$
Figure 1: Illustration of the fundamentals of the seeing double problem.

Formally, the RC achieves multifunctionality in this instance if – after
training on the input time series from Eq. (17) – it reconstructs a
coexistence of attractors in $\mathbb{S}$ such that the dynamics in
$\mathbb{P}$ resembles trajectories on both $\mathcal{C}_{A}$ and
$\mathcal{C}_{B}$. In practice we determine whether the ‘reconstructed
attractors’ in $\mathbb{P}$ – that is, $\hat{\mathcal{C}}_{A}$ and
$\hat{\mathcal{C}}_{B}$ – follow the correct directional arcs and satisfy a
‘roundness’ condition below $0.25$ – determined empirically in [3, 14] and is
defined as the difference in radii between the largest and smallest circular
trajectories which inscribe a particular circular orbit.

While the seeing double problem may at first seem as a relatively simple
problem – i.e. in comparison to reconstructing chaotic attractors – it is the
overlap between $\mathcal{C}_{A}$ and $\mathcal{C}_{B}$ that makes this task
difficult for the RC to solve. For instance, when the RC approaches a junction
where the circular trajectories intersect, it must use its memory of the
previous time steps in order to continue on its correct trajectory.

In [3, 14], the critical role of $\rho$ is revealed: in particular, it is
found that when $\mathcal{C}_{A}$ and $\mathcal{C}_{B}$ are completely
overlapping – i.e. when $x_{cen}=y_{cen}=0$ – then multifunctionality is
achieved for a small range of relatively large values of $\rho$. On the other
hand, if $\rho$ is too large, then multifunctionality is lost.

To provide a comparison, in this paper we confine our study to the this
extreme scenario where $x_{cen}=y_{cen}=0$.

##  III Methods

###  III-A Model Pipeline

####  III-A1 The Erdös–Renyi Reservoir Computer (ERRC)

As mentioned in Sec. II-A, we use a weighted Erdös–Renyi topology with a
sparsity of $0.05$. Weights are drawn randomly from $[-1,1]$ to construct an
adjacency matrix $\textbf{M}_{ER}$ of size $N=500$. We vary the spectral
radius, $\rho$, of the resulting $\textbf{M}_{ER}$ from 0 to 2.0 for
Experiments 1-2 and 0 to 1.8 for Experiment 3 as outlined in Secs.
III-B1-III-B3. We also explore the ERRC’s dynamics at larger $\rho$ values (up
to $\rho=2.2$) in Experiment 4.

####  III-A2 The Fruit Fly Reservoir Computer (FFRC)

The “Fruit Fly RC” (FFRC) is derived from the hemibrain [11]: Using Neuprint
[16], we access the hemibrain API with a provided key, and run a set of Cypher
queries on the Neo4j graph database to select all neurons in the right lateral
horn ROI which are connected to all others (i.e. in the same ROI). We define
two neurons as being “connected” if they are synaptic partners and have a
sufficiently-large number of shared synaptic sites; here we select a tolerance
of 50 synapses in order to reduce the size and complexity of the model – i.e.
to make the training pipeline more efficient. After querying the hemibrain to
collect neuron connection data, we construct a NetworkX graph which retains
all synaptic partners and their weights (the number of synaptic sites);
finally, from this graph we construct our adjacency matrix $\textbf{M}_{FF}$
of size $N=426$. We interpolate the weight values into $[-1,1]$. Following a
common approach (as in [17] and [18]), we also diagonalize the matrix. It is
important to stress that $\textbf{M}_{FF}$ is unchanging: it has a fixed
structure, which is based off of the hemibrain connectome data, whereas the
ERRC by contrast is randomly initialised.

###  III-B Experiments

In each of the experiments listed below, we set $t_{listen}=6T$ and
$t_{train}=15T$, where $T$ is the period of rotation on each orbit
$\mathcal{C}$. We also assign $\sigma=0.2$ and $\beta=0.01$.

####  III-B1 Experiment 1 – Multifunctionality trials

We conduct 50 sets of 100 trials; in each set, the ERRC and FFRC are both
independently evaluated on the seeing double problem for previously-found
optimal hyperparameter values ($\rho=1.4$, $\gamma=5.0$) – see [3].
$\textbf{W}_{in}$ is randomly initialised on each simulation for both the RC
setups. While the FFRC, as previously mentioned, uses a fixed M structure, the
corresponding $\textbf{M}_{ER}$ for the ERRC is re-initialized for each trial.

In a given set of trials, we count all instances where multifunctionality is
achieved according to the criteria in Sec. II-B and as outlined in [3, 14].

####  III-B2 Experiment 2 – Varying $\rho$ and $\gamma$

As previously observed in [3], depending on the choice of both $\rho$ and
$\gamma$, these parameters can have a profound impact on the
multifunctionality of RCs on the seeing double problem. Here, as in [3], we
aim to determine the regions in the $(\rho,\gamma)$-plane where
multifunctionality is achieved for both the FFRC and ERRC. We conduct one set
of 100 multifunctionality trials (as in Experiment 1) for each $\rho,\gamma$
combination for $\rho,\gamma$ $\in$ $[0,2.0]\times[5,95]$.

####  III-B3 Experiment 3 – Comparing RC activations

As the RC’s predicted time series is a trained linear combination of RC
activation states, it is reasonable to analyze the activity of each neuron in
the cases of multifunctionality and non-multifunctionality, for both RC
models.

Following this intuition, we compute the number of unique local maxima – on
the interval from $t=t_{train}$ to $t=27T$ – for each neuron ($\hat{r}_{(i)}$)
in both RC setups. We then construct a heat map (see Fig. 5) which shows the
count for each neuron versus $\rho$ for a multifunctional and a non-
multifunctional – i.e. in cases where only one orbit is reconstructed or
neither – instance of the FFRC and ERRC models, respectively.

####  III-B4 Experiment 4 – Exploring seeing double dynamics

Finally, we aim to shed some light on the differences between how the FF and
ER RCs solve the seeing double problem, which follows the bifurcation analysis
presented in [14] – here we explore the changes in the dynamics of the FF and
ER RCs in $\mathbb{P}$ for changes in $\rho$. More specifically, we track the
evolution of predictions in the $[\rho,x,y]$-space and illustrate how
$\hat{\mathcal{C}}_{A}$ and $\hat{\mathcal{C}}_{B}$ come into existence in
cases where both the FF and ER RCs achieve multifunctionality. The influence
of ‘untrained attractors’, attractors which exist in $\mathbb{P}$ but were not
present during the training (like in [14, 2]) are also examined here.

##  IV Results and Discussion

Note: we recommend the use of ‘Adobe Reader’ or ‘Chrome PDF Viewer’ to view
the figures in this section.

####  IV-1 Experiment 1

Comparing the instances where multifunctionality (MF) occurs in the FF and ER
RCs on the seeing double problem across 50 sets of 100 trials – see Fig. 2) –
we observe that the FFRC achieves an average multifunctionality count of 6.46
out of 100; conversely, the RC scores 4.66 out of 100 on average. The
distribution of FFRC scores is neither positively nor negatively skewed;
whereas the RC is negatively skewed. Differences observed between the
distributions of multifunctionality instances are significant: here
$p=0.000035<0.05$ for the Wilcoxon rank-sum test.

####  IV-2 Experiment 2

Figure 2: A raincloud plot illustrating FF versus ER RC multifunctionality
(MF) across 50 sets of 100 trials on the seeing double problem. Figure 3: ERRC
counts of multifunctionality in the $[\gamma,\rho]$-plane. Figure 4: FFRC
counts of multifunctionality in the $[\gamma,\rho]$-plane.

In Fig. 3 we provide multifunctionality counts (out of 100 trials,
respectively) for the ERRC on the seeing double problem across the
$[\gamma,\rho]$-plane of $[5,95]\times[0,2.0]$. We report an approximate
window of multifunctionality in the $[\gamma$, $\rho]$ range of
$[5,35]\times[1.25,1.5]$. Maximum multifunctionality occurs at
$[\gamma,\rho]$=$[15,1.5]$ – here we observe a count of 7 out of 100 trials.
As previously observed in [3], multifunctional capacity falls as $\rho$
continues to increase. At $\rho=2.0$, for example, we observe no evidence of
multifunctionality for any of the reported $\gamma$ values.

For the FFRC (see Fig. 4) we find the greatest occurrance of
multifunctionality at $[\gamma,\rho]=[15,1.5]$ and also $[15,2.0]$, where the
reported count is 10 instances out of 100 trials. The hyperparameter region
where multifunctionality occurs is approximately $[\gamma,\rho]$ $\in$
$[5,75]$ $\times$ $[1.5,2.0]$, a much larger than the window of
multifunctionality found for the ERRC. Moreover, the frequency of
multifunctionality across all sets of 100 trials is greater overall.
Importantly, the FFRC is also capable of exhibiting multifunctionality at
large $\rho$ values (the ERRC is not); which is particularly interesting as
this is where we observe – i.e. for $\gamma=15$ – maximum multifunctionality.

####  IV-3 Experiment 3

(a) ERRC (MF)

(b) ERRC (non-MF)

(c) FFRC (MF)

(d) FFRC (non-MF)

Figure 5: Unique local maxima counts for each $i^{th}$ neuron vs. $\rho$ in a
case where multifunctionality (MF) is and is not achieved for the FFRC in (a)
and (b) and the ERRC in (c) and (d).

Looking at the activity profiles of all neurons $\hat{r}_{(i)}$ in the ERRC
and FFRC (Fig. 5), we first compare the population dynamics of RCs exhibiting
multifunctionality (MF) and non-multifunctionality. For the FFRC activations,
we observe that the number of unique local maxima is “high” (above 40) in more
neurons during MF. We speculate – as in [19] – that a higher proportion of
reservoir activation neurons with many unique local maxima would indicate a
greater richness of reservoir activation curves to draw a set of predictions
from. Between the MF and non-MF ERRC heat maps, we observe a slightly larger
population of neurons with “high” (above 60) unique local maxima; however, the
differences are less pronounced. Between the ERRC and FFRC models, we see that
more neurons are involved in the ERRC predictions overall in both MF and non-
MF cases. Moreover, in the ERRC there are neurons with a higher magnitude of
unique local maxima (roughly 70 in the ERRC versus 45 in the FFRC). This
follows intuitively: a small subset of neurons in the fly brain act as
“information highways for multisensory integration” [20]; conversely,
randomly-weighted neurons have arbitrary importance, and thus we would expect
that an effective output prediction would rely on a broad sampling of
activations in order to match to a ground truth signal. Finally, across all
figures in Fig. 5, we note that increasing the spectral radius $\rho$ also
increases the proportion of neurons which have a high number of unique local
maxima.

####  IV-4 Experiment 4

(a) ERRC

(b) FFRC

Figure 6: Dynamics of the ERRC in (a) and FFRC in (b) for increasing $\rho$.
$FP_{i}$: fixed point $i$; $LC_{j}$: limit cycle $j$; $\hat{\mathcal{C}}_{A}$:
reconstructed $\mathcal{C}_{A}$; $\hat{\mathcal{C}}_{B}$: reconstructed
$\mathcal{C}_{B}$.

We now explore the prediction dynamics of the ERRC and FFRC in the respective
$\mathbb{P}$ for increasing $\rho$.

For the ERRC, (see Fig. 6(a)), like in [14], at small $\rho$ values we find
that four anti-symmetric fixed points exist which subsequently bifurcate into
two distinct limit cycles ($LC$) at $\rho\approx 0.55$, whose dynamics are
shown above the bifurcation diagram for $\rho=0.6$. $LC_{1}$ can no longer be
tracked for $\rho>0.62$, while $LC_{2}$ remains stable and exists up to
$\rho=1.65$. Coexisting with $LC_{2}$ here is the reconstruction of
$\mathcal{C}_{B}$, which first appears as a torus at $\rho=0.76$ and begins to
more closely resemble $\mathcal{C}_{B}$ from $\rho=0.78$ to $\rho=1.25$. The
state of the ERRC subsequently tends to $LC_{3}$, which is born at
$\rho=0.91$; this is initially a torus before it becomes a limit cycle – as
highlighted by the plots in $\mathbb{P}$ at $\rho=0.92,1.15$ (above the
bifurcation diagram in Fig. 6(a)). $LC_{3}$ can no longer be tracked for
$\rho>1.69$. At $\rho=1.64$, $\hat{\mathcal{C}}_{B}$ is reborn; however, for
$\rho>1.83$ and beyond, $\hat{\mathcal{C}}_{B}$ becomes chaotic, where it
remains indefinitely (or for as far as it can be tracked with reasonable
accuracy).

The ERRC is shown to exhibit multifunctionality – wherein
$\hat{\mathcal{C}}_{A}$ is found to coexist with $\hat{\mathcal{C}}_{B}$ – for
the intervals of $\rho=[1.17,1.25]$ and $[1.71,1.76]$. An additional limit
cycle, $LC_{4}$, also briefly appears here, for $\rho=[1.69,1.71]$, and its
dynamics for $\rho=1.7$ is shown above the bifurcation diagram.

In Fig. 6(b) we illustrate the prediction dynamics of the FFRC on the seeing
double problem. We find that, as in Fig. 6(a), at small $\rho$ values, four
anti-symmetric fixed points exist. However, as we continue to track the
changes in these fixed points the differences between how the FF and ER RC
solves the seeing double problem emerges. We find that for $FP_{3}$ and
$FP_{4}$ there is a small region of hysteresis with an additional branch of
stable fixed points – $FP_{31}$ and $FP_{41}$, respectively. For $\rho>0.7$,
$FP_{31}$ and $FP_{41}$ can no longer be tracked and the state of the RC tends
to $FP_{1}$ and $FP_{2}$, respectively. At $\rho=0.73$ there is a bifurcation
from these fixed points to a limit cycle, $LC_{1}$ (potentially a
SNIPER/homoclinic bifurcation based on the characteristics of $LC_{1}$). For
$\rho>0.84$, $LC_{1}$ can no longer be tracked and the state of the FFRC tends
to $\hat{\mathcal{C}}_{A}$, which exists up to $\rho=2.08$. By tracking
$\hat{\mathcal{C}}_{A}$ as $\rho$ decreases, we find that it goes through
several bouts of torii bifurcations, initially appearing as a period-3 limit
cycle at $\rho=0.75$, highlighted by the plot above the bifurcation diagram in
Fig. 6(b) for $\rho=0.76$, we also show here for $\rho=0.79$ that there exists
two antisymmetric limit cycles $LC_{2}$ and $LC_{3}$ for $\rho=[0.77,0.80]$.

We see in Fig. 6(b) that the FFRC achieves multifunctionality for
$\rho=[1.29,2.08]$; even though $\mathcal{C}_{B}$ comes into existence at
$\rho=1.27$, it is only properly reconstructed (according to the criteria in
Sec. II-B) at $\rho=1.29$, and coexists with $\mathcal{C}_{A}$ until
$\rho=2.08$. We also note that another limit cycle ($LC_{4}$) exists while the
FFRC is multifunctional. It is suggested that additional limit cycles exist in
$\mathbb{P}$ as $\rho$ continues to increase.

Comparing the findings for the ERRC and FFRC, what is perhaps most interesting
is that we observe clear evidence of multifunctionality for a much broader
range of row values – from $\rho=1.29$ to $2.08$, totalling a multifunctional
$\rho$-interval of $~{}0.79$, which is much larger than that of the ERRC
($\approx 0.13$). Moreover, compared to the ERRC – which becomes chaotic at
large $\rho$ values – the FFRC prediction dynamics persist (without succumbing
to chaos) long past this $\rho$ limit.

##  V Conclusion

###  V-A Summary

In this paper we find that the FFRC outperforms the ERRC on the seeing double
problem in three ways:

  1. 1.

A higher frequency of achieving multifunctionality for $\rho=1.4$, $\gamma=5$
(Experiment 1).

  2. 2.

A broader window of $[\rho,\gamma]$-space where multifunctionality is present,
and a larger magnitude of multifunctionality overall (Experiment 2).

  3. 3.

Prediction dynamics of the FFRC persist as non-chaotic, circular trajectories
well beyond the observed $\rho$ threshold in the ERRC (Experiment 4).

These findings suggest that fruit fly brain structure – relative to an
arbitrary, random topology – possesses a greater capacity for
multifunctionality, and is more robust to MF-related parameter fluctuations.
Interestingly, the FFRC appears to mimic analogous abilities observed in its
biological counterpart [8].

Fig. 5 suggests that the FFRC takes advantage of a smaller population of
neurons with higher importance – i.e. for a given $\rho$ value there are only
a small number of neurons which ‘fire’ with a large number of unique local
maxima. In comparison, we see here that for the ERRC there is a larger
proportion of highly activated neurons for a given $\rho$.

###  V-B Limitations

We acknowledge that our FFRC adjacency matrix, $\textbf{M}_{FF}$, is a
translation of its corresponding connectome ROI; which captures broad lateral
horn connectivity, but does not include all synapses – i.e. due to applying a
threshold (see Sec. III). As a structural translation only, the FFRC also
fails to capture functional aspects (e.g. the action of neurotransmitters).
Detailed structural elements are also absent, such as neuron morphologies (we
use point neurons). One could therefore argue that this structurally-inspired
model is only providing a “taste” of the potential capacity of the fly brain
for multifunctionality.

###  V-C Future Work

We will continue to analyse the nonlinear and chaotic dynamics of the FFRC and
ERRC in order to further explore their limits of multifunctionality. We will
also seek to (as in [3]) determine the impact of additional model factors –
such as the input matrix designs ($\mathbf{W}_{in}$) – on multifunctionality.

We aim to transplant other animal connectome-based networks, such as [21, 22],
to RC setups to test whether these networks can also be exploited in a machine
learning context.

## References

  * [1] K. L. Briggman and W. Kristan Jr, “Multifunctional pattern-generating circuits,” Annu. Rev. Neurosci., vol. 31, pp. 271–294, 2008.
  * [2] A. Flynn, V. A. Tsachouridis, and A. Amann, “Multifunctionality in a reservoir computer,” Chaos, vol. 31, p. 013125, Jan. 2021.
  * [3] A. Flynn et al., “Exploring the limits of multifunctionality across different reservoir computers,” in 2022 International Joint Conference on Neural Networks (IJCNN), pp. 1–8, IEEE, 2022.
  * [4] A. Flynn et al., “Symmetry kills the square in a multifunctional reservoir computer,” Chaos, vol. 31, p. 073122, July 2021.
  * [5] K. S. Rózsa, “Organization of the multifunctional neural network regulating visceral organs in Helix pomatia L (Mollusca, Gastropoda),” Experientia, vol. 43, pp. 965–972, Sept. 1987.
  * [6] A. Berkowitz, “Multifunctional and specialized spinal interneurons for turtle limb movements,” Ann. N. Y. Acad. Sci., vol. 1198, 2010.
  * [7] E. Jankowska, “Spinal interneuronal systems: identification, multifunctional character and reconfigurations in mammals,” J. Physiol., vol. 533, pp. 31–40, May 2001.
  * [8] A. O’Sullivan et al., “Multifunctional wing motor control of song and flight,” Curr. Biol., vol. 28, pp. 2705–2717.e4, Sept. 2018.
  * [9] C. T. Hsu, J. T. Y. Choi, and A. Sehgal, “Manipulations of the olfactory circuit highlight the role of sensory stimulation in regulating sleep amount,” Sleep, vol. 44, May 2021.
  * [10] N. Gupta and M. Stopfer, “Functional analysis of a higher olfactory center, the lateral horn,” J. Neurosci., vol. 32, pp. 8138–8148, June 2012.
  * [11] L. K. Scheffer  et. al, “A connectome and analysis of the adult Drosophila central brain,” Elife, vol. 9, Sept. 2020.
  * [12] J. Morra and M. Daley, “Imposing Connectome-Derived topology on an echo state network,” in 2022 International Joint Conference on Neural Networks (IJCNN), pp. 1–6, July 2022.
  * [13] J. Morra and M. Daley, “Using connectome features to constrain echo state networks,” arXiv preprint arXiv:2206.02094, 2022.
  * [14] A. Flynn, V. A. Tsachouridis, and A. Amann, “Seeing double with a multifunctional reservoir computer,” arXiv preprint arXiv:2305.05799, 2023\.
  * [15] Z. Lu, B. R. Hunt, and E. Ott, “Attractor reconstruction by machine learning,” Chaos, vol. 28, no. 6, p. 061104, 2018.
  * [16] “neuPrintExplorer.” https://neuprint.janelia.org/.  Accessed: 2023-3-18.
  * [17] X. Gao and P. A. Robinson, “Importance of self-connections for brain connectivity and spectral connectomics,” Biol. Cybern., vol. 114, pp. 643–651, Dec. 2020.
  * [18] J. H. Proske, M. Wittmann, and C. G. Galizia, “Olfactory sensor processing in neural networks: lessons from modeling the fruit fly antennal lobe,” Front. Neuroeng., vol. 5, p. 2, Feb. 2012.
  * [19] C. Gallicchio, “Sparsity in reservoir computing neural networks,” in 2020 International Conference on INnovations in Intelligent SysTems and Applications (INISTA), pp. 1–7, IEEE, 2020.
  * [20] K. Mehta, R. F. Goldin, and G. A. Ascoli, “Circuit analysis of the Drosophila brain using connectivity-based neuronal classification reveals organization of key information processing pathways.” Mar. 2022.
  * [21] S. J. Cook et. al, “Whole-animal connectomes of both Caenorhabditis elegans sexes,” Nature, vol. 571, pp. 63–71, July 2019.
  * [22] S. W. Oh et. al, “A mesoscale connectome of the mouse brain,” Nature, vol. 508, pp. 207–214, Apr. 2014.