problem  Input: Question:

# A necessary and sufficient condition for the existence
of a properly coloured $f$-factor in an edge-coloured graph

Roman Čada1
<EMAIL_ADDRESS>Michitaka Furuya2
<EMAIL_ADDRESS>Kenji Kimura3
<EMAIL_ADDRESS>Kenta Ozeki4
<EMAIL_ADDRESS>Christopher Purcell1111Corresponding author.
<EMAIL_ADDRESS>Takamasa Yashima1,5
<EMAIL_ADDRESS>
1European Centre of Excellence NTIS, Department of Mathematics,
University of West Bohemia,
P.O. Box 314, 306 14 Pilsen, Czech Republic
2College of Liberal Arts and Sciences,
Kitasato University,
1-15-1 Kitasato, Minami-ku, Sagamihara, Kanagawa 252-0373, Japan
3Department of Information Technology and Electronics,
Ishinomaki Senshu University,
1 Shinmito, Minamizakai, Ishinomaki, Miyagi 986-8580, Japan
4Faculty of Environment and Information Sciences,
Yokohama National University,
79-2 Tokiwadai, Hodogaya-ku, Yokohama, Kanagawa 240-8501, Japan
5Department of Computer and Information Science,
Seikei Universtiy,
3-3-1 Kichijoji-Kitamachi, Musashino-shi, Tokyo, 180-8633, Japan

###### Abstract

The main result of this paper is an edge-coloured version of Tutte’s
$f$-factor theorem. We give a necessary and sufficient condition for an edge-
coloured graph $G^{c}$ to have a properly coloured $f$-factor. We state and
prove our result in terms of an auxiliary graph $G_{f}^{c}$ which has a
1-factor if and only if $G^{c}$ has a properly coloured $f$-factor; this is
analogous to the “short proof” of the $f$-factor theorem given by Tutte in
1954. An alternative statement, analogous to the original $f$-factor theorem,
is also given. We show that our theorem generalises the $f$-factor theorem;
that is, the former implies the latter. We consider other properties of edge-
coloured graphs, and show that similar results are unlikely for $f$-factors
with rainbow components and distance-$d$-coloured $f$-factors, even when $d=2$
and the number of colours used is asymptotically minimal.

##  1 Introduction

In order to characterise the graphs which have a 1-factor, Tutte proved the
following well-known theorem, in which ${\text{odd}}(H)$ is the number of
components of a graph $H$ with an odd number of vertices.

###### Theorem A

[15] A graph $G$ has a 1-factor if and only if, for each subset $S$ of $V(G)$,
${\text{odd}}(G-S)\leq|S|$.

If we want to characterise the graphs which have an $f$-factor222If $G$ is a
graph and $f$ is a function $f:V(G)\rightarrow\mathbb{N}$, an $f$-factor of
$G$ is a subgraph $F$ that spans $G$ such that $d_{F}(v)=f(v)$ for each $v$ in
$V(G)$. Throughout the paper, we include $0$ in $\mathbb{N}$., we can use
Theorem A in the following way. For any graph $G$, we may construct the graph
$G_{f}$ by replacing each vertex $u$ in $V(G)$ with a complete bipartite graph
on $S_{u}\cup T_{u}$ where $S_{u}=\\{u_{v}\mid uv\in E(G)\\}$ and
$T_{u}=\\{u^{\prime}_{i}\mid 1\leq i\leq d_{G}(u){-}f(u)\\}$, with an edge in
$G_{f}$ between $u_{v}$ and $v_{u}$ whenever $uv$ is an edge in $G$ (unless
$f(v)>d_{G}(v)$ for some vertex $v$ of $G$, in which case, $G_{f}$ does not
exist and $G$ can have no $f$-factor). It is easy to check that $G$ has an
$f$-factor if and only if $G_{f}$ (exists and) has a 1-factor. So we could
simply apply Theorem A to $G_{f}$ to decide whether $G$ has an $f$-factor.
However, Tutte’s $f$-factor theorem, or, more accurately, its proof as given
in [17], says that we need not check the condition for every subset of
$V(G_{f})$. For a pair of disjoint sets $S,T\subseteq V(G)$, let
$X_{S,T}=(\bigcup_{u\in S}S_{u})\cup(\bigcup_{u\in T}T_{u})$. Tutte’s
$f$-factor theorem can be stated as follows.

###### Theorem B

[16] (but see [17]) A graph $G$ has an $f$-factor if and only if, for each
pair of disjoint subsets $S,T$ of $V(G)$,
${\text{odd}}(G_{f}-X_{S,T})\leq|X_{S,T}|$.

The proof of the $f$-factor theorem given in [17] is essentially a proof of
the above theorem followed by a proof that it is equivalent to the original
formulation. In this way, Tutte reduced $f$-factors to 1-factors, which is not
easy to infer directly from the original (and most common) version of the
theorem given below; here, $h(S,T)$ denotes the number of components $C$ of
$G{-}(S\cup T)$ such that $\sum_{v\in V(C)}f(v)+|E_{G}(C,T)|$ is odd
($E_{G}(X,Y)$ is the set of edges with one endpoint in $X$ and the other in
$Y$).

###### Theorem C

[16] A graph $G$ has an $f$-factor if and only if, for each pair of disjoint
subsets $S,T$ of $V(G)$,

$\sum_{u\in S}f(u)-\sum_{u\in T}(f(u)+d_{S}(u))\geq h(S,T).$

Our main result is an analogue of the $f$-factor theorem for properly colored
$f$-factors in edge-coloured graphs. Recently, properly coloured structures in
edge-coloured graphs have received much attention in the literature [5, 6, 8,
10, 13].

$2$$1$$1$$1$$1$

Figure 1: Left: an edge-coloured graph $G^{c}$ and a function $f$ from $V(G)$
to $\mathbb{N}$; the label on $v$ denotes $f(v)$. Right: the graph
$G_{f}^{c}$.

Let $G$ be a graph and let $c:E(G)\rightarrow\\{1,\dots,k\\}$ be a colouring
of its edges. We denote the resulting edge-coloured graph by $G^{c}$. Our aim
in this paper is to characterise the pairs $(G^{c},f)$, where $f$ is a
function $f:V(G)\rightarrow\mathbb{N}$, such that $G^{c}$ has a properly
coloured $f$-factor; that is, one in which adjacent edges have different
colours. We call such a factor a pc-$f$-factor for short. In order to decide
whether $G^{c}$ has a pc-$f$-factor we construct an auxiliary graph in the
following way. For each vertex $u$ in $G^{c}$, we define $E^{c}(u)$ to be the
set of colours assigned by $c$ to the set of edges incident with $u$. The
colour degree of $u$ is defined to be $d^{c}(u)=|E^{c}(u)|$. We obtain the
graph $G^{c}_{f}$ from $G^{c}$ by replacing each vertex $v$ with a complete
bipartite graph on $S_{u}\cup T_{u}$, where $S_{u}=\\{u_{i}\mid i\in
E^{c}(u)\\}$ and $T_{u}=\\{u^{\prime}_{i}\mid 1\leq i\leq d^{c}(u)-f(u)\\}$,
with an edge in $G^{c}_{f}$ between $u_{j}$ and $v_{j}$ whenever $uv$ is an
edge with $c(uv)=j$; see Figure 1 for an example of this construction. It is
easy to check that $G^{c}$ has a pc-$f$-factor if and only if ${G_{f}^{c}}$
has a 1-factor. To decide whether $G^{c}$ has such a factor, we could apply
Theorem A to $G^{c}_{f}$, similarly to the uncoloured version described above.
Our main result is that we need not check the condition for every subset,
analogously to Theorem B.

We now introduce some concepts that will be important throughout the paper. We
define a palette system ${\mathcal{S}}$ of an edge-coloured graph $G^{c}$ to
be a triple $(S,T,W)$ of disjoint subsets of $V(G^{c})$, where $T$ and $W$ are
disjoint unions of subsets of $V(G^{c})$ defined as follows. Let $\hat{f}$ be
the maximum value of $f$. Let ${\mathcal{C}}_{0}$ and ${\mathcal{C}}_{1}$
denote the following families of subsets of ${1,\dots,k}$:

${\mathcal{C}}_{0}=\bigcup_{0\leq
i\leq\hat{f}-2}\binom{\\{1,\dots,k\\}}{i};\hskip
14.22636pt{\mathcal{C}}_{1}=\bigcup_{1\leq
i\leq\hat{f}-1}\binom{\\{1,\dots,k\\}}{i}.$

Let $\\{T^{A}\subseteq V(G^{c})\mid A\in{\mathcal{C}}_{0}\\}$ be a set of
disjoint subsets of $V(G^{c})$ and let $T$ be their union. Let
$\\{W^{A}\subseteq V(G^{c})\mid A\in{\mathcal{C}}_{1}\\}$ be a set of disjoint
subsets of $V(G^{c})$ and let $W$ be their union. For each palette system
${\mathcal{S}}$, we further define a set $X_{\mathcal{S}}$ of vertices of the
derived graph $G^{c}_{f}$. Let $X_{S},X_{T},$ and $X_{W}$ be defined as
follows.

$\displaystyle X_{S}$ $\displaystyle=\bigcup_{u\in S}S_{u}$ $\displaystyle
X_{T}$ $\displaystyle=\bigcup_{A\in{\mathcal{C}}_{0}}\bigcup_{u\in
T^{A}}(T_{u}\cup\\{u_{i}\mid i\in A\\})$ $\displaystyle X_{W}$
$\displaystyle=\bigcup_{A\in{\mathcal{C}}_{1}}\bigcup_{u\in W^{A}}\\{u_{i}\mid
i\in A\\}$

We define $X_{\mathcal{S}}=X_{S}\cup X_{T}\cup X_{W}$. In Figure 2, we show
how $X_{\mathcal{S}}$ intersects $S_{v}\cup T_{v}$ when $v$ is in $S$, $T$ and
$W$ respectively. We can now state our main result.

###### Theorem 1

Let $G^{c}$ be an edge-coloured graph and let $f$ be a function from $V(G)$ to
$\mathbb{N}$. Then there is a properly coloured $f$-factor in $G^{c}$ if and
only if, for every palette system ${\mathcal{S}}$, we have
${\text{odd}}(G^{c}_{f}-X_{\mathcal{S}})\leq|X_{\mathcal{S}}|$.

