# Faster Location in Combinatorial Interaction Testing

Ryan E. Dougherty Department of Electrical Engineering & Computer Science,
United States Military Academy, West Point, NY, 10996, U.S.A. Email:
<EMAIL_ADDRESS>Dylan N. Green Department of Electrical
Engineering & Computer Science, United States Military Academy, West Point,
NY, 10996, U.S.A. Email<EMAIL_ADDRESS>Grace M. Kim Department of
Electrical Engineering & Computer Science, United States Military Academy,
West Point, NY, 10996, U.S.A. Email<EMAIL_ADDRESS>
###### Abstract

Factors within a large-scale software system that simultaneously interact and
strongly impact the system’s response under a configuration are often
difficult to identify. Although screening such a system for the existence of
such interactions is important, determining their location is more useful for
system engineers. Combinatorial interaction testing (CIT) concerns creation of
test suites that nonadaptively either detect or locate the desired
interactions, each of at most a specified size or show that no such set
exists.

Under the assumption that there are at most a given number of such
interactions causing such a response, locating arrays ($\mathsf{LA}$s)
guarantee unique location for every such set of interactions and an algorithm
to deal with outliers and nondeterministic behavior from real systems, we
additionally require the $\mathsf{LA}$s to have a “separation” between these
collections. State-of-the-art approaches generate $\mathsf{LA}$s that can
locate at most one interaction of size at most three, due to the massive
number of interaction combinations for larger parameters if no constraints are
given. This paper presents LocAG, a two-stage algorithm that generates
(unconstrained) $\mathsf{LA}$s using a simple, but powerful partitioning
strategy of these combinations. In particular, we are able to generate
$\mathsf{LA}$s with more factors, with any desired separation, and greater
interaction size than existing approaches.

Keywords: locating array, covering array, genetic algorithm

##  1 Introduction

The analysis of large-scale complex systems has always been a challenge, and
is necessary as such systems are ubiquitous. One difficult aspect of this
analysis is ensuring correct operation, which is accomplished often with
testing. If the number of system configurations is sufficiently high, then
exhaustive testing may be infeasible. Combinatorial interaction testing (CIT)
involves designing and analyzing a test suite to cover many interactions of
system components within the tests. One of the most central objects in CIT is
a covering array, which is a formal model that guarantees all interactions of
size at most a specified number $t$ appear at least a specified number of
times $\lambda$. Utilization of a covering array within a testing scenario is
simple: for each of the covering array’s rows (i.e., a single test), set the
corresponding system component to the specified input. The execution of each
test yields a response from the system. A covering array guarantees that if
the response is desired from each of the test runs, then any undesired
behavior in the system is the result of more than $t$ components. The
limitation of covering arrays is that they do not provide _recovery_ of what
interactions caused the response or what settings to components significantly
impact the response.

Localizing the fault(s) within a system is a well attacked problem; one
strategy for CIT is to run a set of tests and note which tests passed and
failed. Second, test each possible interaction that appears within each failed
test. Third, estimate the likelihood that the interaction did indeed caused
the fault. Finally, generate new tests based on this likelihood. This approach
is known as _adaptive_ testing; however, some testing environments do not
support such a strategy, such as any environment that is nondeterministic
(either in simulation or measurement). Locating arrays, introduced by Colbourn
and McClary [11], are a nonadaptive testing strategy that in addition provide
a guarantee that a set of interactions of a given size $d$ correspond to a
unique set of tests. Therefore, the interactions responsible for the response
can (in principle) be recovered.

Despite the general framework, the constructions of locating arrays have only
been well studied for $d=1$, whether mathematical [11] or computational [27,
28]. This restriction is mostly due to the computational cost involved (see
Section 3) or because of practical motivation, such as systems with “heavy-
hitter” assumptions [41].

In this work, we present an algorithm LocAG that computationally constructs
locating arrays much faster than existing approaches. One consequence is that
we can construct locating arrays for larger and more complex systems than
these approaches, including locating at most $d=2$ interactions for some
systems. Our algorithm contains two stages; the first uses a simple but
powerful partitioning strategy, and the second uses a genetic algorithm. As
far as we are aware, this work is the first to produce non-trivial locating
arrays with $d=2$. Additionally, our formulation allows for redundancy in the
underlying models in cases of testing environment nondeterminism. The paper is
organized as follows:

  * •

Section 2 includes preliminaries about CIT and genetic algorithms.

  * •

Section 3 includes details about, and pseudocode for, our two-stage approach.

  * •

Section 4 contains our experimental design, main research questions, and
experimental evaluations.

  * •

Section 5 contains threats to validity about our method.

  * •

Section 6 contains related work about locating arrays and applications of
evolutionary computation to CIT.

  * •

Section 7 provides future work directions.

  * •

Section 8 concludes the paper.

##  2 Preliminaries

###  2.1 CIT

We develop a formal testing model for CIT. Let $F_{1},\cdots,F_{k}$ be $k$
_factors_ , and each factor $F_{i}$ has an associated set of $v$ _levels_
$\\{x_{i,1},\cdots,x_{i,v}\\}$. A _test_ is an assignment to $F_{i}$ one of
its levels, for each $1\leq i\leq k$. An _interaction_ is a set of pairs
$(F_{i},x_{i})$ where $x_{i}$ is a level for $F_{i}$; if an interaction has
size $t$, it is a _$t$ -way interaction_. Here, $t$ is the _strength_ of the
interaction. Let $\mathsf{A}$ be an array with $N$ rows and $k$ columns, where
each column $i$ corresponds to factor $F_{i}$ and each entry in column $i$ is
one of the levels for $F_{i}$. Let $T$ be a $t$-way interaction, and
$\rho_{\mbox{$\mathsf{A}$}}(T)$ to be the set of rows in $\mathsf{A}$ for
which $T$ appears. The formal definition of “appears” within a row $r$ is that
for each column-value pair $(F_{i},x_{i})$ within $T$, row $r$ has the level
for factor $F_{i}$ set to $x_{i}$. If $T$ appears in a row $r$, then we say
$T$ is _covered_ in $r$. Suppose that every $t$-way interaction $T$ has the
property that $\rho_{\mbox{$\mathsf{A}$}}(T)$ is nonempty (i.e.,
$|\rho_{\mbox{$\mathsf{A}$}}(T)|\geq 1$); then we denote $\mathsf{A}$ as a
_covering array_ $\mbox{$\mathsf{CA}$}(N;t,k,v)$.

Much research has been devoted to finding the smallest covering array for
which the coverage property still holds, i.e., the smallest $N$ for which a
$\mbox{$\mathsf{CA}$}(N;t,k,v)$ exists. This smallest $N$ is the _covering
array number_ [7], and corresponds to the minimum number of tests needed for
such a system. Empirical analysis on real-world systems shows that pair-wise
testing ($t=2$) can detect approximately half of software faults, whereas
higher-strength testing ($t=6$) can detect over 99% of faults [7]. Therefore,
methods to construct covering arrays of higher-strength are desired.

Figure 1 gives an example of a covering array $\mbox{$\mathsf{CA}$}(6;2,4,2)$.
It has $N=6$ rows, $k=4$ columns, $v=2$ different entries (0 and 1), and for
every $t=2$ columns, all $v^{t}=4$ combinations appear at least once. As an
example, for columns 1 and 3 (indexing from 1), we compute
$\rho_{\mbox{$\mathsf{A}$}}(T)$ for all interactions $T$ in these columns:

  * •

When $T=\\{(1,0),(3,0)\\}$, $\rho_{\mbox{$\mathsf{A}$}}(T)=\\{1,6\\}$.

  * •

When $T=\\{(1,0),(3,1)\\}$, $\rho_{\mbox{$\mathsf{A}$}}(T)=\\{2\\}$.

  * •

When $T=\\{(1,1),(3,0)\\}$, $\rho_{\mbox{$\mathsf{A}$}}(T)=\\{4,5\\}$.

  * •

When $T=\\{(1,1),(3,1)\\}$, $\rho_{\mbox{$\mathsf{A}$}}(T)=\\{3\\}$.

$\begin{array}[]{cccc}0&0&0&0\\\ 0&1&1&1\\\ 1&0&1&0\\\ 1&1&0&1\\\ 1&0&0&1\\\
0&1&0&0\end{array}$ Figure 1: A $\mbox{$\mathsf{CA}$}(6;2,4,2)$.

Of course, all of the other $\rho_{\mbox{$\mathsf{A}$}}(T)$ sets need to be
verified for this array to be called a covering array. For two of the four
example interactions, the second and fourth, there was only one test that
witnessed the interaction. If there is experimental noise or measurement error
in the system, and if $\rho_{\mbox{$\mathsf{A}$}}(T)$ is “small” for an
interaction $T$, then running the same test in which $T$ appears may yield
different responses. On the other hand, if $\rho_{\mbox{$\mathsf{A}$}}(T)$ is
“large”, then the likelihood of a response related to $T$ being incorrect from
the ground truth is small. Therefore, we impose another requirement on
covering arrays, in that $|\rho_{\mbox{$\mathsf{A}$}}(T)|\geq\lambda$ for all
interactions $T$ where $\lambda$ is a provided integer. We denote such an
array as $\mbox{$\mathsf{CA}$}_{\lambda}(N;t,k,v)$; here, $\lambda$ is the
_redundancy_. For example, the covering array in Figure 1 has $\lambda=1$ as
all interactions are covered at least once.

A limitation of covering arrays is that they do not permit the identification
of interactions causing the response; locating arrays are an extension that
allows identification. We first extend $\rho$ to include sets of interactions
in a straightforward way. Let $\mathcal{T}$ be a set of $d$ $t$-way
interactions, where $d\geq 1$ is another provided integer. Let $\mathsf{A}$ be
a covering array. Define $\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T})$ to be the
set of rows any interaction in $\mathcal{T}$ appears in $\mathsf{A}$, i.e.,
$\rho_{\mbox{$\mathsf{A}$}}(T)=\bigcup_{T\in\mathcal{T}}\rho_{\mbox{$\mathsf{A}$}}(T)$.
Let $\mathcal{T}_{1},\mathcal{T}_{2}$ be arbitrary distinct $d$-sets of
$t$-way interactions. Suppose it is the case that the symmetric difference of
$\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T}_{1}),\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T}_{2})$
is always larger than $\lambda$; in other words,
$\mathcal{T}_{1}=\mathcal{T}_{2}$ if and only if

$|(\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T}_{1})\cup\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T}_{2}))\setminus((\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T}_{1})\cap\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T}_{2}))|<\lambda.$

If so, then we denote $\mathsf{A}$ as a _$(d,t,\lambda)$ -locating array_,
written as $\mbox{$\mathsf{LA}$}_{\lambda}(N;d,t,k,v)$. When $\lambda=1$, we
instead write $\mathsf{A}$ as a $(d,t)$-locating array. When this symmetric-
difference-on-rows property holds for $\mathcal{T}_{1},\mathcal{T}_{2}$, we
say that these two sets are a _locating pair_ , and a _nonlocating pair_
otherwise.

An example of a locating array $\mbox{$\mathsf{LA}$}_{1}(7;1,2,4,2)$ is shown
in Figure 2. Since $d=1$, it is sufficient to determine that for any single
interaction $T_{1}$ that the rows in which it appears is different than any
other single interaction $T_{2}$. We provide an example for verification.
Suppose $T_{1}=\\{(1,0),(3,0)\\}$ and $T_{2}=\\{(2,1),(4,0)\\}$ are two
interactions (again indexing columns from 1). Then
$\rho_{\mbox{$\mathsf{A}$}}(T_{1})=\\{4,5\\}$ and
$\rho_{\mbox{$\mathsf{A}$}}(T_{2})=\\{1,2\\}$. Since the symmetric difference
of $\\{4,5\\}$ and $\\{1,2\\}$ is 4, which is at least $\lambda=1$, we have
that $T_{1},T_{2}$ are a locating pair. Verification would have to in
principle examine every other pair of interactions.

$\begin{array}[]{cccc}0&1&1&0\\\ 1&1&0&0\\\ 1&0&0&1\\\ 0&0&0&0\\\ 0&1&0&1\\\
0&0&1&1\\\ 1&0&1&0\end{array}$ Figure 2: A
$\mbox{$\mathsf{LA}$}_{1}(7;1,2,4,2)$.

There are variants of the definitions that allow for sets of size _at most_
$d$ (denoted $\overline{d}$ instead of $d$), or individual interaction size
_at most_ $t$ (denoted $\hat{t}$ instead of $t$), or no interaction contained
within another (denoted $\overline{t}$ instead of $t$). The motivation for
these variants is that it is impractical to a priori determine the exact
number of faulty interactions, or how large any interaction itself is. In this
work we focus strictly on building $(\overline{d},t)$-locating arrays as the
other variants are simple modifications of the underlying method. For similar
reasons, we assume that all factors have the same number of levels. Note that
when $d=1$, $(d,t)$-locating arrays are the same as
$(\overline{d},t)$-locating arrays.