We remark that the necessity of the condition of Theorem 1 follows immediately
from the 1-factor theorem: if $G^{c}$ has a pc-$f$-factor, then $G^{c}_{f}$
has a 1-factor by construction and so ${\text{odd}}(G^{c}_{f}{-}X)\leq|X|$ for
all $X\subseteq V(G^{c}_{f})$ by Theorem A. We prove the sufficiency of the
condition in Section 2. We continue this section by describing some additional
computational results, which we prove in Section 3; we complete the section
with some important definitions.

$v\in S$$T_{v}$$S_{v}$$+$$\dots$$\dots$

$v\in
T^{\\{{\color[rgb]{0.90234375,0.625,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.625,0}1},{\color[rgb]{0,0.62109375,0.44921875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.62109375,0.44921875}2},{\color[rgb]{0.3359375,0.70703125,0.9140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.3359375,0.70703125,0.9140625}3}\\}}$$+$$\dots$$\dots$

$v\in
W^{\\{{\color[rgb]{0.90234375,0.625,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.90234375,0.625,0}1},{\color[rgb]{0,0.62109375,0.44921875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.62109375,0.44921875}2},{\color[rgb]{0.3359375,0.70703125,0.9140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.3359375,0.70703125,0.9140625}3}\\}}$$+$$\dots$$\dots$

Figure 2: In $G_{f}^{c}$, $X_{\mathcal{S}}\cap(S_{v}\cup T_{v})$ depends on
whether $v$ is in $S$, $T$ or $W$. Here, $X_{\mathcal{S}}$ is depicted in
grey.

Given an edge-coloured graph $G^{c}$ and a function $f$ from $V(G^{c})$ to
$\mathbb{N}$, we can construct $G_{f}^{c}$ efficiently; that is, the number of
computational steps required is bounded by a polynomial in the number of bits
required to represent $G^{c}$ and $f$ (approximately
$|E(G^{c})|{+}|V(G^{c})|\log\hat{f}$). Since a 1-factor in a graph can also be
computed efficiently (using any algorithm for maximum matching; e.g., [3]), we
may deduce that finding a pc-$f$-factor in an edge-coloured graph, if one
exists, can be done in polynomial time. It is natural to ask whether
$f$-factors with other properties can be reduced to 1-factors efficiently. We
say that an edge-coloured graph is rainbow if every edge has a unique colour.
Rainbow coloured substructures in edge-coloured graphs are widely studied; we
direct the reader to the survey by Kano and Xuelinang [11]. A rainbow
component $f$-factor (or rc-$f$-factor) in an edge-coloured graph $G^{c}$ is
an $f$-factor for which each component is rainbow. We show that deciding
whether an edge-coloured graph has an rc-$f$-factor is $\mathsf{NP}$-complete,
and therefore no efficient reduction from rc-$f$-factors to 1-factors exists
unless ${\mathsf{P}}={\mathsf{NP}}$.

Being properly coloured is a local condition while being rainbow coloured is
global. It is natural to ask what role is played by locality in the difference
between pc-$f$-factors and rc-$f$-factors. We introduce an intermediate case
to answer this question. An edge-coloured graph is distance-$d$-coloured if
the distance between every monochromatic pair of its edges is at least $d$;
distance-$1$-colouring coincides with proper edge colouring. A
distance-$d$-colouring of a graph $G$ is also a proper vertex colouring of the
$d$th power of the line graph of $G$. Proper vertex and edge colourings are,
of course, widely studied; distance-$d$-colourings have been the subject of
several papers [4, 9, 14]. We show that deciding the existence of a
distance-$d$-coloured $f$-factor in an edge-coloured graph is
$\mathsf{NP}$-complete even for $d=2$. We strengthen this result by showing
that the problem remains hard even when the number of colours in the graph is
asymptotically minimal.

###  1.1 Notation and Terminology

In this paper we consider only finite simple graphs. We follow the definitions
in [2] unless stated otherwise and refer the reader to [1] for a full
treatment of factor theory. Here, we recall some important concepts. To delete
a set $X$ of vertices from a graph $G$ is to remove them from $V(G)$ and
remove all edges incident with at least one vertex in $X$ from $E(G)$. The
resulting graph is denoted by $G{-}X$. If $X$ is a singleton $\\{x\\}$, we may
omit the brackets and write $G-x$; we adopt this convention also for the union
and difference of sets and write, say, $(X\setminus x)\cup y$. If $X$ is a
subset of $V(G)$, the subgraph of $G$ induced by $X$ is the graph obtained by
deleting $V(G)\setminus X$ from $G$.

##  2 The Main Result

We start this section by completing the proof of Theorem 1; that is, we prove
that the condition in the theorem is sufficient for an edge-coloured graph to
have a pc-$f$-factor. We then show that our result implies Tutte’s $f$-factor
theorem (Theorem B). Finally, we discuss an alternative statement of the
result, analogous to the original statement of the $f$-factor theorem (Theorem
C).

###  2.1 Sufficiency

In order to show that the condition in Theorem 1 is sufficient, completing its
proof, we suppose that there exists an edge-coloured graph $G^{c}$ which has
no pc-$f$-factor for some function $f$ from $V(G)$ to $\mathbb{N}$. We will
show that there exists a palette system ${\mathcal{S}}=(S,T,W)$ such that
${\text{odd}}(G^{c}_{f}{-}X_{\mathcal{S}})>|X_{\mathcal{S}}|$, where
$X_{\mathcal{S}}=X_{S}\cup X_{T}\cup X_{W}$ as defined in Section 1. We know
that $G_{f}^{c}$ has no 1-factor by construction; by Theorem A, there must
exist a set of vertices $X$ in $G_{f}^{c}$ such that
${\text{odd}}(G^{c}_{f}{-}X)>|X|$. We say that a set with this property is
_violating_. We want to show that there is a palette system ${\mathcal{S}}$
such that $X_{\mathcal{S}}=X_{S}\cup X_{T}\cup X_{W}$ is violating. In the
following claims, we show that there is a violating set $X$ with subsets
corresponding to $X_{S}$, $X_{T}$ and $X_{W}$. The first claim deals with the
subset corresponding to $X_{T}$.

###### Claim 2.1

Let $v\in V(G^{c})$. There exists a violating set $X$ of ${G_{f}^{c}}$ such
that if $X\cap T_{v}\not=\emptyset$, then:

  1. (1)

$T_{v}\subseteq X$;

  2. (2)

$|X\cap S_{v}|\leq f(v){-}2$.

###### Proof.

Let $X$ be a violating set of ${G_{f}^{c}}$ with minimum cardinality. We
suppose that $X\cap T_{v}$ is not empty, and begin by proving (1). If
$S_{v}\subseteq X$, then $\mbox{odd}(G_{f}^{c}-(X\setminus
T_{v}))=\mbox{odd}(G_{f}^{c}-X)+|X\cap T_{v}|\geq|X|+1\geq|X\setminus
T_{v}|+1$, and so $X\setminus T_{v}$ is violating, contradicting the
minimality of $X$. We therefore assume that $S_{v}\setminus X$ is not empty.
If $f(v)=d^{c}(v)$, then $T_{v}=\emptyset$, contradicting the definition of
$X$; thus, $f(v)<d^{c}(v)$. Suppose that there exists a vertex $x\in
T_{v}\setminus X$. Comparing the components of $G_{f}^{c}{-}X$ and
$G_{f}^{c}{-}(X\setminus T_{v})$, we see that they only differ at the
component containing $x$. In particular, we observe that
${\text{odd}}(G_{f}^{c}{-}X)-{\text{odd}}(G_{f}^{c}{-}(X\setminus T_{v}))\leq
1$. But then we have:

$\displaystyle{\text{odd}}(G_{f}^{c}{-}(X\setminus T_{v}))$
$\displaystyle\geq{\text{odd}}({G_{f}^{c}}{-}X)-1$ $\displaystyle\geq|X|$
$\displaystyle=|X\cap T_{v}|+|X\setminus T_{v}|$ $\displaystyle\geq|X\setminus
T_{v}|+1,$

and therefore $X\setminus T_{v}$ is violating, contradicting the minimality of
$X$. We conclude that (1) holds.

Now suppose that $X\cap T_{v}\not=\emptyset$ and $|X\cap S_{v}|\geq f(v){-}1$;
we will show that (2) holds. By (1), $T_{v}\subseteq X$. Note that $S_{v}$
contributes at most $|S_{v}\setminus X|$ odd components to ${G_{f}^{c}}{-}X$.
We observe that ${\text{odd}}({G_{f}^{c}}{-}X)$ and
${\text{odd}}({G_{f}^{c}}{-}(X\setminus T_{v}))$ differ by at most
$|S_{v}\setminus X|$; this maximum is attained when each vertex of
$S_{v}\setminus X$ is in a separate odd component and $|T_{v}|+|S_{v}\setminus
X|$ is even. If $|X\cap S_{v}|=f(v){-}1$, then $|T_{v}|+|S_{v}\setminus
X|=(d^{c}(v){-}f(v))+(d^{c}(v){-}f(v){+}1)$ is odd, in which case
${\text{odd}}({G_{f}^{c}}{-}X)-{\text{odd}}({G_{f}^{c}}{-}(X\setminus
T_{v}))\leq|S_{v}\setminus X|{-}1$. Let $\eta=1$ if $|X\cap S_{v}|=f(v){-}1$
and $\eta=0$ otherwise; in other words, we have $|X\cap S_{v}|\geq
f(v){-}\eta$. We also have
${\text{odd}}({G_{f}^{c}}{-}X)-{\text{odd}}({G_{f}^{c}}{-}(X\setminus
T_{v})\leq|S_{v}\setminus X|{-}\eta$. But then we have:

$\displaystyle{\text{odd}}({G_{f}^{c}}{-}(X\setminus T_{v}))$
$\displaystyle\geq{\text{odd}}({G_{f}^{c}}{-}X)-|S_{v}\setminus X|+\eta$
$\displaystyle\geq|X|+1-|S_{v}\setminus X|+\eta$ $\displaystyle=|X\setminus
T_{v}|+|X\cap T_{v}|+1-|S_{v}\setminus X|+\eta$ $\displaystyle=|X\setminus
T_{v}|+(d^{c}(v)-f(v))+1-(d^{c}(v)-|X\cap S_{v}|)+\eta$
$\displaystyle=|X\setminus T_{v}|-f(v)+1+|X\cap S_{v}|+\eta$
$\displaystyle\geq|X\setminus T_{v}|+1,$

which contradicts the minimality of $X$ as before; this completes the proof of
(2) and the claim. ∎

∎

The next claim shows that a violating set $X$ satisifying the above claim also
has disjoint subsets corresponding to $X_{S}$ and $X_{W}$.

###### Claim 2.2

Let $v\in V(G)$. There exists a violating set $X$ of ${G_{f}^{c}}$ which
satisfies Claim 2.1, such that if $X\cap T_{v}=\emptyset$ and $X\cap
S_{v}\not=\emptyset$, then one of the following holds:

  1. (1)

$S_{v}\subseteq X$;

  2. (2)

$1\leq|X\cap S_{v}|\leq f(v)-1$.

###### Proof.

Let $X$ be a violating set satisfying Claim 2.1 and suppose $X$ is of maximum
cardinality among such sets. Further suppose that $X\cap T_{v}$ is empty but
$X\cap S_{v}$ is not. We assume that neither (1) nor (2) hold, and derive a
contradiction. Since $|S_{v}|=d^{c}(v)$, if (1) does not hold then
$1\leq|X\cap S_{v}|\leq d^{c}(v){-}1$. If $d^{c}(v)=f(v)$, (2) follows
immediately, giving a contradiction. We may therefore assume that
$d^{c}(v)>f(v)$, and thus $T_{v}$ is not empty. Since (1) does not hold, there
exists a vertex $u$ in $S_{v}\setminus X$; note that every vertex in $T_{v}$
is a neighbour of $u$. Since (2) does not hold, $|X\cap S_{v}|\geq f(v)$. We
now consider $X^{\prime}=X\cup S_{v}$. Observe that each vertex of $T_{v}$ is
isolated, and therefore an odd component, in ${G_{f}^{c}}{-}X^{\prime}$. On
the other hand, the vertices in $T_{v}$ are in the same component as $u$ in
${G_{f}^{c}}{-}X$. We conclude that ${\text{odd}}({G_{f}^{c}}{-}X^{\prime})$
and ${\text{odd}}({G_{f}^{c}}{-}X)$ differ by at least $|T_{v}|{-}1$; this
minimum is attained only if $|T_{v}|+|S_{v}\setminus X|$ is odd. If $|X\cap
S_{v}|=f(v)$, then $|T_{v}|+|S_{v}\setminus
X|=(d^{c}(v)-f(v))+(d^{c}(v)-f(v))$ is even, in which case
${\text{odd}}({G_{f}^{c}}{-}X^{\prime})-{\text{odd}}({G_{f}^{c}}{-}X)\geq|T_{v}|$.
Let $\eta=0$ if $|X\cap S_{v}|=f(v)$ and $\eta=1$ otherwise; in other words,
we have that $|X\cap S_{v}|\geq f(v){+}\eta$. We also have that
${\text{odd}}({G_{f}^{c}}{-}X^{\prime})-{\text{odd}}({G_{f}^{c}}{-}X)\geq|T_{v}|{-}\eta$.
But then we have:

$\displaystyle{\text{odd}}({G_{f}^{c}}{-}X^{\prime})$
$\displaystyle\geq{\text{odd}}({G_{f}^{c}}{-}X)+|T_{v}|-\eta$
$\displaystyle\geq|X|+1+|T_{v}|-\eta$ $\displaystyle=|X|+1+|S_{v}|-f(v)-\eta$
$\displaystyle=|X^{\prime}|+|X\cap S_{v}|+1-f(v)-\eta$
$\displaystyle\geq|X^{\prime}|+1,$

which contradicts the maximality of $X$, completing the proof. ∎∎

We can now complete the proof of Theorem 1. Let $X$ be a violating set that
satisfies Claims 2.1 and 2.2. It is clear that $X$ is the disjoint union of
three sets corresponding respectively to Claim 2.1 and the first and second
parts of Claim 2.2; respectively and suggestively, we call these sets $T,S$
and $W$. We define these sets formally as follows:

$\displaystyle S$ $\displaystyle=\\{u\in V(G^{c})\mid S_{u}\subseteq X\\}$
$\displaystyle T^{A}$ $\displaystyle=\\{u\in V(G^{c})\mid T_{u}\subseteq
X,S_{u}\cap X=\\{u_{i}\mid i\in A\\}\\}$
$\displaystyle(A\in{\mathcal{C}}_{0})$ $\displaystyle W^{A}$
$\displaystyle=\\{u\in V(G^{c})\mid T_{u}\cap X=\emptyset,S_{u}\cap
X=\\{u_{i}\mid i\in A\\}\\}$ $\displaystyle(A\in{\mathcal{C}}_{1})$
$\displaystyle T$ $\displaystyle=\bigcup_{A\in{\mathcal{C}}_{0}}T^{A}$
$\displaystyle W$ $\displaystyle=\bigcup_{A\in{\mathcal{C}}_{1}}W^{A}.$

Now, with $X_{S},X_{T}$ and $X_{W}$ defined as in Section 1, and with
$X_{\mathcal{S}}=X_{S}\cup X_{T}\cup X_{W}$, it is easy to verify that
$X=X_{\mathcal{S}}$ as required.

###  2.2 Relationship to Tutte’s $f$-Factor Theorem

We now show that our main result is stronger than the $f$-factor theorem, in
the sense that the latter may be deduced from the former. For a graph $G$ and
a function $f$ from $V(G)$ to $\mathbb{N}$, let (C1) be the statement that,
for all disjoint subsets $S,T$ of $V(G)$,
${\text{odd}}(G_{f}{-}X_{S,T})\leq|X_{S,T}|$; i.e., (C1) is the condition in
Theorem B. For $G$ and $f$ as before and for a colouring $c$ of the edges of
$G$, let (C2) be the statement that, for all palette systems ${\mathcal{S}}$
of $G$, ${\text{odd}}({G_{f}^{c}}{-}X_{\mathcal{S}})\leq|X_{\mathcal{S}}|$;
i.e., (C2) is the condition in Theorem 1. Thus, Theorem B is the statement
that $G$ has an $f$-factor if and only if $G_{f}$ satisfies (C1); Theorem 1 is
the statement that $G^{c}$ has a pc-$f$-factor if and only if $G_{f}^{c}$
satisfies (C2). The following lemma shows that the restriction of (C2) to
proper edge-colourings is equivalent to (C1).

###### Lemma 2

Let $G$ be a graph, let $c$ be a proper edge-colouring of $G$ and let $f$ be a
function from $V(G)$ to $\mathbb{N}$. Then $G_{f}$ satisfies (C1) if and only
if $G_{f}^{c}$ satisfies (C2).

###### Proof.

Since $c$ is a proper edge-colouring, $G_{f}$ is isomorphic to $G_{f}^{c}$.
Suppose that $G_{f}^{c}$ satisfies (C2). Let $S$ and $T$ be disjoint subsets
of $V(G)$. Let ${\mathcal{S}}$ be the palette system obtained from $S$ and $T$
by leaving $S$ unchanged, setting $T^{\emptyset}=T$, and leaving $T^{A}$ and
$W^{A}$ empty for all non-empty $A$. In this case, it follows from the
definitions of $X_{S,T}$ and $X_{\mathcal{S}}$ that $X_{S,T}=X_{\mathcal{S}}$.
Since $G_{f}^{c}$ satisfies (C2),
${\text{odd}}(G_{f}^{c}{-}X_{\mathcal{S}})\leq|X_{\mathcal{S}}|$, and it
immediately follows that ${\text{odd}}(G_{f}{-}X_{S,T})\leq|X_{S,T}|$; i.e.,
$G_{f}$ satisfies (C1).

Now suppose that $G_{f}$ satisfies (C1). Let ${\mathcal{S}}=(S,T,W)$ be a
palette system in $G^{c}$. Let $A$ be an element of ${\mathcal{C}}_{1}$, and
consider modifying ${\mathcal{S}}$ by removing a vertex $w$ from $W^{A}$. By
the definition of $X_{W}$, the effect of this operation is to remove $|A|$
vertices from $X_{W}$ and thereby reduce $|X_{\mathcal{S}}|$ by $|A|$, which
is at least 1 since $A$ is non-empty. On the other hand, if the component of
${G_{f}^{c}}{-}X_{\mathcal{S}}$ containing $T_{w}$ is odd and $|A|$ is odd,
then the effect of removing $w$ from $W^{A}$ is to reduce
${\text{odd}}(G_{f}^{c}{-}X_{\mathcal{S}})$ by 1; otherwise,
${\text{odd}}({G_{f}^{c}}{-}X_{\mathcal{S}})$ stays the same or even
increases. The effect of modifying ${\mathcal{S}}$ by moving a vertex $v$ from
$T^{A}$ to $T^{\emptyset}$ is identical. We deduce that if
${\mathcal{S}}^{\prime}$ is obtained from ${\mathcal{S}}$ by repeatedly
performing these operations, then
${\text{odd}}(G_{f}^{c}{-}X_{{\mathcal{S}}^{\prime}})\leq|X_{{\mathcal{S}}^{\prime}}|$
implies ${\text{odd}}(G_{f}^{c}{-}X_{\mathcal{S}})\leq|X_{\mathcal{S}}|$.

Let ${\mathcal{S}}^{*}$ be the palette system obtained from ${\mathcal{S}}$ by
moving all vertices in $T^{A}$ to $T^{\emptyset}$ and removing all vertices
from $W^{A}$, for all non-empty $A$. Observe that
$X_{S,T}=X_{{\mathcal{S}}^{*}}$. Since $G_{f}$ satisfies (C1),
${\text{odd}}(G_{f}{-}X_{S,T})\leq|X_{S,T}|$, from which it immediately
follows that
${\text{odd}}(G_{f}^{c}{-}X_{{\mathcal{S}}^{*}})\leq|X_{{\mathcal{S}}^{*}}|$.
By the argument given in the previous paragraph, we conclude that
${\text{odd}}(G_{f}^{c}{-}X_{\mathcal{S}})\leq|X_{\mathcal{S}}|$ as required.
∎

∎

###### Theorem 3

Theorem 1 implies Tutte’s $f$-factor theorem.

###### Proof.

Let $G$ be a graph, let $f$ be a function from $V(G)$ to $\mathbb{N}$ and let
$c$ be a proper edge-colouring of $G$. Suppose $G_{f}$ satisfies (C1) but $G$
has no $f$-factor. Since $G$ has no $f$-factor, $G^{c}$ has no pc-$f$-factor.
By Theorem 1, $G_{f}^{c}$ does not satisfy (C2). But then $G_{f}$ does not
satisfy (C1) by Lemma 2, which is a contradiction.

Now suppose that $G_{f}$ does not satisfy (C1) but has an $f$-factor. By Lemma
2, $G_{f}^{c}$ does not satisfy (C2) and therefore by Theorem 1, $G^{c}$ has
no pc-$f$-factor. But since $c$ is a proper edge-colouring, every $f$-factor
of $G$ is a pc-$f$-factor of $G^{c}$, so $G$ has no $f$-factor, which is a
contradiction. ∎

∎

###  2.3 Alternative Statement

We now present a different version of Theorem 1; the difference between the
original statement and the one that follows is analogous to the difference
between Tutte’s $f$-factor theorem as presented in Theorem B and as in Theorem
C.

In order to restate our main result, we define two operations on vertices. Let
$G$ be a graph and $c$ a colouring of its edges. When we $c$-split a vertex
$v$ of $G$, we replace $v$ with $d^{c}(v)$ vertices denoted by $v_{i}$ for
each colour $i$ in $E^{c}(v)$, and for each $w$ in $N_{G}(v)$, we replace the
edge $vw$ by $v_{c(vw)}w$. When we twin a vertex $x$ of $G$, we replace $x$
with two vertices $x_{0}$ and $x_{1}$, and for each $y$ in $N_{G}(x)$, we
replace the edge $xy$ with two edges $x_{0}y,x_{1}y$; we also add an edge
between $x_{0}$ and $x_{1}$. Let ${\mathcal{S}}=(S,T,W)$ be a palette system
and let $G_{\mathcal{S}}$ denote the graph obtained from $G$ by performing the
following operations for every vertex $y$ in $S\cup T\cup W$: if $y$ is in
$S$, we delete $y$; if $y$ is in $T^{A}$ for some $A$ in ${\mathcal{C}}_{0}$,
we $c$-split $y$ and then delete $y_{i}$ whenever $i\in A$; if $y$ is in
$W^{A}$ for some $A$ in ${\mathcal{C}}_{1}$, we delete the edge $yz$ whenever
$c(yz)\in A$ and then twin $y$ if $f(y)+|A|$ is even. We denote by
$h({\mathcal{S}})$ the number of odd components of $G_{\mathcal{S}}$.

###### Theorem 4

Let $G^{c}$ be an edge-coloured graph and let $f$ be a function from $V(G)$ to
$\mathbb{N}$. Then there is a properly coloured $f$-factor in $G^{c}$ if and
only if, for every palette system ${\mathcal{S}}$, we have

$\sum_{u\in S}f(u)+\sum_{A\in{\mathcal{C}}_{0}}\sum_{u\in
T^{A}}(d^{c}(u)-f(u)+|A|)+\sum_{A\in{\mathcal{C}}_{1}}|W^{A}||A|\geq
h({\mathcal{S}}).$

###### Proof.

We show that the inequality in the statement of the theorem is a restatement
of that in Theorem 1. Add $\sum_{u\in S}d^{c}(u)$ to both sides of the
inequality in the statement of the theorem and rearrange it to obtain:

$h({\mathcal{S}})+\sum_{u\in S}(d^{c}(u)-f(u))\leq\sum_{u\in
S}d^{c}(u)+\sum_{A\in{\mathcal{C}}_{0}}\sum_{u\in
T^{A}}(d^{c}(u)-f(u)+|A|)+\sum_{A\in{\mathcal{C}}_{1}}\sum_{u\in W^{A}}|A|.$

It follows from the definition of $X_{\mathcal{S}}$ that the right-hand side
of the (rearranged) inequality is equal to $|X_{\mathcal{S}}|$. By Theorem 1,
it is enough to show that the left-hand side is equal to
${\text{odd}}({G_{f}^{c}}{-}X_{\mathcal{S}})$.

Observe that each vertex $v$ in $S$ contributes $d^{c}(v){-}f(v)$ isolated
vertices (and therefore odd components) to ${G_{f}^{c}}{-}X_{\mathcal{S}}$. We
denote those isolated vertices by $I_{S}$; that is, $I_{S}=\bigcup_{u\in
S}T_{u}$. Consider a vertex $w$ which is in $W^{A}$ for some $A$. Suppose we
identify $(S_{w}\setminus\\{w_{i}\mid i\in A\\})\cup T_{w}$ to a single vertex
$w^{*}$ and then, if $f(w){+}|A|$ is even, we twin $w^{*}$. Since
$|(S_{w}\setminus\\{w_{i}\mid i\in A\\})\cup T_{w}|$ is even if and only if
$f(w){+}|A|$ is even, this operation preserves the number of odd components in
the graph. If we perform this operation for every vertex in $W,$ we obtain
from ${G_{f}^{c}}{-}X_{\mathcal{S}}{-}I_{S}$ a graph isomorphic to
$G_{\mathcal{S}}$. Therefore,
${\text{odd}}({G_{f}^{c}}{-}X_{\mathcal{S}}{-}I_{S})={\text{odd}}(G_{\mathcal{S}})=h({\mathcal{S}})$,
which completes the proof. ∎

∎

##  3 Computational Results

We now turn to global properties of coloured factors. The main result of this
section is that, given an edge-coloured graph $G^{c}$ and a function
$f:V(G)\rightarrow\mathbb{N}$, deciding whether $G^{c}$ has a rainbow
component $f$-factor (rc-$f$-factor) is an ${\mathsf{NP}}$-complete problem.
This implies that it is not possible to reduce rc-$f$-factors to 1-factors
unless ${\mathsf{P}}{=}{\mathsf{NP}}$. We omit a full discussion of
computational complexity theory and refer the reader to [7]. Formally, the
computational problem we are interested in is the following.

To prove our main result we introduce a problem that is known to be
${\mathsf{NP}}$-hard. We define a $1$-in-$3$-colouring of a 3-uniform
hypergraph $H$ to be a function $\phi:V(H)\rightarrow\\{-1,1\\}$ such that in
each edge of $H$ there is exactly one vertex $v$ with $\phi(v)=1$.

It is known that h-1-in-3-col is ${\mathsf{NP}}$-hard even for $k$-regular
hypergraphs, where $k\geq 3$ [12]. We will reduce this version of h-1-in-3-col
to rc-fac; given a $k$-regular, 3-uniform hypergraph $H$, we construct a graph
$G_{H}$, a colouring $c$ and a function $f$ such that $G_{H}^{c}$ has an
rc-$f$-factor if and only if $H$ has a $1$-in-$3$-colouring. In fact, the
function $f$ will be the constant function with $f(v)=k{-}1$ for every vertex
$v$ in $V(G)$; thus, we can prove the stronger result that the following
problem is ${\mathsf{NP}}$-hard, for any $r\geq 2$.

We remark that the constant $r$ is a fixed part of the definition of the
problem, not a part of the input. The hardness of this problem implies
hardness of the version of the problem where the constant is in the input,
which in turn implies hardness of rc-fac.

###### Theorem 5

The rainbow component factor problem is ${\mathsf{NP}}$-complete. Moreover,
the rainbow component $r$-factor problem is ${\mathsf{NP}}$-complete, for any
integer $r\geq 2$.

###### Proof.

It is easy to see that the problem is in ${\mathsf{NP}}$; a nondeterministic
Turing machine can guess a set of edges and it is easy to verify in polynomial
time whether a set of edges induces 1) an $r$-factor and 2) a graph each
component of which is rainbow (by traversal of the components).