###  2.2 Genetic Algorithms in CIT

Metaheuristic algorithms have long played a role in the construction of
combinatorial arrays; see Section 6 for more details. In this paper we employ
a genetic algorithm, and provide an overview of them here. We form a
_population_ $\mathcal{P}$, which is a set of _individuals_. Each individual
is an array of a fixed size, but is not necessarily a covering or locating
array; the number of columns in our setup will always be the number of system
factors, but the (initial) number of rows will be determined after the first
stage of our algorithm terminates (see Section 3 for details). Initially, each
individual is generated uniformly-at-random (i.e., each entry is chosen
uniformly at random, independently of other entries). A fitness score is
calculated for each individual based on the given problem; a common score for
covering arrays is how many interactions are covered in the individual. All
the individuals are now ranked according to their score. Determining the next
population is based on _selection_ , _crossover_ , and _mutation_ operators.
Selection determines which individuals (“parents”) will produce “offspring,”
crossover combines the “genes” of these parents to produce the offspring, and
mutation randomly alters the offspring’s genes. The most fit individuals,
among the original population and produced offspring, survive to the next
generation. The process then repeats until a termination condition is reached.

##  3 Approach

This section contains our two-stage algorithm for constructing locating
arrays. Locating arrays have two requirements: (1) all interactions must be
covered at least a given number of times, and (2) all pairs of sets of
interactions (at most a given size) must have sufficiently high symmetric
difference on rows in which they appear. These requirements appear related but
in some cases are not; covering arrays of course satisfy requirement (1), but
make no guarantee about (2). Suppose that $\mathcal{T}_{1},\mathcal{T}_{2}$
are already found to be a locating pair within some covering array
$\mathsf{A}$. Then adding more rows to $\mathsf{A}$ will not cause them to
become nonlocating. These facts together suggest a two-stage approach, where
the first stage constructs a covering array, and the second stage appends rows
to locate the remaining nonlocating pairs (if any exist).

Why bother with a two-stage approach, and not simply use an existing single
method to directly build a locating array? This is certainly possible, and
there are a number of algorithms to do so [43, 30]; further, using a direct
algorithm is arguably simpler and easier to write and maintain than
coordinated multiple of them. These methods suffer from one big disadvantage:
determining nonlocating pairs is very intensive, both storage-wise (for some
methods) and computationally (for all methods). There are only a small number
of system setups for which a direct locating array construction is known, thus
computationally finding locating arrays is necessary for most cases. We give
our reasoning about computational cost through $(d,t)$-locating arrays for
simplicity; the computation/storage costs are higher for
$(\overline{d},t)$-locating arrays. The number of interactions for a covering
array is $\binom{k}{t}v^{t}$, and thus the number of $d$-sets of interactions
is $S=\binom{\binom{k}{t}v^{t}}{d}$. The number of pairs of $d$-sets to check
non-location is $P=\binom{S}{2}$; when $d>1$ and other parameters are
moderately large, $S$ is extremely large. Suppose that we have a system with
$k=20$ factors, $v=3$, and strength $t=2$. This system contains 1710
interactions. If $d=1$, then $S=1710$, and $P=1461195$; if $d=2$, then
$S=1461195$, and $P$ is greater than 1 trillion. This is just to iterate
through all pairs _once_ ; metaheuristic approaches generally need to compute
the number of nonlocating pairs many times. Therefore, when $d>1$, iterating
through all pairs is largely infeasible; and even if $d=1$, $P$ is still very
large, even for moderately complex systems.

We give further motivation for having two stages. Empirically, many pairs of
$d$-sets within a covering array are also locating, provided $d$ is
sufficiently small. Consider a row-optimal
$\mbox{$\mathsf{CA}$}_{1}(7;2,15,2)$ by the methods of Kleitman [26] and
Spencer [45], and independently by Katona [25], reproduced in Figure 3. Every
interaction appears at least once, but there are many interactions appearing
more than once. Indeed, if the number of rows is larger than $\lambda v^{t}$,
such interactions always exist. In the case of Figure 3, 165 interactions
(39.3%) are covered once, 195 (46.4%) are covered twice, and 60 (14.3%) are
covered thrice.

$\begin{array}[]{ccccccccccccccc}0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&1&1&1&1&1&1&1&1&1&1\\\ 0&1&1&1&1&0&0&0&0&1&1&1&1&1&1\\\
1&0&1&1&1&0&1&1&1&0&0&0&1&1&1\\\ 1&1&0&1&1&1&0&1&1&0&1&1&0&0&1\\\
1&1&1&0&1&1&1&0&1&1&0&1&0&1&0\\\ 1&1&1&1&0&1&1&1&0&1&1&0&1&0&0\end{array}$
Figure 3: A row-optimal $\mbox{$\mathsf{CA}$}_{1}(7;2,15,2)$ by the methods of
Kleitman [26] and Spencer [45], and independently by Katona [25].

In this section, we outline a two-stage approach, which we call LocAG, to
generate locating arrays; the first is in Section 3.1, and the second in
Section 3.2. The overall goal of the first stage is to produce a covering
array with redundancy $\lambda$ with few rows and determine all nonlocating
pairs from the covering array. The second stage produces as few rows as
necessary to locate these remaining pairs, and employs a genetic algorithm.
The workflow of LocAG is shown in Figure 4.

Figure 4: Main overview of LocAG’s workflow. The first stage is divided into
four sub-stages: (FS1) generating an initial covering array $\mathsf{A}$,
(FS2) determining the rows of $\mathsf{A}$ for each $d$-set of interactions,
(FS3) partitioning these $d$-sets based on their rows, and (FS4) using this
partition to intelligently determine non-locating pairs. The second stage
takes the output from the first stage (the non-locating pairs) and runs a
genetic algorithm to find a small number of rows to add to $\mathsf{A}$ so
that all non-locating pairs are now locating.

###  3.1 First Stage

The first stage of LocAG has four sub-parts: (FS1) generation of an initial
covering array $\mathsf{A}$, (FS2) determining the rows of $d$-sets within
$\mathsf{A}$, (FS3) partitioning these $d$-sets into appropriate groups, and
finally (FS4) determining non-locating pairs of $d$-sets based on this
grouping.

We begin with FS1 about generating an initial covering array. We use the CAGen
tool [52], which provides support for generating higher-index covering arrays.
The method is based on the in-parameter-order strategy [31]; we provide high-
level pseudocode of their method in Algorithm 1. In general, any covering
array generation method with support for higher indices would suffice, such as
that of Dougherty et al. [19]. Even though CAGen uses a specific generation
strategy, we do not make any effort to optimize our method by assuming a
specific internal structure of the covering array, such as generation from
some mathematical object [34, 44, 10] or from a recursive construction [7]. We
return to this as future work in Section 8.

Algorithm 1 FS1: CAGen Overview (Initial $\mathsf{CA}$ Generation)

$\mbox{$\mathsf{A}$}\leftarrow$ exhaustive array on $t$ columns with index
$\lambda$.

for $i\leftarrow t,\cdots,k$ do

Horizontally extend $\mathsf{A}$ by one column.

if $\mathsf{A}$ contains an uncovered interaction then

Vertically extend $\mathsf{A}$ until all such interactions are
$\lambda$-covered.

end if

end for

return $\mathsf{A}$.

For the second sub-part FS2, we determine the rows for all $d$-sets of
interactions $D$, the process of which comes from the definition of locating
arrays. For each interaction $I$ in $D$, we determine
$\rho_{\mbox{$\mathsf{A}$}}(I)$ and union all such sets of rows together for
$D$. Pseudocode is presented in Algorithm 2.

Algorithm 2 FS2: Determining Rows of $\overline{d}$-Sets

$\mbox{$\mathsf{A}$}\leftarrow$ a covering array
$\mbox{$\mathsf{CA}$}_{\lambda}(N;t,k,v)$ from Algorithm 1.

for all sets of interactions $D$ of size at most $d$ do

Set $\rho_{\mbox{$\mathsf{A}$}}(D)\leftarrow\bigcup_{I\in
D}\rho_{\mbox{$\mathsf{A}$}}(I)$

end for

return $\rho_{\mbox{$\mathsf{A}$}}$.

The first non-trivial algorithm is for the third sub-part FS3, presented in
Algorithm 3. We create a data structure $RowMap$ consisting of pairs, where
the first element is an integer, which represents how many rows in which a
$d$-set appears, and the second element is a collection of $d$-sets and the
rows in which these $d$-sets appear. Since in FS1 a covering array with
redundancy $\lambda$ was created, every interaction must appear at least
$\lambda$ times; however, some interactions may appear many more times. The
meaning of $RowMap$ is to group $d$-sets into smaller collections based on the
number of rows in which they appear. Consider two elements $K_{1},K_{2}$ in
$RowMap$, and observe the first element $n_{1},n_{2}$ of each. If $n_{1}$ and
$n_{2}$ are sufficiently different, then any pair of $d$-sets they represent
(where one comes from $K_{1}$ and the other from $K_{2}$) appear that many
times differently, which would imply these $d$-sets are a locating pair.
Therefore, we can avoid the computation of whether two $d$-sets are locating
where one $d$-set comes from $K_{1}$, and the other from $K_{2}$. Algorithm 3
creates a dictionary with such a partition.

Algorithm 3 FS3: Partitioning $\overline{d}$-Sets

$\rho_{\mbox{$\mathsf{A}$}}\leftarrow$ result of Algorithm 2.

$RowMap\leftarrow$ empty dictionary, with keys being integers and values being
arrays; insert keys 0 through $|\mbox{$\mathsf{A}$}|$ with empty initial
values into $RowMap$.

for all sets of interactions $D$ of size at most $d$ do

$r\leftarrow|\rho_{\mbox{$\mathsf{A}$}}(D)|$.

Insert $(D,\rho_{\mbox{$\mathsf{A}$}}(D)))$ into $RowMap[r]$.

end for

return $RowMap$.

For FS4, Algorithm 4 determines all nonlocating pairs. If two keys
$K_{1},K_{2}$ are equal, then we need to compare all distinct pairs of
$d$-sets they represent; if not, then we compare all pairs. In addition to
each pair of $d$-sets added to $NonLoc$, we also provide the size of the
symmetric difference. This will help improve the second stage of LocAG for the
following reason. Suppose that $D_{1},D_{2}$ were found to be a nonlocating
pair by Algorithm 4 with symmetric difference size $\ell$, and the goal is
$\lambda$, where $\lambda>\ell$. Then in the rows to-be-added in the second
stage, $D_{1},D_{2}$ only need to have a symmetric difference size
$\lambda-\ell$.

Algorithm 4 FS4: Determine Non-Locating Pairs of $\overline{d}$-Sets

$RowMap\leftarrow$ result of Algorithm 3.

$NonLoc\leftarrow$ empty array.

for all $\\{(K_{1},V_{1}),(K_{2},V_{2})\\}\subseteq RowMap$ do

if $|K_{1}-K_{2}|\geq\lambda$ then

continue.

end if

if $K_{1}\neq K_{2}$ then

for all $(D_{1},R_{1})\in V_{1},(D_{2},R_{2})\in V_{2}$ do

if the symmetric difference of $R_{1},R_{2}$ is less than $\lambda$ then

$\ell\leftarrow$ size of this symmetric difference.

Add $(D_{1},D_{2},\ell)$ to $NonLoc$.

end if

end for

else

for all $\\{(D_{1},R_{1}),(D_{2},R_{2})\\}\subseteq V_{1}$ do

if the symmetric difference of $R_{1},R_{2}$ is less than $\lambda$ then

$\ell\leftarrow$ size of this symmetric difference.

Add $(D_{1},D_{2},\ell)$ to $NonLoc$.

end if

end for

end if

end for

return $NonLoc$.

The runtime of Algorithm 4 is not easily analyzed as that requires knowledge
about how many times each interaction is covered a priori (as well as which
$d$-sets have the same number of rows). Regardless, Algorithm 4 has highest
performance when (1) the number of $d$-sets within each value of $RowMap$ is
relatively balanced, (2) the number of rows in $\mathsf{A}$ is large, and (3)
$d$ is small. For (1), in practice the sizes within $RowMap$ follow a “bell
curve” shape. Observe Table 1 for an example of this behavior. We used CAGen
to generate a covering array $\mbox{$\mathsf{CA}$}_{2}(168;3,40,3)$, and for
$d=1$ took note of how many $d$-sets are covered each number of times.

$|\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T})|$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
# $d$-Sets | 2454 | 10490 | 28681 | 51545 | 62414 | 52722 | 32967 | 15856 | 6356 | 2226 | 746 | 227 | 61 | 8 | 7
Table 1: For a $\mbox{$\mathsf{CA}$}_{2}(168;3,40,3)$ generated by CAGen, we
report the number of times any $d$-set is covered in the array as well as how
many $d$-sets are covered that many times.