Let $r$ be an integer greater than or equal to 2, and let $H$ be an
$(r{+}1)$-regular, 3-uniform hypergraph. We will construct an edge-coloured
graph ${G_{H}^{c}}$ such that ${G_{H}^{c}}$ has an rc-$r$-factor if and only
if $H$ has a $1$-in-$3$-colouring. As discussed above, this is enough to prove
the theorem.

We now describe the construction of ${G_{H}^{c}}$. For each vertex $x$ in $H$,
the graph $G_{H}$ contains a subgraph isomorphic to $K_{r+1}$ and $r{+}1$
subgraphs isomorphic to $K_{r}$ (where $K_{n}$ denotes the complete graph on
$n$ vertices). We call the former the central clique of $x$, and we denote the
latter by $Q^{x}_{i}$ for $1\leq i\leq r{+}1$. We denote the vertices of the
central clique of $x$ by $x_{1},\dots,x_{r+1}$, and for each $i$ we add an
edge from $x_{i}$ to each vertex of $Q^{x}_{i}$.

For each edge $e=\\{x,y,z\\}$ in $H$ we add a vertex to $G_{H}$ denoted by
$v_{e}$. We arbitrarily order the edges of $H$ in which each vertex appears;
we may thus refer to $e$ as (say) the $i$th edge of $x$, the $j$th edge of
$y$, and the $k$th edge of $z$. In that case, we add an edge from $v_{e}$ to
each vertex of $Q^{x}_{i}$, $Q^{y}_{j}$, and $Q^{z}_{k}$.

We now describe the colouring $c$ of the edges of $G_{H}$. To simplify our
notation, we introduce the constants $\rho_{0}=\binom{r}{2}$ and
$\rho_{1}=\binom{r+1}{2}$. All colours assigned by $c$ will be in
$\\{1,\dots,\rho_{1}\\}$. For each vertex $x$ in $H$, $c$ assigns the edges of
the central clique of $x$ distinct colours (there are $\rho_{1}$ edges in the
clique). For $1\leq i\leq r{+}1$, $c$ assigns the edges in $Q_{i}^{x}$
distinct colours from $\\{1,\dots,\rho_{0}\\}$ (there are $\rho_{0}$ such
edges). Each of the $r$ edges from $x_{i}$ to $Q_{i}^{x}$ is assigned a
distinct colour from $\\{\rho_{0}{+}1,\dots,\rho_{1}\\}$ by $c$ (note that
$\rho_{1}-\rho_{0}=r$). Finally, when the $j$th edge of $x$ in $H$ is $e$, we
set $c(v_{e}u)=c(ux_{j})$ for each vertex $u$ in $Q_{j}^{x}$; in other words,
$c$ assigns the edge $v_{e}u$ the same colour that it assigns the edge
$ux_{j}$. It is easy to see that this construction can be performed in
polynomial time.

$x_{1}$$x_{2}$$x_{3}$$y_{1}$$y_{2}$$y_{3}$$w_{2}$$w_{1}$$w_{3}$$z_{1}$$z_{3}$$z_{2}$$Q_{1}^{x}$$Q_{2}^{x}$$Q_{3}^{x}$$Q_{1}^{y}$$Q_{2}^{y}$$Q_{3}^{y}$$Q_{1}^{z}$$Q_{3}^{z}$$Q_{2}^{z}$$Q_{2}^{w}$$Q_{1}^{w}$$Q_{3}^{w}$$v_{e_{1}}$$v_{e_{2}}$$v_{e_{3}}$$v_{e_{4}}$
Figure 3: $G_{H}^{c}$ for $r{=}2$ where $H$ is the hypergraph on
$\\{w,x,y,z\\}$ with edges $e_{1}{=}\\{z,w,x\\}$, $e_{2}{=}\\{w,x,y\\}$,
$e_{3}{=}\\{x,y,z\\}$, $e_{4}{=}\\{y,z,w\\}$. Colours 1, 2, 3 are shown in
green, blue, and orange, respectively.

In Figure 3 we give an example of the construction where $H$ is the complete
3-uniform hypergraph on four vertices. It is easy to see that $H$ has no
1-in-3-colouring. The reader is invited to check that $G_{H}^{c}$ has no
rc-2-factor. Note that to cover $x_{1}$, for example, such a factor must
include as a component either the central clique of $x$ or the clique on
$x_{1}\cup Q_{1}^{x}$.

Now suppose that $H$ has a 1-in-3-colouring $\phi$. We construct an
rc-$r$-factor $F_{\phi}$ for ${G_{H}^{c}}$. Let $x$ be a vertex in $V(H)$ and
suppose $x$ appears in edges $e_{1},\dots,e_{r+1}$. Then, if $\phi(x)=1$, we
include in $F_{\phi}$ the edges of the central clique of $x$ and the edges of
the clique on $v_{e_{i}}\cup Q_{i}^{x}$ for $1\leq i\leq r{+}1$; otherwise, we
include the edges of the clique on $x_{i}\cup Q_{i}^{x}$ for $1\leq i\leq
r{+}1$. The obtained subgraph is clearly rainbow as every component is a
rainbow clique. For each vertex $x$ in $H$, the vertices in the central clique
of $x$ are covered by exactly $r$ edges of $F_{\phi}$, as are those in
$Q_{i}^{x}$ for $1\leq i\leq r{+}1$. It remains to check that, for each edge
$e$ of $H$, the vertex $v_{e}$ is covered by exactly $r$ edges of $F_{\phi}$.
For each vertex $x$ in $e$ such that $\phi(x)=1$, we included $r$ edges that
contain $v_{e}$. Since $\phi$ is a 1-in-3-colouring, there is exactly one such
vertex in $e$, and thus $v_{e}$ is covered by exactly $r$ edges, as required.

Now suppose that ${G_{H}^{c}}$ has an rc-$r$-factor $F$. We will show that $H$
has a 1-in-3 colouring $\phi_{F}$. Observe that, for each $x$ in $V(H)$ and
for $1\leq i\leq r{+}1$, every edge of $Q_{i}^{x}$ must be in $F$, because
every vertex in $Q_{i}^{x}$ is incident with $r{+}1$ edges, two of which have
the same colour. Therefore, if there is an edge in $F$ from $v_{e}$ to
$Q_{i}^{x}$, there cannot be an edge in $F$ from $v_{e}$ to $Q_{j}^{y}$,
unless $x=y$ and $i=j$, because such a pair of edges would connect a
monochromatic pair of edges. We deduce that there is exactly one vertex $x$ in
each edge $e$ of $H$ such that $v_{e}\cup Q_{i}^{x}$ is a component of $F$ for
some value of $i$. Furthermore, if $v_{e}\cup Q_{i}^{x}$ is not a component of
$F$, then $x_{i}\cup Q_{i}^{x}$ is a component of $F$. We conclude that, if
the $i$th and $j$th edges of $x$ are $e$ and $e^{\prime}$, and $v_{e}\cup
Q_{i}^{x}$ is a component of $F$, then $v_{e^{\prime}}\cup Q_{j}^{x}$ is a
component of $F$ (otherwise, there is an edge $x_{i}x_{j}$ in $F$ and then
there are more than $r$ edges in $F$ incident with $x_{j}$). It follows that
we may define a valid 1-in-3-colouring $\phi_{F}$ of $H$ by setting
$\phi_{F}(x)=1$ if and only if $v_{e}\cup Q_{i}^{x}$ is a component of $F$
whenever $e$ is the $i$th edge of $x$ in $H$. ∎

∎

It is natural to ask whether we can find a nice characterisation of edge-
coloured graphs with $\Pi$-$f$-factors, where $\Pi$ is some local property of
edge-coloured graphs; that is, $\Pi$ is valid for an edge-coloured graph
$G^{c}$ whenever it is valid within a constant distance of each vertex.
Unfortunately, such a conjecture would be false in general (unless
${\mathsf{P}}={\mathsf{NP}}$). Consider the following problem for integers $d$
and $r$.

The proof of Theorem 5 can be easily modified to show that the above problem
is hard for $r\geq 2$ and $d\geq 3$. It is enough to demonstrate that, in this
case, a set of edges induces a distance-$d$-coloured $r$-factor if and only if
it induces an rc-$r$-factor. One direction is immediate, since every
rc-$r$-factor in every edge-coloured graph is distance-$d$-coloured by
definition. The other direction requires observing that a
distance-$d$-coloured $r$-factor in the constructed graph ${G_{H}^{c}}$ must
be the disjoint union of rainbow cliques. With some modifications to
${G_{H}^{c}}$, we may even prove that d2c-$r$-fac is hard using the same
proof. However, the modifications are tedious (we leave them as a puzzle for
the interested reader) and suboptimal in a sense we will now describe. The
colouring constructed in the proof of Theorem 5 uses $\Omega(r^{2})$ colours.
While a distance-$d$-coloured $r$-factor requires $\Omega(r^{2})$ colours for
$d\geq 3$, a distance-2-coloured $r$-factor only requires a number of colours
linear in $r$. Therefore, we omit the modification of the above proof and
strengthen the result for the case $d=2$; that is, we show that d$2$c-$r$-fac
is hard even when the number of colours used by the input colouring $c$ is
linear in $r$.

The construction in the proof of the following theorem is similar to that in
the proof of Theorem 5, but the role of the cliques is played by subgraphs
isomorphic to the Kneser graph $KG(2r{-}1,r{-}1)$. Recall that $[n]$ denotes
the set $\\{1,\dots,n\\}$ and $\binom{[n]}{k}$ denotes the set of subsets of
$[n]$ of size $k$. Then, $KG(n,k)$ is the graph on $\binom{[n]}{k}$ with an
edge between $A$ and $B$ if and only if $A\cap B=\emptyset$. Observe that, in
$KG(2r{-}1,r{-}1)$, if $A$ and $B$ are adjacent then $|A\cup B|=2r{-}2$; that
is, there is a unique element $c^{*}(AB)$ in $[2r{-}1]\setminus(A\cup B)$. It
is not difficult to check that $c^{*}$ is a distance-2-colouring of
$KG(2r{-}1,r{-}1)$, which we call the canonical colouring; note that
$KG(2r{-}1,r{-}1)$ is $r$-regular. For example, when $r=3$, we have $KG(5,2)$
which is isomorphic to the Petersen graph, as shown in Figure 4 along with its
canonical colouring.

###### Theorem 6

The distance-$d$-coloured $r$-factor problem is ${\mathsf{NP}}$-complete for
integers $d,r$ at least 2. Furthermore, the distance-2-coloured $r$-factor
problem is ${\mathsf{NP}}$-complete even when the input colouring uses at most
$2r{-}1$ colours.

34124523152535131424 Figure 4: $KG(5,2)$ with its canonical colouring; the
vertex $\\{x,y\\}$ is labelled $xy$.

###### Proof.

As we discussed above, we need only deal with the second part of the statement
of the theorem. Furthermore, it is easy to see that the problem is in
${\mathsf{NP}}$ as in the previous theorem.

Let $r\geq 2$, $\rho=\binom{2r-1}{r-1}$, and let $H$ be a $\rho$-regular,
3-uniform hypergraph. We construct a graph $\bar{G}_{H}$ and a colouring $c$
of its edges using at most $2r{-}1$ colours, such that $H$ has a
1-in-3-colouring if and only if $\bar{G}_{H}^{c}$ has a distance-2-coloured
$r$-factor.