For (3), in all experiments we performed, we had $d\in\\{1,2\\}$. We address
(2) next. The CAGen tool produces small covering arrays quickly, but since
Algorithm 4 is much slower on these small arrays than big ones, when $d>1$, we
also employ a different covering array generation approach for comparison.
Specifically, we use the Lovász local lemma construction from Calbert and
Dougherty [4]; we denote this method as LLL. This method constructs a
uniformly random initial array (i.e., all entries chosen uniformly-at-random,
independent of other entries) of a size that meets asymptotic growth, and
checks if it is a covering array. If so, then it terminates. Otherwise, all
columns of the first uncovered interaction’s columns are resampled; the check
is repeated until a covering array is found. The number of rows LLL produces
is higher than that of CAGen in practice, but is both asymptotically optimal
and simpler to implement than CAGen. Even though the number of rows LLL
produces is higher than CAGen, there are both more partitions and fewer
nonlocating pairs in general for the second stage. Very often the first stage
with LLL will locate all pairs of $d$-sets.

####  3.1.1 Optimizations

We now describe additional optimizations to the above algorithms that,
although do change the big-O runtime overall slightly, nevertheless improve
performance in practice. One big optimization is with using sorted arrays
instead of sets, especially the second elements within each value of $RowMap$
during Algorithm 3. This choice has two advantages. The first is that
computing the symmetric difference can be done in linear time in the size of
the original collections by a simple “incrementing” algorithm. The second is
during both the inner and outer loops of Algorithm 4. One can envision each of
these loops instead as a nesting of two loops. Since we only need to consider
2 $d$-sets at a time, and the order does not matter, we iterate through
$RowMap$ in sorted order for the outer loop, where the second loop for
$(K_{2},V_{2})$ starts where $(K_{1},V_{1})$ is currently. The behavior for
the inner loops is similar. Since we loop in sorted order, if the second set’s
smallest row number is larger than that of the first’s, then we can
immediately terminate the loop for the second. The sorting happens in FS3;
this sorting does increase the running time for this substage. However, this
increase is negligible overall as the vast majority of the runtime in the
first stage is within FS4.

###  3.2 Second Stage

If there are no pairs in $NonLoc$ from Algorithm 4, then we skip the second
stage; otherwise, we continue. The goal of LocAG’s second stage is to add rows
to an existing covering array $\mathsf{A}$ from the first stage that support
location for all pairs in $NonLoc$. The number of rows needed will depend on
the number of these pairs as well as what the pairs are; one could use a
computationally expensive algorithm to do so, such as those developed by
Seidel et al. [43]. To do so, we employ a genetic algorithm combined with
binary search. For background on the usage of genetic algorithms and other
metaheuristic techniques with covering arrays, see Timaná-Peña et al. [49].

Individuals within our genetic algorithm are represented by an
$N^{\prime}\times k$ array ($N^{\prime}$ rows, $k$ columns), with initially
all entries set to a uniformly-at-random value between $0$ and $v-1$; we
describe how to calculate $N^{\prime}$ next. Some existing genetic algorithm
approaches [46] require the number of rows a priori; we use a method inspired
by that of Sabharwal et al. [39]. Suppose that we have determined that our GA
was not able to find an individual that locates all pairs in $NonLoc$ with
$N_{lo}$ rows, but was able to do so with $N_{hi}$ rows, where
$N_{hi}>N_{lo}$. We then run binary search within the range $(N_{lo},N_{hi}]$
to find as-small-as-possible number of rows to add $N^{\prime}$ by repeatedly
running our GA. We keep track of the most-fit individuals throughout the
process. To start this process, we initialize $N^{\prime}$ to be the largest
$\ell$ in $NonLoc$, as that many rows are required (at least) to locate that
pair. Note that interactions are not required to appear (separate from
location), as they are guaranteed to be covered by FS1. While the GA fails, we
multiply $N^{\prime}$ by 2; this process terminates as the optimal value of
$N^{\prime}$ is at most the size of $NonLoc$. When the GA finally succeeds
with a value $N^{\prime}$, we set $N_{hi}\leftarrow N^{\prime}$ and
$N_{lo}\leftarrow N^{\prime}/2$. Since locating array sizes grow
logarithmically [43, 13], one could set $N^{\prime}$ initially to be a value
that is guaranteed to work; this will lower the number of GA iterations
slightly, but we do not pursue this here for simplicity.

Once the fitness of all individuals is calculated, we take the most fit half
of the population, and discard the rest. We then select parents for crossover
and/or mutation until we generate enough individuals to restore the population
size. Mutation and crossover operators for the GA are standard. Whenever
mutation is considered, we choose a random number $r_{mut}$ between 1 and 3.
If $r_{mut}=1$, we randomly sample a new row and place it in a random position
of the individual. If $r_{mut}=2$, we do the same but with an entire column.
And if $r_{mut}=3$, we randomly change one entry. For crossover, we generate a
random number $r_{cross}\in\\{1,2\\}$. If $r_{cross}=1$, we perform 1-point
crossover in terms of the rows of the parents; otherwise, we perform 2-point
crossover. The fitness function determines how many locating pairs there are
among those in $NonLoc$ within the individual. Our GA has 100 individuals,
runs for 100 generations, has mutation set at 30%, crossover at 10%, and
employs uniformly-at-random selection of parents each generation.

##  4 Experimental Design and Evaluation