We now describe the construction of $\bar{G}_{H}$. For each vertex $x$ in
$V(H)$ and for $1\leq i\leq\rho$, we add a set of vertices
$Q_{i}^{x}=\\{x_{i}^{X}\mid X\in\binom{[2r-1]}{r-1}\\}$ and a set of vertices
$\bar{Q}_{i}^{x}=\\{\bar{x}_{i}^{X}\mid X\in\binom{[2r-1]}{r-1}\\}$. We add
edges so that the respective subgraphs induced by $Q_{i}^{x}$ and
$\bar{Q}_{i}^{x}$ are isomorphic to $KG(2r{-}1,r{-}1)$; that is, we add an
edge $x_{i}^{X}x_{i}^{Y}$ (and $\bar{x}_{i}^{X}\bar{x}_{i}^{Y}$) if and only
if $X\cap Y=\emptyset$. To simplify our notation, we will relabel two
important vertices. We denote $x_{i}^{\\{1,\dots,r-1\\}}$ by $x_{i}$ and
$\bar{x}_{i}^{\\{r+1,\dots,2r-1\\}}$ by $\bar{x}_{i}$. We add edges between
the vertices $\\{x_{1},\dots,x_{\rho}\\}$ so that they induce a subgraph
isomorphic to $KG(2r{-}1,r{-}1)$; this is done in an arbitrary way, and we
call the subgraph the central gadget of $x$. We add an edge from $\bar{x}_{i}$
to each neighbour of $x_{i}$ in $Q_{i}^{x}$; that is, we add the edge
$\bar{x}_{i}x_{i}^{X}$ if and only if $\\{1,\dots,r-1\\}\cap X=\emptyset$. In
this way, $(Q_{i}^{x}\setminus x_{i})\cup\bar{x_{i}}$ induces a subgraph
isomorphic to $KG(2r{-}1,r{-}1)$. Finally, we add a vertex $v_{e}$ for each
edge $e$ of $H$. When $e$ is the $i$th edge of some vertex $x$, we add edges
from $v_{e}$ to each neighbour of $\bar{x}_{i}$ in $\bar{Q}_{i}^{x}$; that is,
we add the edge $v_{e}\bar{x}_{i}^{X}$ if and only if
$\\{r+1,\dots,2r{-}1\\}\cap X=\emptyset$. Thus,
$(\bar{Q}_{i}^{x}\setminus\bar{x}_{i})\cup v_{e}$ also induces a subgraph
isomorphic to $KG(2r{-}1,r{-}1)$. In Figure 5, we have depicted part of the
constructed graph $\bar{G}_{H}$ in the case $r=3$.

We now describe the colouring $c$ of the edges of $\bar{G}_{H}$. The central
gadget of each vertex is given the canonical colouring of $KG(2r{-}1,r{-}1)$.
The subgraphs induced by $Q_{i}^{x}$ and $\bar{Q}_{i}^{x}$ are also given the
canonical colouring; to clarify, we set $c(x_{i}^{X}x_{i}^{Y})$ (and
$c(\bar{x}_{i}^{X}\bar{x}_{i}^{Y})$) to be the unique element of
$[2r{-}1]\setminus(X\cap Y)$. We set
$c(\bar{x}_{i}x_{i}^{X})=c(x_{i}x_{i}^{X})$ and
$c(v_{e}\bar{x}_{i}^{X})=c(\bar{x}_{i}\bar{x}_{i}^{X})$. This completes the
description of $\bar{G}_{H}^{c}$.

$v_{e}$$Q_{i}^{x}$$\bar{Q}_{i}^{x}$$\bar{x}_{i}$$x_{i}$ Figure 5: A subgraph
of $\bar{G}_{H}$ for some hypergraph $H$, showing how the central clique of
$x$ is connected to $v_{e}$, when $r=3$.

Suppose that $H$ has a 1-in-3-colouring $\phi$. We construct a
distance-2-coloured $r$-factor $F_{\phi}$ for ${\bar{G}_{H}^{c}}$. Let $x$ be
a vertex in $V(H)$ that appears in the edges $e_{1},\dots,e_{\rho}$. Then, if
$\phi(x)=1$, we include in $F_{\phi}$ the edges of the central gadget of $x$,
the edges in the subgraph induced by $(Q_{i}^{x}\setminus
x_{i})\cup\bar{x}_{i}$ and the edges in the subgraph induced by
$(\bar{Q}_{i}^{x}\setminus\bar{x}_{i})\cup v_{e_{i}}$, for $1\leq i\leq\rho$.
If $\phi(x)=-1$, we include in $F_{\phi}$ the edges in $Q_{i}^{x}$ and
$\bar{Q}_{i}^{x}$, for $1\leq i\leq\rho$. Every component of the subgraph
induced by $F_{\phi}$ is distance-2-coloured; verifying that $v_{e}$ is
covered by $r$ edges of $F_{\phi}$ proceeds as in the proof of Theorem 5.

Now suppose that ${\bar{G}_{H}^{c}}$ has a distance-2-coloured $r$-factor $F$.
We will show that $H$ has a 1-in-3-colouring $\phi_{F}$. Observe that, for
each $x$ in $V(H)$ and for $1\leq i\leq\rho$, every edge in the subgraphs
induced by $Q_{i}^{x}\setminus x_{i}$ and
$\bar{Q}_{i}^{x}\setminus\bar{x}_{i}$ must be in $F$. We claim that there
cannot be a vertex $u$ in $Q_{i}^{x}\setminus x_{i}$ and a vertex $u^{\prime}$
in $\bar{Q}_{i}^{x}\setminus\bar{x}_{i}$ such that both $u\bar{x}_{i}$ and
$u^{\prime}\bar{x}_{i}$ are in $F$. From this it follows that for each $x$ in
$V(H)$, either the central gadget of $x$ is a component of $F$ or none of its
edges are in $F$ and the rest of the proof is identical to that of Theorem 5.
Suppose the claim is false, and observe that $u\bar{x}_{i}$ has a colour in
$\\{r,\dots,2r{-}1\\}$ and $u^{\prime}\bar{x}_{i}$ has a colour in
$\\{1,\dots,r\\}$. The edges containing $u$ in $Q_{i}^{x}\setminus x_{i}$ have
colours $1,\dots,r{-}1$; thus, $u^{\prime}\bar{x}_{i}$ has colour $r$
otherwise $F$ is not distance-2-coloured. The edges containing $u^{\prime}$ in
$\bar{Q}_{i}^{x}\setminus\bar{x}_{i}$ have colours $r{+}1,\dots,2r{-}1$; thus,
$u\bar{x}_{i}$ has colour $r$ as well, which is a contradiction. ∎

∎

## Acknowledgments

This work was supported by project GA20-09525S of the Czech Science Foundation
(to R. Čada), by JSPS Grant-in-Aid for Scientific Research (C) JP23K03204 (to
M. Furuya), by JSPS Grant-in-Aid for Scientific Research (C) JP23K03195 (to K.
Ozeki), and by JSPS Grant-in-Aid for Early-Career Scientists JP20K14353 (to T.
Yashima).

## References

  * [1] Jin Akiyama and Mikio Kano.  Factors and Factorizations of Graphs: Proof Techniques in Factor Theory, volume 2031 of Lecture Notes in Mathematics.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
  * [2] Reinhard Diestel.  Graph Theory.  Springer Berlin Heidelberg, 2018.
  * [3] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449–467, 1965/ed.
  * [4] R.J. Faudree, A. Gyárfas, R.H. Schelp, and Zs. Tuza.  Induced matchings in bipartite graphs.  Discrete Mathematics, 78(1-2):83–87, 1989.
  * [5] S. Fujita, R. Li, and S. Zhang.  Color degree and monochromatic degree conditions for short properly colored cycles in edge-colored graphs.  Journal of Graph Theory, 87:362–373, 2017.
  * [6] S. Fujita and C. Magnant.  Properly colored paths and cycles.  Discrete Applied Mathematics, 159:1391–1397, 2011.
  * [7] Michael R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-completeness.  W. H. Freeman, 1979.
  * [8] G. Gutin, B. Sheng, and M. Wahlström.  Odd properly colored cycles in edge-colored graphs.  Discrete Mathematics, 340:817–821, 2017.
  * [9] Takehiro Ito, Akira Kato, Xiao Zhou, and Takao Nishizeki.  Algorithms for finding distance-edge-colorings of graphs.  Journal of Discrete Algorithms, 5(2):304–322, 2007.
  * [10] M. Kano, S. Maezawa, K. Ota, M. Tsugaki, and T. Yashima.  Color degree sum conditions for properly colored spanning trees in edge-colored graphs.  Discrete Mathematics, 343:11, 2020.
  * [11] Mikio Kano and Li Xueliang.  Monochromatic and heterochromatic subgraphs in edge-colored graphs - a survey.  Graphs and Combinatorics, 24(4):237–263, 2008.
  * [12] Jan Kratochvíl.  Complexity of hypergraph coloring and Seidel’s switching.  In Graph-Theoretic Concepts in Computer Science, pages 297–308. Springer Berlin Heidelberg, 2003.
  * [13] A. Lo.  An edge-colored version of Dirac’s Theorem.  SIAM Journal on Discrete Mathematics, 28(1):18–36, 2014.
  * [14] Michael Molloy and Bruce Reed.  A bound on the strong chromatic index of a graph.  Journal of Combinatorial Theory, Series B, 69(2):103–109, 1997\.
  * [15] William T. Tutte.  The factorization of linear graphs.  Journal of the London Mathematical Society, 22:107–111, 1947.
  * [16] William T. Tutte.  The factors of graphs.  Canadian Journal of Mathematics, 4:314–328, 1952.
  * [17] William T. Tutte.  A short proof of the factor theorem for finite graphs.  Canadian Journal of Mathematics, 6:347–352, 1954.


# Auto deep learning for bioacoustic signals

Giulio Tosato1* Abdelrahman Shehata1 Joshua Janssen1 Kees Kamp1 Pramatya Jati1
Dan Stowell1,2

1 Department of Cognitive Science and Artificial Intelligence, Tilburg
University, Tilburg

2 Naturalis Biodiversity Center, Leiden

* Corresponding author<EMAIL_ADDRESS>

## Abstract

This study investigates the potential of automated deep learning to enhance
the accuracy and efficiency of multi-class classification of bird
vocalizations, compared against traditional manually-designed deep learning
models. Using the Western Mediterranean Wetland Birds dataset, we investigated
the use of AutoKeras, an automated machine learning framework, to automate
neural architecture search and hyperparameter tuning. Comparative analysis
validates our hypothesis that the AutoKeras-derived model consistently
outperforms traditional models like MobileNet, ResNet50 and VGG16. Our
approach and findings underscore the transformative potential of automated
deep learning for advancing bioacoustics research and models. In fact, the
automated techniques eliminate the need for manual feature engineering and
model design while improving performance. This study illuminates best
practices in sampling, evaluation and reporting to enhance reproducibility in
this nascent field. All the code used is available at
https://github.com/giuliotosato/AutoKeras-bioacustic

####