We conducted all experiments in this paper on an Apple Silicon M2 Max
processor with 64GB of memory. Both stages of LocAG were written in C++.111For
ease of generating interactions and $d$-sets of them in the first stage, we
used the CppItertools project by Haining
(https://github.com/ryanhaining/cppitertools) that generates combinations of a
collection. For each parameter situation, we ran 10 iterations of the second
stage when using CAGen (as it is deterministic and the GA is not), and 10
iterations of both the first and second stage when using the LLL method (as
they are both randomized). All times are for single-threaded operation, as
that allows for a more direct comparison to existing methods.

The _type_ of a $\mbox{$\mathsf{LA}$}_{\lambda}(N;d,t,k,v)$ is denoted as
$v^{k}$; for example, a test suite with 20 factors and 2 levels each has type
$2^{20}$. We consider different types in our evaluation of LocAG, namely when
$v\in\\{2,3\\}$ and $k\in\\{10,15,20,30,40,50,100\\}$ for $d=1$; and
$v=3,10\leq k\leq 16$ for $d=2$. We set a timeout of 1 hour (across both
stages) for each type when $d=1$, and 2 hours when $d=2$.

We now investigate the effectiveness of LocAG for constructing locating
arrays. We formulate the following research questions:

  * •

RQ1: How much faster does LocAG produce locating arrays than existing methods
for $d=1$, if at all?

  * •

RQ2: How much smaller are the locating arrays produced by LocAG compared to
existing methods for $d=1$, if at all?

  * •

RQ3: Can LocAG produce locating arrays for $d>1$ in a “reasonable” amount of
time?

###  4.1 RQ1: Performance of LocAG

We answer RQ1 from two perspectives: (1) a comparison between the number of
iterations/found nonlocating pairs in the first stage of LocAG and that of
existing approaches, and (2) overall time across both stages of LocAG.

####  4.1.1 First Stage Iterations Comparison

To see how much this first stage reduces the size of $NonLoc$, we ran an
experiment. We set $d\in\\{1,2\\},t=2,10\leq k\leq 16,v=3$, and $\lambda=2$,
and for each scenario generated covering arrays using the LLL and CAGen
methods. As there may not be a locating array with $d\geq v$ [11], this is the
first computationally challenging case for $d=2$. In Table 2, we show the
overall total number of pairs of $d$-sets, the sizes of covering arrays
produced by both the LLL and CAGen methods, and the number of $d$-sets
compared within FS4 in Algorithm 4 using these covering arrays. It is
immediately apparent that the number of nonlocating pairs is indeed much
smaller than the total number of pairs. Additionally, the average number of
found nonlocating pairs is many thousands of times smaller than the number of
pairs. For example, for $d=2,k=15$, for CAGen the reduction is by a factor of
over 20 thousand; for LLL it is even more dramatic, at 10 million times
smaller (with a sacrifice in the number of rows). This gives strong evidence
that our method is significantly faster than a brute-force method for fitness
calculation.

|  |  | LLL | CAGen
---|---|---|---|---
| $k$ | # Pairs | $N$ | $|NonLoc|$ | $N$ | $|NonLoc|$
$d=1$ | 10 | 81810 | 71 | 10 | 24 | 621
11 | 122265 | 72 | 0 | 33 | 361
12 | 176121 | 73 | 0 | 33 | 519
13 | 246051 | 74 | 1 | 33 | 785
14 | 334971 | 75 | 0 | 33 | 914
15 | 446040 | 75 | 2 | 33 | 1057
| 16 | 582660 | 76 | 1 | 33 | 1299
$d=2$ | 10 | 3346397145 | 71 | 2094 | 24 | 2334285
11 | 7474303980 | 72 | 5765 | 33 | 589839
12 | 15509215260 | 73 | 4114 | 33 | 1205422
13 | 30270424275 | 74 | 4945 | 33 | 2778153
14 | 56102617935 | 75 | 6485 | 33 | 3489916
15 | 99475617780 | 75 | 9458 | 33 | 4822635
| 16 | 169746046470 | 76 | 12291 | 33 | 7961747
Table 2: Comparison between LLL and CAGen for the number of nonlocating pairs
after Algorithm 4 for $(1,2)$ and $(2,2)$-locating arrays. Here, $10\leq k\leq
16,v=3,\lambda=2$. The table reports the total number of pairs for each
situation, the initial covering array size for each method, and the number of
nonlocating pairs for each.

We analyze the memory overhead of our approach compared to a brute-force one,
specificially for iterating over pairs of $d$-sets. There are two brute-force
approaches: calculating $\rho_{\mbox{$\mathsf{A}$}}(\mathcal{T})$ on-the-fly
for each pair of $d$-sets (slower), and storing them in a data structure for
lookup (faster). Note that the faster brute-force method must store all
$d$-sets of interactions with the rows that cover their interactions. The main
overhead with our approach is with the construction of $RowMap$. We show that
the number of keys in $RowMap$ is far smaller than the number of $d$-sets.
Consider the extreme case of every possible number of rows being represented
in $RowMap$; there would be $N$ such sets. LLL will guarantee that $N$ is
$O(v^{t}\log k+\lambda v^{t})$ by the analysis of Calbert and Dougherty [4].
The number of interactions, not even considering $d$-sets of them, is already
vastly larger than this. Therefore, our method is nearly identical in memory
usage compared to the faster brute-force method. Even though this memory
overhead is much larger than for the slower brute-force method, it is many
thousands of times faster (implied by Table 2) as such methods in general have
to repeat the calculation many times.

####  4.1.2 Overall Runtime for Both Stages

We give an analysis of the runtime of the first stage of LocAG; empirical
results are in Subsection 4.2. The main advantage is a lower storage
requirement than existing approaches, notably conditional expectation (CE)
[43], a one-row-at-a-time approach. There, all pairs of $d$-sets need to be
stored to determine an appropriate next row that locates as many pairs as
possible. If there are $S$ $d$-sets (as calculated previously), then CE’s
storage requirement is $O(S^{2})$. Our approach only stores each $d$-set once,
and the rows of the initial covering array. The storage therefore is $O(S\cdot
N)$ where $N$ is the size of this covering array; since $N$ will be
$O(v^{t}\log k+\lambda v^{t})$ by the analysis of Calbert and Dougherty [4],
$N$ is much smaller than $S$, yielding a large improvement over CE.
Additionally, CE’s runtime involves iterating through all pairs at least once,
which is $O(S^{2})$ again. Our method in FS3 only sorts each observed $d$-set
once, which gives $O(N\cdot S\log S)$ runtime overall (as it must iterate
through the covering array’s rows), which is a very large improvement.

The second stage is harder to analyze as that would require knowledge of both
how many nonlocating pairs are left, and what those pairs are. If a collection
of nonlocating pairs are sufficiently “conflicting” (i.e., require many rows
for all pairs to become locating), then that would force the GA to run for
more iterations. As implied by Table 2, it is empirically the case that the
number of nonlocating pairs is dramatically smaller than the original count.
Suppose there are $m$ nonlocating pairs remaining for the second stage. A
simple analysis of randomized constructions of locating arrays [43] shows that
the number of rows required to locate $m$ nonlocating pairs is $O(\log m)$,
where all parameters other than the number of nonlocating pairs (i.e., $d$,
$v$, $t$, $\lambda$) are fixed. Therefore, the GA will take $O(\log\log m)$
overall runs to find a suitable number of rows to add, in expectation, as the
GA also constructs arrays randomly (initially). If the GA’s population
contains $|\mathcal{P}|$ individuals, then the second stage’s total runtime is
$O(|\mathcal{P}|\cdot m\log\log m)$. This analysis implies that if
$|\mathcal{P}|$ is small, the GA will terminate quickly; however, this choice
in general increases $m$.

###  4.2 RQ2: Sizes of $\mathsf{LA}$s from LocAG

This section addresses RQ2. As implied by our analysis in Section 3, the main
bottleneck in LocAG is the runtime. In Tables 3 and 4, we give the results
from our experimental setup for LocAG. They contain the results of generating
$(d,t)$-locating arrays with LocAG for $d=1,v\in\\{2,3\\},2\leq t\leq 5$, and
$k\in\\{10,15,20,30,40,50,100\\}$. For each parameter situation, we consider
when the initial array is generated by CAGen, when it is generated by the LLL
method, and the best known size in the literature (if there is one, we provide
a reference). We provide both the smallest number of rows achieved along with
the corresponding time taken. LocAG has a time-out of one hour; when
generating a locating array would take longer, we note that with $\dagger$.

As is evident, the best known locating arrays are smaller than our results
other than for a handful of situations. However, we are able to generate such
arrays much more quickly than existing methods. Further, we generated locating
arrays for parameters not previously possible, e.g., $t\geq 4$.

|  | $t=2$ | $t=3$ | $t=4$ | $t=5$
---|---|---|---|---|---
| Type | $N$ | Time | $N$ | Time | $N$ | Time | $N$ | Time
$\lambda=1$ | $2^{10}$ | 14/22/11 [28] | 0.3/0.0/0.1 | 36/60/$\star$ | 16.8/0.0/$\star$ | 87/144/$\star$ | 40.9/0.1/$\star$ | 191/315/$\star$ | 202.2/0.2/$\star$
$2^{15}$ | 16/23/15 [28] | 2.5/0.0/3.2 | 47/67/$\star$ | 85.4/0.1/$\star$ | 123/170/$\star$ | 484.9/1.8/$\star$ | 294/391/$\star$ | 1795.6/43.7/$\star$
$2^{20}$ | 18/24/17 [28] | 6.0/0.3/5.4 | 59/72/$\star$ | 169.7/0.4/$\star$ |  $\dagger$/186/$\star$ |  $\dagger$/32.7/$\star$ |  $\dagger$/444/$\star$ |  $\dagger$/580.9/$\star$
$2^{30}$ | 21/26/26 [43] | 28.1/0.1/$\star$ | 67/80/$\star$ | 410.9/2.6/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{40}$ | 24/28/26 [43] | 45.4/0.7/$\star$ |  $\dagger$/86/$\star$ |  $\dagger$/14.1/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{50}$ | 26/29/26 [43] | 107.1/1.7/$\star$ |  $\dagger$/91/$\star$ |  $\dagger$/56.1/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{100}$ | 33/36/31 [43] | 617.6/16.1/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$\lambda=2$ | $2^{10}$ | 20/30/19 [43] | 0.6/0.0/$\star$ | 54/78/$\star$ | 25.2/0.0/$\star$ | 120/183/$\star$ | 40.9/0.1/$\star$ | 277/401/$\star$ | 257.4/0.7/$\star$
$2^{15}$ | 23/31/22 [43] | 2.7/0.0/$\star$ | 69/87/$\star$ | 99.0/0.3/$\star$ | 153/211/$\star$ | 338.0/6.3/$\star$ | 364/482/$\star$ | 1483.7/157.1/$\star$
$2^{20}$ | 25/33/26 [43] | 9.4/0.1/$\star$ | 77/92/$\star$ | 234.7/0.6/$\star$ |  $\dagger$/229/$\star$ |  $\dagger$/104.6/$\star$ |  $\dagger$/532/$\star$ |  $\dagger$/1948.4/$\star$
$2^{30}$ | 30/34/33 [43] | 26.9/0.2/$\star$ |  $\dagger$/99/$\star$ |  $\dagger$/7.1/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{40}$ | 32/35/33 [43] | 51.7/0.3/$\star$ |  $\dagger$/106/$\star$ |  $\dagger$/44.8/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{50}$ | 35/38/33 [43] | 110.5/1.6/$\star$ |  $\dagger$/112/$\star$ |  $\dagger$/174.3/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{100}$ | 41/45/39 [43] | 511.2/14.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$\lambda=3$ | $2^{10}$ | 24/36/24 [43] | 0.6/0.0/$\star$ | 67/94/$\star$ | 28.0/0.0/$\star$ | 142/217/$\star$ | 32.0/0.3/$\star$ | 325/471/$\star$ | 152.0/1.4/$\star$
$2^{15}$ | 29/38/29 [43] | 4.7/0.0/$\star$ | 85/103/$\star$ | 143.6/0.6/$\star$ | 185/248/$\star$ | 417.5/14.8/$\star$ | 432/578/$\star$ | 1706.6/268.7/$\star$
$2^{20}$ | 32/40/31 [43] | 4.9/0.0/$\star$ | 99/109/$\star$ | 407.1/1.1/$\star$ |  $\dagger$/266/$\star$ |  $\dagger$/183.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{30}$ | 36/42/40 [43] | 20.3/0.2/$\star$ |  $\dagger$/118/$\star$ |  $\dagger$/13.2/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{40}$ | 39/45/40 [43] | 50.4/1.1/$\star$ |  $\dagger$/127/$\star$ |  $\dagger$/315.6/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{50}$ | 43/46/40 [43] | 82.6/2.0/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{100}$ | 50/54/46 [43] | 347.4/14.9/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$\lambda=4$ | $2^{10}$ | 31/43/30 [43] | 0.6/0.0/$\star$ | 87/109/$\star$ | 21.6/0.0/$\star$ | 215/248/$\star$ | 51.0/0.4/$\star$ | 497/536/$\star$ | 141.4/1.8/$\star$
$2^{15}$ | 37/45/34 [43] | 4.0/0.0/$\star$ | 115/118/$\star$ | 118.4/0.2/$\star$ | 256/283/$\star$ | 441.5/19.7/$\star$ | 558/625/$\star$ | 1592.3/169.9/$\star$
$2^{20}$ | 41/46/37 [43] | 10.3/0.1/$\star$ | 128/124/$\star$ | 348.8/1.5/$\star$ |  $\dagger$/299/$\star$ |  $\dagger$/242.5/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{30}$ | 47/48/47 [43] | 23.8/0.1/$\star$ |  $\dagger$/132/$\star$ |  $\dagger$/17.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{40}$ | 50/50/47 [43] | 43.1/0.9/$\star$ |  $\dagger$/141/$\star$ |  $\dagger$/108.6/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{50}$ | 53/56/47 [43] | 72.9/5.2/$\star$ |  $\dagger$/145/$\star$ |  $\dagger$/448.6/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$2^{100}$ | 64/59/53 [43] | 742.1/13.0/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
Table 3: Results for LocAG in finding $(\overline{1},t,\lambda)$-locating
arrays where $2\leq t\leq
5,k\in\\{10,15,20,30,40,50,100\\},v=2,1\leq\lambda\leq 4$. There are three
values of $N$ and time reported for each $t$; what is reported by LocAG where
CAGen generated the initial covering array, the same where LLL generated the
initial covering array, and the smallest known $N$ in the literature. The
corresponding time values are those from the same locating array method (i.e.,
not necessarily the smallest time across all literature), and are reported in
seconds. When no $N$ is known from existing work, or no time is provided from
existing work, a $\star$ is given. A reference is also provided when
available. In case of timeout for LocAG, $\dagger$ is given.

|  | $t=2$ | $t=3$ | $t=4$ | $t=5$
---|---|---|---|---|---
| Type | $N$ | Time | $N$ | Time | $N$ | Time | $N$ | Time
$\lambda=1$ | $3^{10}$ | 35/55/29 [28] | 7.4/0.0/4.0 | 132/235/$\star$ | 52.7/0.0/$\star$ |  $\dagger$/862/$\star$ |  $\dagger$/0.7/$\star$ |  $\dagger$/2918/$\star$ |  $\dagger$/2.4/$\star$
$3^{15}$ | 42/59/40 [43] | 10.8/0.0/$\star$ | 165/262/$\star$ | 221.4/0.3/$\star$ |  $\dagger$/997/$\star$ |  $\dagger$/28.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{20}$ | 45/61/44 [43] | 35.0/0.0/$\star$ | 191/280/$\star$ | 523.1/1.9/$\star$ |  $\dagger$/1083/$\star$ |  $\dagger$/365.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{30}$ | 54/65/57 [43] | 117.1/0.0/$\star$ |  $\dagger$/304/$\star$ |  $\dagger$/25.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{40}$ | 58/68/57 [43] | 247.6/0.1/$\star$ |  $\dagger$/320/$\star$ |  $\dagger$/154.9/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{50}$ | 63/69/57 [43] | 411.6/0.2/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{100}$ | 76/77/67 [43] | 1985.0/4.4/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$\lambda=2$ | $3^{10}$ | 51/74/46 [43] | 5.9/0.0/$\star$ | 187/302/$\star$ | 36.3/0.0/$\star$ |  $\dagger$/1077/$\star$ |  $\dagger$/2.1/$\star$ |  $\dagger$/3587/$\star$ |  $\dagger$/7.0/$\star$
$3^{15}$ | 57/78/52 [43] | 8.7/0.0/$\star$ | 221/331/$\star$ | 197.1/1.0/$\star$ |  $\dagger$/1221/$\star$ |  $\dagger$/90.3/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{20}$ | 62/81/57 [43] | 18.1/0.0/$\star$ | 253/350/$\star$ | 607.5/6.2/$\star$ |  $\dagger$/1313/$\star$ |  $\dagger$/1152.9/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{30}$ | 72/86/70 [43] | 59.1/0.1/180 |  $\dagger$/376/$\star$ |  $\dagger$/85.8/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{40}$ | 77/88/70 [43] | 138.1/0.3/180 |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{50}$ | 82/90/70 [43] | 299.7/0.7/180 |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{100}$ | 98/97/81 [43] | 1752.5/12.5/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$\lambda=3$ | $3^{10}$ | 64/91/57 [43] | 6.7/0.0/$\star$ | 264/359/$\star$ | 41.7/0.1/$\star$ |  $\dagger$/1260/$\star$ |  $\dagger$/3.5/$\star$ |  $\dagger$/4157/$\star$ |  $\dagger$/9.2/$\star$
$3^{15}$ | 70/96/65 [43] | 27.5/0.0/$\star$ | 299/390/$\star$ | 273.5/1.8/$\star$ |  $\dagger$/1412/$\star$ |  $\dagger$/165.3/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{20}$ | 90/99/69 [43] | 48.4/0.0/$\star$ | 325/411/$\star$ | 412.8/10.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{30}$ | 97/103/83 [43] | 166.2/0.2/$\star$ |  $\dagger$/438/$\star$ |  $\dagger$/143.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{40}$ | 100/106/83 [43] | 327.8/0.5/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{50}$ | 102/109/83 [43] | 491.2/1.2/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{100}$ |  $\dagger$/116/94 [43] |  $\dagger$/22.0/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$\lambda=4$ | $3^{10}$ | 86/106/66 [43] | 8.3/0.0/$\star$ | 267/411/$\star$ | 49.9/0.2/$\star$ |  $\dagger$/1427/$\star$ |  $\dagger$/5.3/$\star$ |  $\dagger$/4676/$\star$ |  $\dagger$/14.7/$\star$
$3^{15}$ | 79/111/73 [43] | 136.8/0.0/$\star$ | 326/444/$\star$ | 248.7/2.4/$\star$ |  $\dagger$/1585/$\star$ |  $\dagger$/225.5/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{20}$ | 99/115/79 [43] | 49.0/0.0/$\star$ | 343/465/$\star$ | 623.9/16.9/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{30}$ | 110/119/95 [43] | 77.3/0.2/$\star$ |  $\dagger$/494/$\star$ |  $\dagger$/213.8/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{40}$ | 117/123/95 [43] | 158.2/0.7/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{50}$ | 122/125/95 [43] | 506.9/1.9/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
$3^{100}$ |  $\dagger$/133/107 [43] |  $\dagger$/32.5/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$ |  $\dagger$/$\dagger$/$\star$
Table 4: Results for LocAG in finding $(\overline{1},t,\lambda)$-locating
arrays where $2\leq t\leq
5,k\in\\{10,15,20,30,40,50,100\\},v=3,1\leq\lambda\leq 4$. There are three
values of $N$ and time reported for each $t$; what is reported by LocAG where
CAGen generated the initial covering array, the same where LLL generated the
initial covering array, and the smallest known $N$ in the literature. The
corresponding time values are those from the same locating array method (i.e.,
not necessarily the smallest time across all literature), and are reported in
seconds. When no $N$ is known from existing work, or no time is provided from
existing work, a $\star$ is given. A reference is also provided when
available. In case of timeout for LocAG(1 hour), $\dagger$ is given.

|  | $t=2$
---|---|---
| Type | $N$ | Time
$\lambda=1$ | $3^{5}$ | 49 | 0.3
$3^{6}$ | 56 | 1.6
$3^{7}$ | 59 | 5.7
$3^{8}$ | 61 | 18.5
$3^{9}$ | 67 | 47.4
$3^{10}$ | 72 | 112.8
$\lambda=2$ | $3^{5}$ | 68 | 1.1
$3^{6}$ | 73 | 4.5
$3^{7}$ | 79 | 19.0
$3^{8}$ | 86 | 44.9
$3^{9}$ | 88 | 158.1
$3^{10}$ | 95 | 358.2
$\lambda=3$ | $3^{5}$ | 84 | 1.7
$3^{6}$ | 93 | 7.3
$3^{7}$ | 95 | 19.0
$3^{8}$ | 105 | 95.8
$3^{9}$ | 110 | 268.3
$3^{10}$ | 111 | 3061.4
$\lambda=4$ | $3^{5}$ | 99 | 2.7
$3^{6}$ | 107 | 12.3
$3^{7}$ | 113 | 48.0
$3^{8}$ | 121 | 141.7
$3^{9}$ | 126 | 1212.4
$3^{10}$ | 136 | 6993.0
Table 5: Results for LocAG in finding $(\overline{2},t,\lambda)$-locating
arrays where $t=2,5\leq k\leq 10,v=3,1\leq\lambda\leq 4$. We used the LLL
method for initial covering array generation. The corresponding times are for
both stages, and are reported in seconds.

###  4.3 RQ3: Generating $\mathsf{LA}$s with $d>1$

This subsection concerns answering RQ3. In Table 5, we show the results of
LocAG for generating $(\overline{2},2)$-locating arrays with $5\leq k\leq
10,1\leq\lambda\leq 4$, and $v=3$. This is the first nontrivial case as there
may not exist locating arrays with $\overline{d}=\overline{2}$ and $v=2$ [11].
Here, we use the LLL method for initial array generation as CAGen’s usage
yields many more nonlocating pairs, causing the second stage to become much
slower. The timeout for these experiments was 2 hours.

These are the first locating arrays with $\overline{d},t$ both at least 2;
even so, the time taken increases rapidly as parameters increase. To consider
the cases when $d$ and $t$ are larger, or even if $k>10$ or $v>3$, would
require a new method or assumption about the underlying $d$-sets.
Nevertheless, for “small” systems, LocAG can indeed generate locating arrays
with $d>1$ in a “reasonable” amount of time.

##  5 Threats to Validity

We are aware of several threats to the validity of our approach. The main
threat involves the correctness of the written programs for both stages of
LocAG. First, to determine the correctness of the CAGen program for the first
stage, we wrote an independent covering array verifier. Next, we ran the
program on the resulting initial covering arrays; all these covering arrays
passed verification. Second, for both stages we created implementations of the
algorithms in Section 3 in both Python and C++. For the first stage and for
each parameter situation in Subsection 4.2, we fixed a single covering array
and verified that the resulting $NonLoc$ set is the same for both
implementations.

There is a potential threat for the second stage of LocAG as genetic
algorithms have not been applied to locating arrays as far as we are aware. We
do not see any threat with the chosen representation, selection operators, and
fitness function of our GA as they are standard with respect to covering
arrays; see Stardom [46] for details.

##  6 Related Work

Related works fall into four main categories: mathematical constructions,
computational approaches, metaheuristic methods, and applications of locating
arrays in experiments. There are several works that give a general background
for CIT, notably those by Kuhn et al. [29] and Nie and Leung [37].
Additionally there are many other covering array construction approaches, such
as AETG [6] and the density algorithm [3].

Locating arrays were first introduced by Colbourn and McClary [11] as a
variant of the existing covering arrays, as well as a related type called
detecting arrays; see [12] for a more recent summary. The algorithm to recover
the significant interactions for a detecting arrays is more efficient than the
same for a locating arrays, but their sizes are in general larger. We do not
pursue detecting arrays in our work, and leave such application for future
work. There has been some work in finding optimal locating arrays for $d=1$
and $t=1$ [48, 9], with bounds for this case for detecting arrays [14].
Asymptotic bounds are pursued by Colbourn and Syrotiuk [13]. Some recursive
constructions were proved by Colbourn and Fan [8], although only for the $d=1$
case. Very recently, Colbourn and Syrotiuk [15] construct detecting arrays for
$t=1$ and arbitrary $d$ using a variant of separating hash families. Detecting
arrays have a stronger condition than for locating arrays, but contain more
rows in general. The produced arrays by many of these methods have some
internal structure, and thus the methods in this paper could in principle
reduce the number of to-be-compared $d$-sets.

Computational methods based on the Stein-Lovász-Johnson paradigm [47, 33, 24]
were pursued by Seidel et al. [43]. Nagamoto et al. [35] developed a two-stage
method for some locating array parameters that is similar in spirit to our
method. Our work could be considered an extension based on the partitioning
strategy we developed. Lanus et al. [30] created a tree-based verification
algorithm for locating arrays and was the first paper (as far as we are aware)
to computationally create locating arrays with both $d>1$; however, they only
concerned _main effects_ , where $t=1$ (see Colbourn and Syrotiuk for
discussion on these effects in CIT [14]). There may potentially be some more
optimizations in our approach based on theirs.

Dougherty [18] partitioned covering array generation into multiple stages
(instead of just 1 or 2) using a genetic algorithm [18]. Instead of using the
algorithm to modify the arrays directly, the genetic algorithm helped
determine the optimal number of stages in which to have every interaction
covered $\lambda$ times. In principle his methods can also be applied to
locating array generation, as follows. Suppose the pairs of $d$-sets to check
are $\mathcal{P}=\\{P_{1},\cdots,P_{s}\\}$. Instead of having a large storage
requirement as our work does here, determine an efficiently-computable
partition of $\mathcal{P}$, construct locating arrays for each part, and
vertically juxtapose all such arrays. Such methods were used for covering
array generation using groups [40].

Hnich et al. [21] used constraint-based methods for covering arrays, and this
was later applied to finding $(\overline{1},2)$ and
$(\overline{1},3)$-locating arrays by Konishi et al. [27]. Jin et al. [22]
used Satisfiability Modulo Theories for finding “constrained” $(1,2)$-locating
arrays. The search space increases dramatically as $d$ and $t$ increase, as
discussed in Section 3. Thus a new idea is required if
constraint/satisfiability methods are to be employed for larger $d,t$. Jin,
Shi, and Tsuchiya [23] also used a satisfiability approach for finding
detecting arrays where there is a constraint on the $d$-sets considered for
$d\in\\{1,2\\}$, which involves a notably smaller set of $d$-sets compared to
all $d$-sets. Our approach is only for unconstrained locating arrays; we plan
on incorporating constraints into our algorithm as future work.

Simple hill-climbing approaches often lead to local optima for covering array
generation [46]. As a result, evolutionary computation has been employed to
covering arrays in many forms, of which we name a few: simulated annealing
[51, 20, 50], genetic algorithms [46, 39, 18], tabu search [38, 53], particle
swarm optimization [32], and ant colony optimization [5]. As far as we are
aware, there has only been one previous work, by Konishi et al. [28], that
used evolutionary computation for finding locating arrays, specifically with
simulated annealing. To do so, they used a two-phase algorithm which
continually binary searches between pre-calculated bounds until a locating
array is found; this is the same idea as our second stage. The second phase
occurs as simulated annealing is used once again to refine the solution. This
work indicated that simulated annealing can scale with large systems if $t=2$,
yet often is unable to produce locating arrays for larger $t$ values.

There have been several real-world experiments performed to identify
significant interactions in screening experiments using locating arrays.
Aldaco et al. [2] constructed a $(\overline{1},\overline{2},2)$-locating array
on a system with 75 factors for screening the response of TCP throughput.
Their approach was initially similar to ours: they first generated a covering
array, and applied post-optimization [36] to reduce its size; see Section 7
for details on post-optimization. Compton et al. [16] constructed a
$(\overline{1},\overline{2})$-locating array for 24 factors in screening a
wireless testbed system. Seidel et al. [42] analyzed the same testbed system,
along with another larger wireless network system, with a “heavy hitters” tree
search algorithm for more robust analysis of the significant interactions.
Seidel et al. [41] analyze robustness of recovery as a function of environment
nondeterminism. Very recently, Akhtar et al. [1] further discuss the same
methods with other real-world experiments and data sets. Nearly all of the
locating arrays used within screening experiments are locating arrays with
$d=1$ and $t=2$, and thus can only recover one significant interaction. We
hope that faster construction methods, such as that discussed in this paper,
can aid future experiment analysis methods to more efficiently identify more
than one such interaction.

##  7 Future Work

As mentioned previously, detecting arrays in general employ more rows than
locating arrays do, but the algorithm for recovery of significant interactions
is much more efficient. We plan on both incorporating a version of LocAG that
includes detecting arrays, as well as locating/detecting arrays of “mixed”
types. This last point is important as real-world systems do not necessarily
have the same number of levels for each factor.

For the first stage of LocAG, the CAGen tool constructs covering arrays using
the “in-parameter-order” algorithm [31], which adds one column at a time and
any necessary rows after the new column is added. One could check $d$-sets of
interactions in a similar way; if $\mathcal{T}_{1},\mathcal{T}_{2}$ are
already a locating pair, then adding rows will not make them nonlocating.
Additionally, the LLL method often constructed an array that is already
locating, thus removing the need for the second stage. This gives a potential
research direction of adding an intermediary stage based on the work of Nayeri
et al. [36] called “postopimization.” Applied to our setting, this method
takes a locating array, rearranges rows, and randomizes “don’t care” values
until a row is determined to be redundant (which is then removed). This
process repeats until a termination condition is reached.

The second stage of LocAG, even though more efficient than a brute-force
search as it only operates on a much smaller number of $d$-sets, was
nevertheless often the slower of the two stages, especially when the other
parameters were small enough. An explanation is that most individuals in the
population have very high fitness, but not what is needed to locate; this was
observed for a related object by Dougherty [17]. A multi-stage approach would
be more suitable, such as stopping the GA when a target fitness value smaller
than $|NonLoc|$ is achieved, and starting another GA on the remaining pairs.
We are currently pursuing this direction.

##  8 Conclusion

In this paper we introduced LocAG, a two-stage algorithm for constructing
locating arrays that uses a simple but powerful partitioning strategy in its
first stage, and a genetic algorithm in the second stage. This strategy
utilized the empirical observation that in nearly every covering array with
redundancy $\lambda$, there are many interactions covered more than $\lambda$
times. If there is sufficient difference between the number of times two sets
of interactions are covered, then they automatically are locating pairs. The
partitioning drastically reduces the number of pairs needed to be compared in
determining whether or not they are locating. As we have shown, the number of
pairs is much smaller than the total number of pairs; we then utilize a simple
genetic algorithm to locate all the remaining pairs.

As a result, we presented the first nontrivial locating arrays with (1)
$t\in\\{4,5\\}$, $v\in\\{2,3\\}$ and $d=1$, and (2) $t=2$ and
$\overline{d}=\overline{2}$. Further, the parameters for which a locating
array already exists are handled much more quickly by our two-stage algorithm
than previous approaches.

## Acknowledgments

The opinions in the work are solely of the authors, and do not reflect those
of the U.S. Army, U.S. Army Research Labs, the U.S. Military Academy, or the
Department of Defense.

## References

  * [1] Yasmeen Akhtar, Fan Zhang, Charles J. Colbourn, John Stufken, and Violet R. Syrotiuk.  Scalable level-wise screening experiments using locating arrays.  Journal of Quality Technology, 0(0):1–14, July 2023.  Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/00224065.2023.2220973.
  * [2] Abraham N. Aldaco, Charles J. Colbourn, and Violet R. Syrotiuk.  Locating Arrays: A New Experimental Design for Screening Complex Engineered Systems.  SIGOPS Oper. Syst. Rev., 49(1):31–40, January 2015.  Place: New York, NY, USA Publisher: ACM.
  * [3] Renée C. Bryce and Charles J. Colbourn.  The Density Algorithm for Pairwise Interaction Testing.  Software Testing, Verification, and Reliability, 17:159–182, 2007\.
  * [4] Mason R. Calbert and Ryan E. Dougherty.  Upper Bounds for Covering Arrays of Higher Index, June 2023\.  arXiv:2211.01209 [cs, math].
  * [5] Xiang Chen, Qing Gu, Ang Li, and Daoxu Chen.  Variable Strength Interaction Testing with an Ant Colony System Approach.  In 2009 16th Asia-Pacific Software Engineering Conference, pages 160–167, December 2009.  ISSN: 1530-1362.
  * [6] David M. Cohen, Siddhartha R. Dalal, Michael L. Fredman, and Gardner C. Patton.  The AETG system: An approach to testing based on combinatorial design.  IEEE Transactions on Software Engineering, 23(7):437–444, 1997\.  Publisher: IEEE.
  * [7] Charles J. Colbourn.  Combinatorial aspects of covering arrays.  Le Matematiche (Catania), 58:121–167, 2004.
  * [8] Charles J. Colbourn and Bingli Fan.  Locating one pairwise interaction: Three recursive constructions.  Journal of Algebra Combinatorics Discrete Structures and Applications, 3(3):127–134, September 2016.
  * [9] Charles J. Colbourn, Bingli Fan, and Daniel Horsley.  Disjoint Spread Systems and Fault Location.  SIAM Journal on Discrete Mathematics, 30(4):2011–2026, January 2016\.  Publisher: Society for Industrial and Applied Mathematics.
  * [10] Charles J. Colbourn, Erin Lanus, and Kaushik Sarkar.  Asymptotic and constructive methods for covering perfect hash families and covering arrays.  Designs, Codes and Cryptography, 86(4):907–937, April 2018.
  * [11] Charles J. Colbourn and Daniel W. McClary.  Locating and detecting arrays for interaction faults.  Journal of Combinatorial Optimization, 15(1):17–48, January 2008\.
  * [12] Charles J. Colbourn and Violet R. Syrotiuk.  Coverage, Location, Detection, and Measurement.  In 2016 IEEE Ninth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pages 19–25, Chicago, IL, USA, April 2016. IEEE.
  * [13] Charles J. Colbourn and Violet R. Syrotiuk.  On a Combinatorial Framework for Fault Characterization.  Mathematics in Computer Science, 12(4):429–451, December 2018.
  * [14] Charles J. Colbourn and Violet R. Syrotiuk.  Detecting Arrays for Main Effects.  In Miroslav Ćirić, Manfred Droste, and Jean-Éric Pin, editors, Algebraic Informatics, Lecture Notes in Computer Science, pages 112–123, Cham, 2019. Springer International Publishing.
  * [15] Charles J. Colbourn and Violet R. Syrotiuk.  Detecting arrays for effects of single factors.  In 8th European Congress of Mathematics. EMS Press, Portoroz, Slovenia, 2022.
  * [16] Randy Compton, Michael T. Mehari, Charles J. Colbourn, Eli De Poorter, and Violet R. Syrotiuk.  Screening interacting factors in a wireless network testbed using locating arrays.  In 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 650–655, San Francisco, CA, USA, April 2016. IEEE.
  * [17] Ryan E. Dougherty.  Hash Families and Applications to t-Restrictions.  PhD Thesis, Arizona State University, 2019.
  * [18] Ryan E. Dougherty.  Genetic algorithms for redundancy in interaction testing.  In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO ’20, pages 1241–1249, New York, NY, USA, June 2020. Association for Computing Machinery.
  * [19] Ryan E. Dougherty, Kristoffer Kleine, Michael Wagner, Charles J. Colbourn, and Dimitris E. Simos.  Algorithmic methods for covering arrays of higher index.  Journal of Combinatorial Optimization, 45(1):28, December 2022.
  * [20] Xu Guo, Xiaoyu Song, and Jian-tao Zhou.  Effective Discrete Memetic Algorithms for Covering Array Generation.  In 2018 IEEE 42nd Annual Computer Software and Applications Conference (COMPSAC), volume 01, pages 298–303, Tokyo, Japan, July 2018. IEEE.  ISSN: 0730-3157.
  * [21] Brahim Hnich, Steven D. Prestwich, Evgeny Selensky, and Barbara M. Smith.  Constraint Models for the Covering Test Problem.  Constraints, 11(2):199–219, July 2006.
  * [22] Hao Jin, Takashi Kitamura, Eun-Hye Choi, and Tatsuhiro Tsuchiya.  A Satisfiability-Based Approach to Generation of Constrained Locating Arrays.  In 2018 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pages 285–294, Västerås, Sweden, April 2018. IEEE.
  * [23] Hao Jin, Ce Shi, and Tatsuhiro Tsuchiya.  Constrained detecting arrays: Mathematical structures for fault identification in combinatorial interaction testing.  Information and Software Technology, 153:107045, January 2023.
  * [24] David S. Johnson.  Approximation algorithms for combinatorial problems.  Journal of Computer and System Sciences, 9(3):256–278, December 1974.
  * [25] G. O. H. Katona.  Two applications (for search theory and truth functions) of Sperner type theorems.  Periodica Mathematica Hungarica, 3(1):19–26, March 1973.
  * [26] Daniel J. Kleitman and Joel Spencer.  Families of k-independent sets.  Discrete Mathematics, 6(3):255–262, January 1973.
  * [27] Tatsuya Konishi, Hideharu Kojima, Hiroyuki Nakagawa, and Tatsuhiro Tsuchiya.  Finding Minimum Locating Arrays Using a CSP Solver.  Fundamenta Informaticae, 174(1):27–42, January 2020.  Publisher: IOS Press.
  * [28] Tatsuya Konishi, Hideharu Kojima, Hiroyuki Nakagawa, and Tatsuhiro Tsuchiya.  Using simulated annealing for locating array construction.  Information and Software Technology, 126:106346, October 2020.
  * [29] D. RIchard Kuhn, Raghu N. Kacker, and Yu Lei.  Introduction to Combinatorial Testing.  Chapman & Hall/CRC Innovations in Software Engineering and Software Development Series. Taylor & Francis, Boca Raton, FL, 2013.
  * [30] Erin Lanus, Charles J. Colbourn, and Douglas C. Montgomery.  Partitioned Search with Column Resampling for Locating Array Construction.  In 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pages 214–223, Xi’an, China, April 2019. IEEE.
  * [31] Yu Lei and Kuo-Chung Tai.  In-parameter-order: A test generation strategy for pairwise testing.  In Proceedings Third IEEE International High-Assurance Systems Engineering Symposium, pages 254–261, Washington, DC, USA, 1998\. IEEE.
  * [32] Zhao Li, Yuhang Chen, Yi Song, Kangjie Lu, and Jinwei Shen.  Effective Covering Array Generation Using an Improved Particle Swarm Optimization.  IEEE Transactions on Reliability, 71(1):284–294, March 2022.
  * [33] László Lovász.  On the ratio of optimal integral and fractional covers.  Discrete Mathematics, 13(4):383–390, January 1975.
  * [34] Karen Meagher and Brett Stevens.  Group construction of covering arrays.  Journal of Combinatorial Designs, 13(1):70–77, 2005.  _eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1002/jcd.20035.
  * [35] Takahiro Nagamoto, Hideharu Kojima, Hiroyuki Nakagawa, and Tatsuhiro Tsuchiya.  Locating a Faulty Interaction in Pair-wise Testing.  In 2014 IEEE 20th Pacific Rim International Symposium on Dependable Computing, pages 155–156, Singapore, November 2014. IEEE.
  * [36] Peyman Nayeri, Charles J. Colbourn, and Goran Konjevod.  Randomized post-optimization of covering arrays.  European Journal of Combinatorics, 34(1):91–103, January 2013.
  * [37] Changhai Nie and Hareton Leung.  A Survey of Combinatorial Testing.  ACM Comput. Surv., 43:1–29, 2011.  Publisher: ACM.
  * [38] Kari J. Nurmela.  Upper bounds for covering arrays by tabu search.  Discrete Applied Mathematics, 138(1):143–152, March 2004.
  * [39] Sangeeta Sabharwal, Priti Bansal, and Nitish Mittal.  Construction of t-way covering arrays using genetic algorithm.  International Journal of System Assurance Engineering and Management, 8(2):264–274, June 2017.
  * [40] Kaushik Sarkar.  Covering Arrays: Algorithms and Asymptotics.  PhD Thesis, Arizona State University, 2016.
  * [41] Stephen A. Seidel, Charles J. Colbourn, and Violet R. Syrotiuk.  Robustness of Recovery in Locating Array-Based Screening Experiments.  In 2019 Spring Simulation Conference (SpringSim), pages 1–12, Tuscon, AZ, USA, April 2019. IEEE.
  * [42] Stephen A. Seidel, Michael T. Mehari, Charles J. Colbourn, Eli De Poorter, Ingrid Moerman, and Violet R. Syrotiuk.  Analysis of large-scale experimental data from wireless networks.  In IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 535–540, Honolulu, HI, USA, April 2018. IEEE.
  * [43] Stephen A. Seidel, Kaushik Sarkar, Charles J. Colbourn, and Violet R. Syrotiuk.  Separating Interaction Effects Using Locating and Detecting Arrays.  In Costas Iliopoulos, Hon Wai Leong, and Wing-Kin Sung, editors, Combinatorial Algorithms, Lecture Notes in Computer Science, pages 349–360, Cham, 2018. Springer International Publishing.
  * [44] George B. Sherwood, Sosina S. Martirosyan, and Charles J. Colbourn.  Covering arrays of higher strength from permutation vectors.  Journal of Combinatorial Designs, 14(3):202–213, 2006.
  * [45] J. Spencer.  Minimal scrambling sets of simple orders.  Acta Mathematica Academiae Scientiarum Hungaricae, 22(3):349–353, September 1971.
  * [46] John Stardom.  Metaheuristics and the search for covering and packing arrays.  PhD thesis, Simon Fraser University Burnaby, 2001.
  * [47] S. K. Stein.  Two combinatorial covering theorems.  Journal of Combinatorial Theory, Series A, 16(3):391–397, May 1974\.
  * [48] Yu Tang, Charles J. Colbourn, and Jianxing Yin.  Optimality and Constructions of Locating Arrays.  Journal of Statistical Theory and Practice, 6(1):20–29, March 2012\.  Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/15598608.2012.647484.
  * [49] Jimena Adriana Timaná-Peña, Carlos Alberto Cobos-Lozada, and Jose Torres-Jimenez.  Metaheuristic algorithms for building Covering Arrays: A review.  Revista Facultad de Ingeniería, 25(43):31–45, December 2016.  Publisher: Universidad Pedagógica y Tecnológica de Colombia.
  * [50] Jose Torres-Jimenez, Daniel Osvaldo Ramirez-Acuna, Brenda Acevedo-Juárez, and Himer Avila-George.  New upper bounds for sequence Covering Arrays using a 3-stage approach.  Expert Systems with Applications, 207:118022, November 2022.
  * [51] Jose Torres-Jimenez and Eduardo Rodriguez-Tello.  Simulated Annealing for constructing binary covering arrays of variable strength.  In IEEE Congress on Evolutionary Computation, pages 1–8, Barcelona, Spain, July 2010. IEEE.  ISSN: 1941-0026.
  * [52] Michael Wagner, Kristoffer Kleine, Dimitris E. Simos, Rick Kuhn, and Raghu Kacker.  CAGEN: A fast combinatorial test generation tool with support for constraints and higher-index arrays.  In 2020 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pages 191–200, Porto, Portugal, October 2020. IEEE.
  * [53] Robert A. Walker II and Charles J. Colbourn.  Tabu search for covering arrays using permutation vectors.  Journal of Statistical Planning and Inference, 139(1):69–80, January 2009.


# Spectral properties of edge Laplacian matrix

Shivani Chauhan  Department of Mathematics, Shiv Nadar Institution of
Eminence, Dadri, U.P, 201314<EMAIL_ADDRESS>and  A. Satyanarayana Reddy
Department of Mathematics, Shiv Nadar Institution of Eminence, Dadri, U.P,
201314<EMAIL_ADDRESS>
###### Abstract.

Let $N(X)$ be the Laplacian matrix of a directed graph obtained from the edge
adjacency matrix of a graph $X.$ In this work, we study the bipartiteness
property of the graph with the help of $N(X).$ We computed the spectrum of the
edge Laplacian matrix for the regular graphs, the complete bipartite graphs,
and the trees. Further, it is proved that given a graph $X,$ the
characteristic polynomial of $N(X)$ divides the characteristic polynomial of
$N(X^{\prime\prime}),$ where $X^{\prime\prime}$ denote the Kronecker double
cover of $X.$

2010 Mathematics Subject Classification. 05C05, 05C50, 05C76. Keywords and
phrases. Laplacian matrix, edge adjacency matrix.

##  1\. Introduction

The Laplacian matrix $\mathfrak{L}(X)$ or $\mathfrak{L}$ of a directed graph
$X$ is defined as $\mathfrak{L}(X)=\mathfrak{D}(X)-A(X)$, where $A(X)$ is the
adjacency matrix of $X$ and $\mathfrak{D}(X)$ is the diagonal matrix of the
row sums of $A(X).$ In [12, 13], Chai Wah Wu defined the algebraic
connectivity of directed graphs. It is useful in deriving synchronization
criteria for arrays of coupled dynamical systems for both constant and time-
varying coupling. In this work, we are studying the Laplacian matrix of a
special class of directed graphs, for that we first define the edge adjacency
matrix of a graph.

There are other definitions of Laplacian matrices of directed graphs (see [2,
4]). Let $X=(V(X),E(X))$ be a graph with $|V(X)|=n,\;|E(X)|=m.$ We orient the
edges of $X$ arbitrarily, label them as $e_{1},e_{2},\ldots,e_{m}$ and also
$e_{m+i}=e_{i}^{-1},\;1\leq i\leq m,$ where $e_{k}^{-1}$ denotes the edge
$e_{k}$ with the direction reversed. Then the edge adjacency matrix of $X$,
denoted by $M(X)$ or $M$ if $X$ is clear from the context, is defined as

$M_{ij}=\begin{cases}1&\mbox{if $t(e_{i})=s(e_{j})$\; and\; $s(e_{i})\neq
t(e_{j})$,}\\\ 0&\mbox{otherwise.}\end{cases}$

where $s(e_{i})$ and $t(e_{i})$ denote the starting and the terminal vertex of
$e_{i},$ respectively. For further information about the matrix $M$, one can
refer [3, 9, 10].

The edge Laplacian matrix $N(X)$ or $N$ of a graph $X$ is defined as $N=D-M$,
where $D$ is the diagonal matrix of the row sums of $M$ i.e., the $i^{th}$
diagonal entry equals to $deg(t(e_{i}))-1$, and $deg(v)$ denotes the degree of
the vertex $v.$ Recall, a graph is strongly connected if for every ordered
pair of vertices $(v,w)$, there exists a directed path from $v$ to $w.$ In
Theorem 11.10 of [10], it is proved that if $X$ is a connected graph that is
not a cycle graph and does not contain a pendant vertex, then matrix $M$ is
irreducible. Therefore the directed graph obtained from the matrix $M$ is
strongly connected, hence 0 is a simple eigenvalue of $N$. The process of
computation of matrix $N(C_{3})$ is given in Figure 1.

In the next section, we describe the structure of the matrix $N$ which is
useful to determine the bipartiteness property of the graph. Further, the
spectrum of various families of graphs is provided, in particular for regular
graphs, trees, and complete bipartite graphs. Lastly, it is proved that
$\phi_{N(X)}$ divides $\phi_{N(X^{\prime\prime})},$ where $\phi_{A}$ and
$X^{\prime\prime}$ denote the characterstic polynomial of a matrix $A$ and the
Kronecker product of a graph $X$ with $K_{2}$, respectively and $K_{n}$
denotes the complete graph on $n$ vertices. Recall, the Kronecker product
$X_{1}\times X_{2}$ of graphs $X_{1}$ and $X_{2}$ is a graph such that the
vertex set is $V(X_{1})\times V(X_{2})$, vertices $(x_{1},x_{2})$ and
$(x_{1}^{\prime},x_{2}^{\prime})$ are adjacent if $x_{1}$ is adjacent to
$x_{1}^{\prime}$ and $x_{2}$ is adjacent to $x_{2}^{\prime}.$ In particular
given a graph $X,$ $X\times K_{2}$ is called the Kronecker double cover of
$X.$ From now onwards, the edge adjacency matrix of a graph is denoted by $M$
and the diagonal matrix of its rows sums by $D.$

(a) $X$

$e_{1}$$e_{1}^{-1}$$e_{2}$$e_{2}^{-1}$$e_{3}$$e_{3}^{-1}$ (b) Oriented graph
of $X$

$e_{1}$$e_{2}$$e_{3}$$e_{1}^{-1}$$e_{2}^{-1}$$e_{3}^{-1}$ (c) Directed graph
obtained from $M(X)$

| $e_{1}$ | $e_{2}$ | $e_{3}$ | $e_{1}^{-1}$ | $e_{2}^{-1}$ | $e_{3}^{-1}$
---|---|---|---|---|---|---
$e_{1}$ | 1 | -1 | 0 | 0 | 0 | 0
$e_{2}$ | 0 | 1 | -1 | 0 | 0 | 0
$e_{3}$ | -1 | 0 | 1 | 0 | 0 | 0
$e_{1}^{-1}$ | 0 | 0 | 0 | 1 | 0 | -1
$e_{2}^{-1}$ | 0 | 0 | 0 | -1 | 1 | 0
$e_{3}^{-1}$ | 0 | 0 | 0 | 0 | -1 | 1
(d) $N(X)$

Figure 1.

##  2\. Spectrum of edge Laplacian matrix

The collection of all the eigenvalues of a matrix together with its
multiplicities is known as the spectrum of that matrix. If
$\lambda_{1}>\lambda_{2}>\ldots>\lambda_{k}$ are the distinct eigenvalues of a
matrix $A,$ then the spectrum of $A$ is defined by

$\begin{Bmatrix}\lambda_{1}&\lambda_{2}&\cdots&\lambda_{k}\\\
m_{1}&m_{2}&\cdots&m_{k}\end{Bmatrix},$

where $m_{i}$ is the algebraic multiplicity of eigenvalue $\lambda_{i}$ for
$1\leq i\leq k.$ The matrix $N$ has the following structure

(1) $N=D-M=\left[\begin{array}[]{c|c}P&Q\\\ \hline\cr R&S\end{array}\right],$

where $P,Q,R,S$ are $m\times m$ matrices. From the structure of matrix $M,$ we
have that $Q$ and $R$ are symmetric matrices. If $X$ is regular, then
$P=S^{T}$ and $N^{T}=JNJ,$ where $J=\begin{pmatrix}0&\mathbb{I}_{m}\\\
\mathbb{I}_{m}&0\end{pmatrix}$ and $\mathbb{I}_{m}$ denotes the identity
matrix of order $m$. The row and column sums of the matrix $N$ are zero for
regular graphs which implies that the cofactors of any two elements of $N$ are
equal [1, Lemma 4.2]. It is interesting to note that the sum of the blocks of
$N,$ $P+Q+R+S$ is the Laplacian matrix of $L(X)$, where $L(X)$ denotes the
line graph of $X$. As

$N=D-M=\begin{bmatrix}D_{1}&0\\\ 0&D_{2}\end{bmatrix}-\begin{bmatrix}A&B\\\
C&D\end{bmatrix},$

the sum of the blocks of $M$ is equal to $A(L(X))$ [9, p.7] and
$(D_{1}+D_{2})_{ii}=deg(t(e_{i}))+deg(t(e_{i}^{-1}))-2,$ where $1\leq i\leq
m$.

It is well known from [7] that a graph $X$ is bipartite if and only if the
Laplacian matrix and the signless Laplacian matrix of $X$ are similar. Our
next result is analogous to this.

######  Theorem 1.

A graph $X$ is bipartite if and only if $D+M$ and $D-M$ are similar, where $M$
is irreducible.

###### Proof.

Suppose that $X$ is bipartite with $m$ edges. Let
$\\{v_{1},v_{2},\ldots,v_{m}\\}$ and
$\\{v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{n}^{\prime}\\}$ be the vertex
bipartition of $X.$ Choose an orientation in $X$ in such a way that
$e_{i}^{\prime}s$ are the directed edges from $v_{i}$ to $v_{j}^{\prime}$ for
all $1\leq i\leq m,1\leq j\leq n$, then $M$ can be expressed in the following
form

(2) $M=\left[\begin{array}[]{c|c}0&B\\\ \hline\cr C&0\end{array}\right].$

It is simple to check that $P^{T}(D+M)P=D-M$, where
$P=\begin{bmatrix}\mathbb{I}_{m}&0\\\ 0&-\mathbb{I}_{m}\end{bmatrix}.$

Conversely, suppose that $D+M$ and $D-M$ are similar, where $M$ is
irreducible. Clearly, $0$ is an eigenvalue of $D+M$. Let
$x=(x_{1},x_{2},\ldots,x_{2m})$ be the eigenvector corresponding to the
eigenvalue $0$ of $D+M$. Choose $x_{i}$ to be the maximum absolute entry of
$x.$ As $((D+M)x)_{i}=0,$ we have $\sum_{j=1,i\neq
j}^{2m}m_{ij}x_{j}+d_{ii}x_{i}=0$. We obtain $d_{ii}x_{i}=-\sum x_{j},$ where
the summation is over the edges to which $e_{i}$ is feeding and these edges
are $d_{ii}$ in number. By the maximality of $x_{i},$ we have $x_{i}=-x_{j}$
for all edges into which $e_{i}$ is feeding. Now, we explain the construction
of the vertex partition. We put the vertex $e_{i}$ in one partition, say
$V_{1}$, and the vertices $e_{j}^{\prime}s$ into which $e_{i}$ is feeding in
the partition $V_{2}$ and the edges are directed from $e_{i}$ to
$e_{j}^{\prime}s.$ Again we choose the maximum absolute entry of $x$ and
continue the same process. This shows $M$ has the structure given in (2),
hence $X$ is bipartite. ∎

We shall now present the spectrum for several graph families. The spectrum of
a regular graph can be easily obtained from Theorem 2.2 in [6]. Let $X$ be a
$k$-regular graph on $n$ vertices, then the eigenvalues of $N$ are

$k-1\pm
1,k-1-\left(\frac{\lambda_{i}\pm\sqrt{\lambda_{i}^{2}-4(k-1)}}{2}\right),(i=1,\ldots,n)$

where $\lambda_{i}\in spec(A(X))$ and $k-1\pm 1$ each have multiplicity $m-n.$
Later, we computed the eigenvalues of $N$ for trees and complete bipartite
graphs in Theorems 3 and 5, respectively. In Table 1, the spectrum of $N(X)$
is given, where $X$ is a tree on $6$ vertices. We state Theorem 2 which is
required in the proof of Theorem 3.

$X$ | Spectrum of $N(X)$
---|---
| $\begin{Bmatrix}0&1\\\ 2&8\end{Bmatrix}$
| $\begin{Bmatrix}0&1&2\\\ 3&4&3\end{Bmatrix}$
| $\begin{Bmatrix}0&1&2\\\ 3&4&3\end{Bmatrix}$
| $\begin{Bmatrix}0&1&3\\\ 4&2&4\end{Bmatrix}$
| $\begin{Bmatrix}0&2\\\ 4&6\end{Bmatrix}$
| $\begin{Bmatrix}0&4\\\ 5&5\end{Bmatrix}$

Table 1.

######  Theorem 2.

[11, Theorem 3.2] Let $M$ be the edge adjacency matrix of a graph $X.$ Then
$M$ is a nilpotent matrix if and only if $X$ is a forest.

######  Theorem 3.

Let $X$ be a connected graph. Then the eigenvalues of $N$ are the same as the
eigenvalues of $D$ if and only if $X$ is a tree.

###### Proof.

Suppose that $X$ is a tree on $m$ edges. Let
$\phi_{D}(\lambda)=\lambda^{2m}+d_{1}\lambda^{2m-1}+d_{2}\lambda^{2m-2}+\cdots+d_{2m-1}\lambda+d_{2m}$
and
$\phi_{N}(\lambda)=\lambda^{2m}+n_{1}\lambda^{2m-1}+n_{2}\lambda^{2m-2}+\cdots+n_{2m-1}\lambda+n_{2m}$
be the characterstic polynomial of matrix $D$ and $N,$ respectively. We want
to show that $d_{i}=n_{i}$, where $1\leq i\leq 2m.$ In order to prove the
claim, we use the fact that the sum of the products of the eigenvalues of a
matrix $A$ taken $k$ at a time equals the sum of the $k\times k$ principal
minors of $A$ [8, p.53]. It is simple to observe that $d_{1}=n_{1}.$ The
$2\times 2$ principal submatrix of $N$ has the following structure,

$B_{2}=\begin{pmatrix}d_{ii}&-m_{ij}\\\ -m_{ji}&d_{jj}\end{pmatrix},$

where $m_{ij}$ denotes the $ij^{th}$ entry of $M$. By the definition of $M$,
$det(B_{2})=d_{ii}d_{jj}$, therefore $d_{2}=n_{2}$. Let $B_{k}$ denote the
$k\times k$ principal submatrix of $N$, whose rows and columns are indexed by
$i_{1}>i_{2}>\ldots>i_{k}.$ It is well known that

(3) $det(A)=\sum_{\sigma\in S_{n}}sgn(\sigma)\prod_{i=1}^{n}a_{i\sigma(i)},$

where the summation is over all permutation $\\{1,2,\ldots,n\\}$. As $X$ is a
tree, the directed graph obtained from the matrix $M$ has no cycles. By (3),
$det(B_{k})=d_{i_{1}i_{1}}d_{i_{2}i_{2}}\ldots d_{i_{k}i_{k}}$, which implies
$d_{k}=n_{k}$.

Conversely, suppose that $\phi_{D}(\lambda)=\phi_{N}(\lambda)$. Let
$\phi_{M}(\lambda)=\lambda^{2m}+m_{1}\lambda^{2m-1}+m_{2}\lambda^{2m-2}+\ldots+m_{2m-1}\lambda+m_{2m}$.
We want to show that $m_{i}=0\;\forall\;1\leq i\leq 2m.$ The result is proved
using strong induction. Clearly, $m_{1}=m_{2}=0$. Assume that $m_{i}=0\forall
1\leq i\leq k$. As $m_{k+1}=$ sum of $(k+1)\times(k+1)$ principal minors of
$M$, by (3)

(4) $m_{k+1}=\sum_{i_{1}<i_{2}<\ldots<i_{k+1}}\sum_{\sigma\in
S_{k+1}}sgn(\sigma)\prod_{\ell=1}^{k+1}m_{i_{\ell}\sigma(i_{\ell})},$

where $1\leq i_{1},i_{2},\ldots,i_{k+1}\leq 2m.$ In the inner summation of
(4), all the entries corresponding to permutations which are not a cycle of
length $k+1$ are zero, by induction hypothesis. Hence, we are left with the
following expression

$m_{k+1}=\sum_{i_{1}<i_{2}<\ldots<i_{k+1}}\sum_{\sigma\in
C\cup\\{e\\}}(-1)^{k+1}m_{i_{1}\sigma(i_{1})}m_{i_{2}\sigma(i_{2})}\ldots
m_{i_{k+1}\sigma(i_{k+1})},$

where $C$ denotes the cycle of length $k+1$. As sum of $k\times k$ principal
minors of $N$ is equal to the sum of $k\times k$ principal minors of $D$, we
deduce the following expression

$\sum_{i_{1}<i_{2}<\ldots<i_{k+1}}\left(\prod_{j=1}^{k+1}n_{i_{j}i_{j}}+\sum_{\sigma\in
S_{k+1},\sigma\neq\\{e\\}}sgn(\sigma)\prod_{\ell=1}^{k+1}n_{i_{\ell}\sigma(i_{\ell})}\right)=\sum_{i_{1}<i_{2}<\ldots<i_{k+1}}\prod_{j=1}^{k+1}n_{i_{j}i_{j}}.$

By above Equation we obtain

(5) $\sum_{i_{1}<i_{2}<\ldots<i_{k+1}}\sum_{\sigma\in
S_{k+1},\sigma\neq\\{e\\}}sgn(\sigma)\prod_{\ell=1}^{k+1}n_{i_{\ell}\sigma(i_{\ell})}=0.$

As $N=D-M$,
$n_{i_{\ell}\sigma(i_{\ell})}=\begin{cases}d_{i_{\ell}i_{\ell}}&\mbox{if
$\sigma(i_{\ell})=i_{\ell}$}\\\ -m_{i_{\ell}\sigma(i_{\ell})}&\mbox{if
$\sigma(i_{\ell})\neq i_{\ell}$}\end{cases}$. In the inner summation of (5),
all the terms in the permutations except those terms corresponding to full
cycle permutation are zero, by induction hypothesis. Equation (5) reduces to

$\sum_{i_{1}<i_{2}<\cdots<i_{k+1}}\sum_{\sigma\in
C,\sigma\neq\\{e\\}}(-1)^{k+1}(-1)^{k+1}m_{i_{1}\sigma(i_{1})}m_{i_{2}\sigma(i_{2})}\cdots
m_{i_{k+1}\sigma(i_{k+1})}=0.$

Hence $m_{k+1}=0$ and by Theorem 2, the proof is complete. ∎

######  Corollary 4.

Let $X$ be a tree on the $n$ vertices and $(d_{1},d_{2},\ldots,d_{n})$ be the
degree sequence of $X$. Then $d_{i}-1$ is an eigenvalue of $N$ with
multiplicity $d_{i}$, where $1\leq i\leq n$.

We now define the Kronecker product of the matrices and the Schur complement
as it is required to prove our next result. The Kronecker product of the
matrices $A=[a_{ij}]$ and $B$ is defined as the partitioned matrix $[a_{ij}B]$
and is denoted by $A\otimes B.$ Let $H$ be an $n\times n$ matrix partitioned
as $H=\begin{bmatrix}A_{11}&A_{12}\\\ A_{21}&A_{22}\end{bmatrix},$ where
$A_{11}$ and $A_{22}$ are square matrices. If $A_{11}$ is non-singular, then
the Schur complement of $A_{11}$ in $H$ is defined to be the matrix
$A_{22}-A_{21}A_{11}^{-1}A_{12}.$ For Schur complement, we have
$det(H)=det(A_{11})det(A_{22}-A_{21}A_{11}^{-1}A_{12})$ and if
$A_{11}A_{12}=A_{12}A_{11}$, then $det(H)=det(A_{22}A_{11}-A_{21}A_{12})$.
Similarly if $A_{22}$ is non-singular, then the Schur complement of $A_{22}$
in $H$ is defined to be the matrix $A_{11}-A_{12}A_{22}^{-1}A_{21}$ and we can
obtain $det(H)=det(A_{22})det(A_{11}-A_{12}A_{22}^{-1}A_{21})$. If
$A_{21}A_{22}=A_{22}A_{21}$, then $det(H)=det(A_{11}A_{22}-A_{12}A_{21})$.

######  Theorem 5.

Let $X=K_{p,q}$ be the complete bipartite graph on the $n$ vertices. Then the
spectrum of $N(K_{p,q})$ is equal to

$\begin{Bmatrix}0&u&\frac{u\pm\sqrt{v+4}}{2}&\frac{u\pm\sqrt{v+4(1-q)}}{2}&\frac{u\pm\sqrt{v+4(1-p)}}{2}\\\
1&1&(q-1)(p-1)&p-1&q-1\end{Bmatrix},$

where $u=p+q-2$ and $v=(p-q)^{2}$.

###### Proof.

Let
$V(K_{p,q})=\\{v_{1},v_{2},\ldots,v_{p}\\}\cup\\{v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{q}^{\prime}\\}$
be a bipartition of $X$. Choosing an orientation that is defined in the proof
of Theorem 1, then $N(K_{p,q})$ can be written in the following form

$N(K_{p,q})=\begin{bmatrix}(p-1)(U)&\mathbb{J}_{p}\otimes(-\mathbb{I}_{q})+U\\\
V&(q-1)(U)\end{bmatrix},$

where
$U=\mathbb{I}_{p}\otimes\mathbb{I}_{q},V=\mathbb{I}_{p}\otimes(-A(K_{q})),$
and $\mathbb{J}_{n}$ denotes the matrix of order $n$ with all entries one. The
characterstic polynomial of $N(X)$ is

$\phi_{N}(x)=\begin{vmatrix}(p-1-x)(U)&\mathbb{J}_{p}\otimes(-\mathbb{I}_{q})+U\\\
V&(q-1-x)(U)\end{vmatrix}=0.$

A simple check shows that

$V((q-1-x)(U))=((q-1-x)(U))V=\mathbb{I}_{p}\otimes((x-q+1)A(K_{q})).$

By the Schur complement formula, we obtain the following Equation

$\begin{split}\phi_{N}(x)&=det(((p-1-x)U)((q-1-x)U)-(\mathbb{J}_{p}\otimes(-\mathbb{I}_{q})+U)V)\\\
&=det((p-1-x)(q-1-x)(U)-\mathbb{J}_{p}\otimes A(K_{q})-V).\\\ \end{split}$

For the sake of convenience, assume that

$S^{\prime}=(p-1-x)(q-1-x)(U)-\mathbb{J}_{p}\otimes A(K_{q})-V,$
$T^{\prime}=(1-p)A(K_{q})+(p-x-1)(q-x-1)\mathbb{I}_{q},U^{\prime}=A(K_{q})+(p-x-1)(q-x-1)\mathbb{I}_{q}.$

Let $\lambda$ be an eigenvalue of $T^{\prime}$ with its corresponding
eigenvector $v$, then $S^{\prime}V=\lambda V,$ where $V$ is a $p$ dimensional
vector $(v,v,\ldots,v)^{T}$.
Let $\lambda^{\prime}$ be an eigenvalue of $U^{\prime}$ with corresponding
eigenvector $v^{\prime}$. By a straightforward calculation, one can see that
the following linearly independent vectors

$\\{(v^{\prime},-v^{\prime},0,0,\ldots,0)^{T},(v^{\prime},0,-v^{\prime},0,\ldots,0)^{T},\ldots,(v^{\prime},0,0,0,\ldots,-v^{\prime})^{T}\\}$

are the eigenvectors of $S^{\prime}$. As the sum of the multiplicities of the
obtained eigenvalues equals the number of vertices in the directed graph
obtained from $M$. Therefore,
$\phi_{N}(x)=(det(U^{\prime}))^{p-1}det(T^{\prime}).$ As
$A(K_{q})=\mathbb{J}_{q}-\mathbb{I}_{q}$ and the eigenvalues of
$\mathbb{J}_{q}$ are $0$ and $q$ with multiplicity $q-1$ and $1$,
respectively. From here the eigenvalues of $N$ can be deduced. ∎

The following result is about the eigenvalues of symmetric block matrices that
will be used to prove the next result.

######  Theorem 6.

[5] Let $H=\begin{bmatrix}A^{\prime}&B^{\prime}\\\
B^{\prime}&A^{\prime}\end{bmatrix}$ be a symmetric $2\times 2$ block matrix,
where $A^{\prime}$ and $B^{\prime}$ are square matrices of same order. Then
the spectrum of $H$ is the union of the spectra of $A^{\prime}+B^{\prime}$ and
$A^{\prime}-B^{\prime}$.

######  Theorem 7.

Let $X$ be a connected graph, then $\phi_{N(X)}$ divides
$\phi_{N(X^{\prime\prime})}$.

###### Proof.

We know that $N(X)=D(X)-M(X)=\begin{pmatrix}D_{1}-A&-B\\\
-C&D_{2}-D\end{pmatrix}$. From the proof of Theorem 4.2 in Horton [9],
$M(X^{\prime\prime})=\begin{pmatrix}0&MJ\\\ JM&0\end{pmatrix},$ therefore

$N(X^{\prime\prime})=D(X^{\prime\prime})-M(X^{\prime\prime})=\begin{pmatrix}D_{1}&0&-B&-A\\\
0&D_{2}&-D&-C\\\ -C&-D&D_{2}&0\\\ -A&-B&0&D_{1}\end{pmatrix}.$

Note that $P^{T}N(X^{\prime\prime})P=\begin{pmatrix}D_{1}&0&-A&-B\\\
0&D_{2}&-C&-D\\\ -A&-B&D_{1}&0\\\ -C&-D&0&D_{2}\end{pmatrix},$ where
$P=\begin{pmatrix}I_{m}&0&0&0\\\ 0&I_{m}&0&0\\\ 0&0&0&I_{m}\\\
0&0&I_{m}&0\end{pmatrix}.$ The result follows from Theorem 6. ∎

##  3\. Acknowledgement

The authors would like to thank the handling editor and the anonymous
reviewers for their careful reading of the manuscript.

## References

  * [1] R.B. Bapat, Graphs and matrices, volume 27, Springer, (2010).
  * [2] R.B. Bapat, J. W. Grossman and D. M. Kulkarni, Generalized matrix tree theorem for mixed graphs, Linear and Multilinear Algebra, 46(40): 299-312, (1999).
  * [3] S. Chauhan and A.S. Reddy, On the double covers of a line graph, arXiv preprint arXiv:2202.04756v2, (2023).
  * [4] F. Chung, Laplacians and the Cheeger inequality for directed graphs, Annals of Combinatorics, 9(1):1-19, (2005).
  * [5] P.J. Davis, Circulant matrices, American Mathematical Soc., (2013).
  * [6] C. Glover and M. Kempton, Some spectral properties of the non-backtracking matrix of a graph, Linear Algebra and its Applications, 618:37-57, (2021).
  * [7] R. Grone, R. Merris and V. Sunder, The Laplacian spectrum of a graph, SIAM Journal on matrix analysis and applications, 11(2):218-238, (1990).
  * [8] R.A. Horn and C. R. Johnson, Matrix analysis, Cambridge university press, (2012).
  * [9] M.D Horton, Ihara zeta functions of irregular graphs, University of California, San Diego, (2006).
  * [10] A. Terras, Zeta functions of graphs: a stroll through the garden, volume 128, Cambridge University Press, (2010).
  * [11] L. Torres, Non-backtracking spectrum: Unitary eigenvalues and diagonalizability, arXiv preprint arXiv:2007.13611, (2020).
  * [12] C.W. Wu, Algebraic connectivity of directed graphs, Linear and multilinear algebra, 53(3):203-223, (2005).
  * [13] C.W. Wu, On Rayleigh–Ritz ratios of a generalized Laplacian matrix of directed graphs, Linear algebra and its applications, 402:207-227, (2005).