Keywords: AutoKeras; automated deep learning; audio classification; Wetlands
Bird dataset; comparative analysis; bioacoustics; validation dataset; multi-
class classification; spectrograms.

##  1 Introduction

The composition of bird communities and fluctuations in specific species’
populations serve as reliable indicators of an ecosystem’s overall well-being
(Tuggener et al., 2019). Through bioacoustic monitoring —a practice that
records and analyzes natural sounds, including bird calls— ornithologists gain
invaluable insights into avian populations, behaviors, and biodiversity. This
acoustic information not only aids in identifying endangered or declining
species but also offers critical data for conservation initiatives.
Bioacoustics research has historically relied on manual identification of bird
species by experts but with the emergence of machine learning and large audio
datasets, automatic recognition of sounds through deep learning has become
feasible and popular (Stowell 2022). However, building highly accurate deep
learning models presents several challenges. Large labeled datasets with many
examples per class are required, but collecting and annotating sufficient bird
vocalization data is difficult and labor-intensive. The models themselves are
complex, with many architectural design choices (e.g. neural network topology,
hyperparameters) that must be optimized for a particular problem. This neural
architecture engineering relies heavily on human expertise through trial-and-
error testing. Moreover, the computational demands for training these deep
networks are substantial, usually necessitating the use of high-performance
GPUs. Together, these factors create a high barrier to entry for domain
specialists like ecologists or conservationists looking to apply deep learning
for bioacoustics.

Recent work has investigated automated machine learning or AutoML, in which a
meta-algorithm automatically optimizes over these choices. This provides a
solution to automate model development and potentially outperform manual
approaches while enabling domain experts with limited machine learning
expertise to create high-quality models (Truong et al., 2019).

Brown et al. (2021) formulate the problem of automating bioacoustics analysis
as one of workflow construction. They aim to build full workflows by searching
over different tasks like preprocessing, feature extraction, and
classification. Their goal is to find combinations of tasks that maximize
accuracy and efficiency for species detection in synthetic soundscapes. They
treat workflow construction as a combinatorial optimization problem and use a
particle swarm optimization algorithm guided by a neural network surrogate
model to search the space of possible workflows. The surrogate model predicts
the accuracy of workflows to guide the search. They test this approach on
different soundscapes and compare it to algorithms like genetic algorithms.
The focus is on constructing workflows from reusable tasks.

In contrast, our work focuses specifically on multi-class bird vocalization
classification problem and aim to find the optimal neural network architecture
and hyperparameters using neural architecture search with AutoKeras. AutoKeras
automatically searches over deep learning models, tuning the architecture and
hyperparameters using network morphism (Wei, 2016). Network morphism in
AutoKeras is built upon Bayesian optimization to search for optimal neural
network architecture and hyperparameters for efficient neural architecture
search (Jin et al., 2019).The framework incorporates a neural network kernel
and a tree-structured acquisition function optimization algorithm to explore
the search space of possible deep models more effectively, which results in
more accurate and efficient feature extraction.

Our central hypothesis is that an AutoKeras-derived model will demonstrate
superior performance over manually-designed models like MobileNet, ResNet50
and VGG16 on a multi-class bird vocalization classification task. To test this
hypothesis, we use the publicly available Western Mediterranean Wetland Birds
dataset containing vocalizations from 20 endemic species. Our methodology
incorporates stratified sampling and data normalization for multi-class
learning. Additionally, we underscore the critical need for a separate test
set to properly evaluate model generalization, given AutoML’s reliance on the
validation set for model selection.

Overall, our automated techniques eliminate manual feature engineering while
improving performance, illuminating the potential to advance bioacoustics
research and models. The study provides key insights into sampling, evaluation
and reporting to enhance reproducibility in this nascent field.

##  2 Methods

###  2.1 Dataset

The Western Mediterranean Wetland Birds dataset was used in this study,
consisting of 201.6 minutes and 5,795 audio excerpts of 20 endemic bird
species found in the Aiguamolls de l’Emporda’ Natural Park (Gómez-Gómez et
al., 2022). This dataset was specifically created to evaluate small-footprint
deep learning approaches for bird species classification using bioacoustic
monitoring devices and is publicly available.

Most species had only call or song vocalizations considered, but for some
species both calls and songs were obtained (Table 1). In some cases, such as
the Dendrocopos minor species, the drumming effect was selected as the
identifier of the bird’s presence. Similarly, for the Ciconia ciconia species,
a sound produced by a repetitive clap with their bills was labelled as bill
clapping, as it was acoustically similar to woodpecker drumming but with
different spectral distribution.

To automatically classify the audio events, spectrograms of the audio files
were generated using a window size of one second. The manually cleaned audio
files in the dataset were split into fragments of one second each, and for
files shorter than one second, the vocalization was repeated to fill the
window size. This window size was chosen to contain at least one complete bird
vocalization and the fewest possible amount of noise. However, the duration of
the audio files varied greatly among species, making it difficult to satisfy
both requirements (Table 1). The mel-scale was used to emphasize the
frequencies of interest.

Bird species | Sound type | Total time (sec.) | Number of cuts
---|---|---|---
Acrocephalus arundinaceus | songs | 1982 | 453
Acrocephalus melanopogon | songs | 2037 | 221
Acrocephalus scirpaceus | songs | 2360 | 121
Alcedo atthis | songs and calls | 351 | 418
Anas strepera | songs | 292 | 96
Anas platyrhynchos | songs | 229 | 70
Ardea purpurea | calls | 128 | 207
Botaurus stellaris | songs | 414 | 436
Charadrius alexandrinus | songs and calls | 109 | 375
Ciconia ciconia | bill clapping | 479 | 121
Circus aeruginosus | calls | 185 | 307
Coracias garrulus | calls | 178 | 267
Dendrocopos minor | drumming | 563 | 494
Fulica atra | calls | 123 | 372
Gallinula chloropus | calls | 107 | 262
Himantopus himantopus | calls | 1212 | 277
Ixobrychus minutus | songs and calls | 148 | 559
Motacilla flava | songs | 292 | 400
Porphyrio porphyrio | songs and calls | 363 | 186
Tachybaptus ruficollis | songs | 543 | 153
Total | - | 12,096 | 5,795

Table 1: Bird species, sound type, total time in seconds, and number of cuts.

###  2.2 Data preprocessing

To address the multi-class nature of this classification problem, we employed
stratified sampling in dividing the dataset into training, validation, and
test sets. Stratified sampling ensures that each class is properly represented
in each set, which helps mitigate issues with class imbalance during model
training and evaluation (Elfil & Negida, 2017).

Our methodology sampled data points from each class in percentages of 70%,
20%, and 10% for the training, validation, and test sets respectively. This
stratification by class allows the model to learn from a dataset that better
represents the overall distribution of classes.

In order to properly stratify the data, we implemented a sampling strategy
that accounted for the different session lengths in the dataset. The sessions
varied in the number of audio samples they contained for each class. To handle
this we sorted these sessions by length in descending order, so that the
sessions with the most samples were first. This sorted session list allowed us
to allocate the longer sessions to the training set first in order to meet the
70% train split ratio as closely as possible. Once the training set was
filled, we moved on to the validation set, and finally the test set with the
remaining shorter sessions.

figurePhotographs paired with spectrograms illustrating the vocalizations of
various bird species, sourced from the Western Mediterranean Wetland Birds
dataset as presented in the paper by (Gómez-Gómez et al., 2022)

After sorting the sessions by length and iterating through them in order, we
loaded the .npy data and labels into the corresponding train, validation, or
test set. This ultimately allowed us to properly stratify the multi-class
data, ensuring adequate samples of each class in each set while accounting for
the variable session lengths.

To further address class imbalances within the training set, class weights
were calculated to guarantee equal learning opportunities from all classes. To
avoid data leakage between the sets, each audio file was strictly allocated to
only one set.

To mitigate any challenges due to disparities in feature range and magnitude,
data normalization was executed using the MinMaxScaler, restricting data
within the range of 0 to 1. Furthermore, the training data was shuffled before
being inputted into the model. This precaution was taken to prevent
overfitting and enhance the model’s robustness.

Figure 1: *

(a) unsorted

Figure 2: *

(b) sorted

Figure 3: Distribution of samples across classes in the train, validation, and
test sets from the Wetlands Bird Dataset. Bar heights represent sample counts,
with percentages indicating the class proportion within each dataset.

###  2.3 Model comparison

The first step was to acquire the three pretrained models originally used by
(Gómez-Gómez et al., 2022) to analyze the dataset, namely MobileNet V2, VGG16,
and ResNet50.

VGG16: Developed by the University of Oxford’s Visual Geometry Group, VGG16 is
a deep convolutional network known for its simplicity. It features 16 weight
layers and uses small 3x3 convolution filters. Despite its power, it’s
computationally intensive (Simonyan and Zisserman 2014).

ResNet50: ResNet50 is a deep neural network designed to tackle the vanishing
gradient problem in very deep architectures. It consists of 50 layers and uses
“skip connections” to facilitate gradient back-propagation, enabling better
performance in a variety of tasks (He et al. 2016).

MobileNet V2: MobileNet V2 is an efficient convolutional neural network
tailored for mobile and low-resource devices. It employs inverted residual
blocks and depthwise separable convolutions to reduce computational cost
without sacrificing accuracy (Howard et al. 2017).

Upon securing these models, their weights were reset, and a Xavier Glorot
initialization was applied to each of them. This is a standard initialization
to ensure stable convergence during training (Glorot & Bengio 2010).

Subsequently, each model was subjected to a series of 20 retraining cycles
using the preprocessed data to enhance the robustness and validity of our
findings. The models were trained for 500 epochs, with a batch size of 32. We
used categorical cross-entropy loss, the Adam optimizer and a learning rate of
0.0001 was selected to encourage stable convergence and to avoid skipping over
local minima, although small learning rate can slow down the training process.

After retraining the baseline models, our next objective entailed employing
AutoKeras to explore a total of 100 distinct models, with the aim of
determining the optimal architecture for our data. AutoKeras searched over
various neural network architectures, including convolutional and dense
networks. It automatically tuned hyperparameters like learning rate, number of
layers, nodes per layer, activation functions, etc.

Upon identifying the optimal model architecture, we saved the best model. We
reset its and retrained it 20 additional times using the same methodology as
the baseline models. This allowed us to bolster the validity of the AutoKeras
model results.

In summary, our model comparison methodology incorporated proper retraining
and tuning of all models for a fair evaluation, along with AutoKeras neural
architecture search to find an optimal architecture for the bird vocalization
classification task.

##  3 Results

The AutoKeras framework searched a total of 100 models, exploring a wide range
of architectures. Figure 4 shows the variability in validation F1 scores among
the models, with a median F1 score plotted over epochs. Several top performing
models are highlighted, including Xception (Figure 5) which demonstrated the
fastest convergence.

Figure 6 provides a more detailed analysis comparing neural network
architectures and optimization techniques. The left column shows the
distribution of maximum validation F1 scores for different configurations like
image block type, optimizer, and specific model architectures. For example,
the efficient and ResNet architectures exhibited distinct patterns in their F1
score distributions. The right column presents the number of models trained
for each configuration category.

In comparison to the three baseline models (MobileNet, ResNet50, VGG16)
proposed by (Gómez-Gómez et al., 2022),, the Xception model identified by
AutoKeras demonstrated superior performance on both the validation and test
datasets as shown in Figure 13. The median and top three runs for each model
are plotted over epochs, along with the confusion matrix analysis on the test
set. The F1 scores on the separate test set validates that the AutoKeras model
has better generalization beyond just the training and validation data.

Confusion matrix analysis was conducted for all four models, revealing certain
shared challenges among them (Figure 17). Across all models, it was observed
that some classes were consistently misclassified, suggesting that these
classes may share similar features that confuse the models, or alternatively,
the data for these classes may be limited or of lower quality. This is a
common issue in multi-class classification tasks and indicates an area for
future investigation.

In summary, our results demonstrated the superiority of the AutoKeras-derived
Xception model over the pretrained models in terms of performance on both
validation and test datasets.

Figure 4:  Median and top three models performances among the 100 different
models trained using AutoKeras.

Figure 5:  AutoKeras-derived Xception architecture.

Figure 6:  Comparative analysis of neural network architectures and
optimization techniques. The left column depicts the maximum validation F1
score distributions for varying configurations, while the right column shows
the number of models trained for each category.

Figure 7:  Number of epochs for which each model was trained for by AutoKeras.

Figure 8:  Distribution of Validation F-Scores of each model across selected
epochs.

Figure 9: *

(a) mobilnet_v2

Figure 10: *

(b) resnet_50

Figure 11: *

(c) vgg_16

Figure 12: *

(d) Xception

| Max test_f1_score | Avg test_f1_score | Min test_f1_score
---|---|---|---
mobilenet_v2 | 0.8230 | 0.7453 | 0.6907
vgg_16 | 0.7248 | 0.6988 | 0.6580
resnet_50 | 0.8077 | 0.7878 | 0.7641
Xception | 0.8555 | 0.8242 | 0.7944

Figure 13:  Comparison of validation F-scores (median and top three runs),
confusion matrix analysis on the test dataset, and F-score evaluation on the
test set.

Figure 14: *

(a) mobilnet_v2

Figure 15: *

(b) resnet_50

Figure 16: *

(c) vgg_16

| F1-score (Gómez-Gómez et al., 2022) | Max test_f1_score | Avg test_f1_score | Min test_f1_score
---|---|---|---|---
mobilenet_v2 | 0.789 | 0.8230 | 0.7453 | 0.6907
vgg_16 | 0.768 | 0.7248 | 0.6988 | 0.6580
resnet_50 | 0.834 | 0.8077 | 0.7878 | 0.7641
Xception | - | 0.8555 | 0.8242 | 0.7944

Figure 17:  Comparison between our result (right) and result obtained by
(Gómez-Gómez et al., 2022) (left) of validation F-scores (median and top three
runs), confusion matrix analysis on the test dataset, and F-score evaluation
on the test set.

##  4 Discussion

The original authors, Gómez-Gómez et al. (2022), used a stratified sampling
technique based on session length. However, they overlooked variations in
session durations within the dataset. Figure 3 illustrates this oversight:
even though sessions are split 70%, 20%, and 10%, the differing session
lengths result in an imbalanced representation. Our data split, which accounts
for session lengths, significantly deviates from their method. This difference
is evident in our results, particularly in the confusion matrix analysis and
overall model performance. It underscores the crucial role of data
preprocessing for unbalanced datasets. Without proper stratification, models
risk poor generalization and inaccurate evaluations.

The methodology of automated machine learning involves the comparative
analysis of several models, subsequently determining the optimal one based on
its performance on the validation set. Hence, the necessity for a separate
test set becomes clear, reinforcing the importance of model generalization
beyond the confines of the training and validation data.

It is crucial to highlight the importance of accurately representing both the
number of samples and misclassified instances in the confusion matrix. This
approach provides a clearer understanding of how the dataset was split,
aligning with the principles of the open science community. This gives a more
detailed picture of system performance than in (Gómez-Gómez et al., 2022), for
example, who reported percentages.

##  5 Conclusion

Our research demonstrates that the model derived via AutoKeras outperformed
the three models initially proposed by the author, as shown in Figure 13. This
indicates the potential of automated machine learning as a transformative tool
that reduces the need for manual design and optimisation of neural network
models, representing an exciting trajectory for future research in this area.

Furthermore, our results highlight the impact of using stratified sampling
strategy that accounted for the different session lengths in the dataset when
working with multi-class imbalanced datasets. By ensuring proper
representation of all classes in the train, validation, and test sets, we were
able to achieve superior performance compared to the original authors. This
underscores the need to report sampling methodology in research studies, as
suboptimal sampling can lead to poor model generalization and inaccurate
evaluation.

Additionally, we emphasize the value of presenting full confusion matrix
numbers rather than solely percentages when dealing with class imbalance.
Reporting the actual misclassification counts provides greater insight into
model performance and aids reproducibility. The inconsistencies between our
stratified approach and the original authors’ non-stratified methodology
demonstrates the significant impact sampling can have on results.

Overall, this study illuminates automated machine learning and stratified
sampling as critical tools for advancing bioacoustics research and models. Our
methodology and reporting practices align with open science principles and
could help improve model development, evaluation, and reproducibility in this
growing field. The code and models are openly available to facilitate further
research.

## Acknowledgements

Funding and publishing assistance provided by Tilburg University.

Giulio Tosato: Project ideation, dataset preprocessing, AutoKeras
implementation, trained VGG16, ResNet50 and MobilnetV́2, data visualizations,
rewrote parts of paper.

Pramatya Jati: reviewed and adjusted paper, handled dataset, rewrote parts of
paper.

Abdelrahman Shehata: reviewed and adjusted paper, rewrote parts of paper,
augmented audio files.

Kees Kamp: reviewed and adjusted paper, handled dataset.

Joshua Janssen: reviewed and adjusted paper, augmented audio files.

Dan Stowell: advised on study design, reviewed and edited the paper.

## Declaration of Interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Data availability

Dataset available from
https://zenodo.org/records/7505820
Deep learning models available at
https://github.com/giuliotosato/AutoKeras-bioacustic

## Bibliography

Brown, A., Montgomery, J., & Garg, S. (2021). Automatic construction of
accurate bioacoustics workflows under time constraints using a surrogate
model. Applied Soft Computing, 113, 107944.
https://doi.org/10.1016/j.asoc.2021.107944

Elfil, M., & Negida, A. (2017). Sampling methods in Clinical Research; an
Educational Review. PubMed, 5(1), e52.
https://pubmed.ncbi.nlm.nih.gov/28286859

Glorot, X. ,Bengio, Y.. (2010). Understanding the difficulty of training deep
feedforward neural networks. Proceedings of the Thirteenth International
Conference on Artificial Intelligence and Statistics, in Proceedings of
Machine Learning Research 9:249-256 Available from
https://proceedings.mlr.press/v9/glorot10a.html.

Gomez, J. (2022). BirdMLClassification [Python].
https://github.com/jogomez97/BirdMLClassification

Gómez-Gómez, J., Vidaña-Vila, E., & Sevillano, X. (2022). Western
Mediterranean wetlands bird species classification: Evaluating small-footprint
deep learning approaches on a new annotated dataset.
https://arxiv.org/abs/2207.05393

K. He, X. Zhang, S. Ren and J. Sun, ”Deep Residual Learning for Image
Recognition,” 2016 IEEE Conference on Computer Vision and Pattern Recognition
(CVPR), Las Vegas, NV, USA, 2016, pp. 770-778, doi: 10.1109/CVPR.2016.90.
https://ieeexplore.ieee.org/document/7780459.

Howard AG, Zhu M, Chen B, Kalenichenko D, Wang W, Weyand T, Andreetto M, Adam
H. (2017). MobileNets: Efficient Convolutional Neural Networks for Mobile
Vision Applications. arXiv:1704.04861 https://arxiv.org/abs/1704.04861

Jin, H., Song, Q., & Hu, X. (2019). Auto-Keras: An Efficient Neural
Architecture Search System. Knowledge Discovery and Data Mining.
https://doi.org/10.48550/arXiv.1806.10282.

Simonyan K, Zisserman A. 2014. Very deep convolutional networks for large-
scale image recognition. arXiv preprint
arXiv:1409.1556.https://doi.org/10.48550/arXiv.1409.1556

Stowell, D. (2022). Computational bioacoustics with deep learning: a review
and roadmap. PeerJ, 10, e13152. https://doi.org/10.7717/peerj.13152

Truong, A. D., Walters, A., Goodsitt, J., Hines, K. E., Bruss, C. B., &
Farivar, R. (2019). Towards Automated Machine Learning: Evaluation and
Comparison of AutoML Approaches and Tools. ArXiv (Cornell University).
https://doi.org/10.1109/ictai.2019.00209

Tuggener, L., Amirian, M., Rombach, K., Lörwald, S., Varlet, A., Westermann,
C., & Stadelmann, T. (2019). Automated Machine Learning in Practice: State of
the Art and Recent Results. 2019 6th Swiss Conference on Data Science (SDS),
31–36. https://doi.org/10.1109/SDS.2019.00-11

Wei, T. (2016). Network morphism. https://doi.org/10.48550/arXiv.1603.01670