# Improved Dynamic Algorithms for Longest Increasing Subsequence

Tomasz Kociumaka
University of California, Berkeley
<EMAIL_ADDRESS>Saeed Seddighin111Supported in part by an Adobe
research award and a Google research gift.
Toyota Technological Institute at Chicago
<EMAIL_ADDRESS>
###### Abstract

We study dynamic algorithms for the longest increasing subsequence (LIS)
problem. A dynamic LIS algorithm maintains a sequence subject to operations of
the following form arriving one by one: (i) insert an element, (ii) delete an
element, or (iii) substitute an element for another. After performing each
operation, the algorithm must report the length of the longest increasing
subsequence of the current sequence.

Our main contribution is the first exact dynamic LIS algorithm with sublinear
update time. More precisely, we present a randomized algorithm that performs
each operation in time $\widetilde{O}(n^{2/3})$ and after each update, reports
the answer to the LIS problem correctly with high probability. We use several
novel techniques and observations for this algorithm that may find their
applications in future work.

In the second part of the paper, we study approximate dynamic LIS algorithms,
which are allowed to underestimate the solution size within a bounded
multiplicative factor. In this setting, we give a deterministic algorithm with
update time $O(n^{o(1)})$ and approximation factor $1-o(1)$. This result
substantially improves upon the previous work of Mitzenmacher and Seddighin
(STOC’20) that presents an $\Omega(\epsilon^{O(1/\epsilon)})$-approximation
algorithm with update time $\widetilde{O}(n^{\epsilon})$ for any constant
$\epsilon>0$.

##  1 Introduction

Longest increasing subsequence (LIS) is a very old and classic problem in
computer science. In this problem, a sequence $a=\langle
a_{1},a_{2},\ldots,a_{n}\rangle$ of size $n$ is given as input and the LIS of
the sequence is defined as the largest subset of the elements whose values are
strictly increasing in the order of their indices. LIS can also be thought of
as a special case of the longest common subsequence (LCS) problem where the
two inputs are permutations. Both problems date back to the 1950s and have
been subject to a plethora of research [Fre75, Ram97, GJKK07, GG07, EKK+98,
DGL+99, Fis01, ACCL04] especially in recent years [HSSS19, RSSS19, MS20,
MS21].

In this work, we focus on exact and approximation algorithms in the dynamic
setting, where at each step, the sequence can be updated by inserting,
deleting, or substituting an element. The goal is to maintain the size of the
longest increasing subsequence. Many problems have been studied in dynamic
settings; see e.g. [HKNS15, NS17, GKK+18, AOSS18, AOSS19, CCP13, LOP+15,
BDH+19, NSW17]. In general, in a dynamic setting, the goal is to develop an
algorithm which updates the solution efficiently given incremental changes to
the input. In the context of graph algorithms [NS17, NSW17, LOP+15, AOSS18,
AOSS19, BDH+19], such changes are usually modeled by edge insertion or
deletion. For string problems, changes are typically modeled with character
insertion, deletion, and substitution [CCP13, CGP20, CKM20], as we consider
here.

Our work is closely related to two previous works on dynamic LIS. (In what
follows, when we refer to a solution, we typically refer to the size of the
LIS, but also the corresponding increasing subsequence can be found in time
proportional to its size.) Mitzenmacher and Seddighin [MS20] give an
$\Omega(\epsilon^{O(1/\epsilon)})$-approximation algorithm for dynamic LIS
whose update time is bounded by $\widetilde{O}(n^{\epsilon})$ for any constant
$\epsilon>0$. They also present a $(1+\epsilon)$-approximation algorithm for
the dynamic variant of distance to monotonicity which is the dual of LIS.
Their solution for distance to monotonicity requires polylogarithmic update
time. Chen, Chu, and Pinkser [CCP13] also study dynamic LIS and give an exact
solution whose update time depends on the size of the solution. More
precisely, if we denote the solution size by $\mathsf{opt}$, then their
algorithm requires update time $O(\mathsf{opt}\log\frac{n}{\mathsf{opt}})$.
Notice that $\mathsf{opt}$ can be as large as $\Omega(n)$ and therefore their
update time is $\Theta(n)$ in the worst case.

Approximation factor | Update time | Reference
---|---|---
$1-\epsilon$ | $\widetilde{O}(\sqrt{n})$ | [MS20]
$\Omega(\epsilon^{O(1/\epsilon)})$ | $\widetilde{O}(n^{\epsilon})$ | [MS20]
exact | $O(\mathsf{opt}\log\frac{n}{\mathsf{opt}})$ | [CCP13]
exact | $O(n^{2/3}\log^{4}n)$ | Theorem 7
$1-o(1)$ | $O(n^{o(1)})$ | Theorem 35
Table 1: The results of this paper along with previous work on dynamic LIS.
Here, $\mathsf{opt}$ denotes the size of the longest increasing subsequence.
In the algorithm of Theorem 35, if we denote the approximation factor by
$1-\epsilon$, the update time will be bounded by $O((\log n/\epsilon)^{O((\log
n)^{2/3}/\epsilon)})$.

We provide the first exact algorithm for LIS with sublinear update time
regardless of the solution size. In other words, we give an algorithm that
reports the correct value of the size of the longest increasing subsequence
with high probability (at least $1-n^{-10}$) and, after each operation,
updates the solution in time $O(n^{2/3}\log^{4}n)$. In addition to this, we
also present a $(1-o(1))$-approximation algorithm for dynamic LIS that updates
the solution in time $O(n^{o(1)})$. Our method substantially advances the
techniques of [MS20] and significantly improves their main results.

###  1.1 Parallel and Independent Work

Parallel to and independent of this work, Gawrychowski and Janczewski [GJ20]
present a different $1-o(1)$ approximation algorithm for dynamic LIS that
updates the solution in subpolynomial time. While the approximation factors of
both algorithms are $1-o(1)$, their algorithm is faster: it achieves update
time $O(\epsilon^{-5}\log^{11}n)$ while maintaining a
$(1-\epsilon)$-approximation of LIS. To derive a solution, both approximation
algorithms generalize the dynamic LIS problem; our algorithm is able to answer
more general queries, though. We also remark that [GJ20] does not claim any
progress towards obtaining an exact sublinear-time solution for dynamic LIS
(which is our main result).

###  1.2 Related Work

In addition to previous dynamic algorithms for LIS [MS20, CCP13], this problem
has received significant attention in other areas such as property testing
[EKK+98, DGL+99, Fis01, ACCL04], streaming [GJKK07, GG07], and massively
parallel computation (MPC) [IMS17], as well as in the standard algorithmic
setting [Fre75, Ram97, RSSS19, SS10, MS21].

The classic patience sorting solution for LIS utilizes dynamic programming and
binary search to solve LIS exactly in time $O(n\log n)$. Matching lower bounds
($\Omega(n\log n)$) are known for comparison-based algorithms [Fre75] and
solutions based on algebraic decision trees [Ram97]. For approximation
algorithms, for any $\epsilon>0$, a multiplicative $\Omega(n^{-\epsilon})$
approximate solution can be determined in truly sublinear time222Truly
sublinear stands for $O(n^{1-\Omega(1)})$. via random sampling333For an
$\Omega(n^{-\epsilon})$-approximation algorithm, one can sample
$O(n^{1-\epsilon})$ elements from the sequence and report the LIS of those
samples.. Surprisingly, not much is known that improves upon this algorithm
generally, although when $n/\mathsf{LIS}(a)$ is subpolynomial in $n$, we can
obtain better approximation guarantees for LIS [SS10, RSSS19, MS21].

From a complexity point of view, unconditional lower bounds apply to
sublinear-time algorithms for LIS. For instance, any algorithm that obtains a
$1/f(n)$-approximate solution for LIS has to make at least $n/(f(n)+1)$ value
queries444A value query provides an $i$ as input and asks for the value of
$a_{i}$. to the elements of $a$ to distinguish the case that $a$ is decreasing
from the case that $a$ has an increasing subsequence of length at least
$f(n)+1$. Thus a subpolynomial-factor approximation algorithm for LIS in truly
sublinear time is not possible in general. In contrast, positive results are
given in previous work for a special case in which the solution size is at
least $\lambda n$ for large enough $0<\lambda\leq 1$. (Known query complexity
lower bounds do not apply to this setting.) Saks and Seshadhri [SS10] present
a $(1-\epsilon)$-approximation algorithm for LIS in this case. The runtime of
their algorithm is sublinear as long as $\lambda>\log\log n/\log n$. Moreover,
Rubinstein, Seddighin, Song, and Sun [RSSS19] give an
$\Omega(\lambda^{3})$-approximation algorithm for this case in time
$\widetilde{O}(\sqrt{n}/\lambda^{7})$. Very recently, Mitzenmacher and
Seddighin [MS21] improve the approximation factor to
$\Omega(\lambda^{\epsilon})$ for any constant $\epsilon>0$ while keeping the
runtime truly sublinear.

From a technical standpoint, our approximation algorithm is related to the
recent results of [MS20] and [MS21] that approximate LIS in the dynamic and
standard settings, respectively. Both these works use the grid packing
technique for LIS to design their algorithms. We generalize this notion and
prove that the generalized grid packing gives improved dynamic algorithms for
LIS.

###  1.3 Preliminaries

LIS is defined on a sequence of numbers. We assume for simplicity that all of
the numbers are distinct and positive integers. In this problem, the goal is
to find the length of the largest subsequence of elements such that their
values increase according to their indices. We denote the size of the sequence
by $n$ and use $a_{1},\ldots,a_{n}$ to denote the sequence elements. We also
give an alternative definition for the problem which represents the input as
$n$ points on the 2D plane. In this representation, we have $n$ points on the
plane with distinct coordinates. Similarly, we assume for simplicity that all
the coordinates are positive integers. For any subset of points, its LIS is
defined as the largest number of points such that if we sort them based on
their $x$ or $y$ coordinates, we obtain the same ordering.

We adapt the setting of [MS20] for the dynamic LIS problem. Initially, the
input sequence is empty ($|a|=0$). At each step, an element can either be
inserted at an arbitrary position of the sequence or removed from an arbitrary
position of the sequence. (Element substitution can also be implemented with
the previous two operations, so we consider only insertions and deletions.)

We now define the operations more formally. Each insertion operation is of the
form “insert $(i,x)$” where $i$ is an integer between $1$ and the length of
the current sequence plus one. The index $i$ specifies the position of element
$x$. After this operation, all the elements whose previous index was at least
$i$ will be shifted to the right. Similarly, an operation “delete $(i)$”
removes the $i$’th element. Likewise, all the elements whose previous index
was at least $i$ will be shifted to the left. As discussed in previous work
[MS20], one can use a balanced tree data structure that provides access to any
element of the sequence in time $O(\log n)$. Thus, in the analysis of our time
bounds for dynamic LIS, we consider an additional multiplicative $O(\log n)$
overhead for using this data structure and assume that random access is
provided to any element.

To simplify the explanations, we often use the notation $\widetilde{O}$ that
hides the logarithmic factors. When other parameters such as $\epsilon$ or
$\kappa$ are involved, we may use $\widetilde{O}_{\epsilon}$ or
$\widetilde{O}_{\kappa}$ notations that also hide factors that only depend on
$\epsilon$ or $\kappa$. Similarly, $\widetilde{O}_{\epsilon,\kappa}$ hides all
the factors that depend on $\epsilon$, $\kappa$, or (at most polynomially) on
$\log n$.

##  2 Our Results and Techniques

In this section, we present our results and techniques. Our main contribution
is a dynamic algorithm for LIS that maintains an exact solution with update
time $\widetilde{O}(n^{2/3})$. We explain the high-level ideas behind this
algorithm in Section 2.1. We then proceed by bringing the ideas behind our
$(1-o(1))$-approximation algorithm in Section 2.2. For both our dynamic
algorithms, we use the notion of block-based algorithms [MS20] to simplify the
exposition. This enables us to include preprocessing steps which may violate
the worst-case update times. Yet, a block-based algorithm can be turned into a
dynamic algorithm whose worst-case update time is asymptotically equal to the
block-based algorithm’s amortized update time. More precisely, a block-based
algorithm starts with an array $a$ of size $n$. It is allowed to preprocess
the array in time $f(n)$. After the preprocessing step, the algorithm is
required to execute $g(n)$ operations, each in worst-case time $h(n)$. After
$g(n)$ operations, the block-based algorithm terminates. It follows from
[MS20] that such an algorithm can be used to design a dynamic algorithm for
LIS with worst-case update time $O(f(n)/g(n)+h(n))$.

###  2.1 An Exact Algorithm with Sublinear Update Time

Our main result is an exact dynamic algorithm for LIS with sublinear update
time. For this algorithm, we use several combinatorial techniques which we
explain in the following. The first idea is a randomized coloring argument
which lets us decompose the problem into smaller subproblems. Recall that the
algorithm of Chen, Chu, and Pinsker [CCP13] provides the exact LIS value with
update time $O(\mathsf{opt}\log\frac{n}{\mathsf{opt}})$, where $\mathsf{opt}$
is the solution size. Thus, as long as $\mathsf{opt}$ is sublinear in $n$,
their algorithm updates the solution in sublinear time. Intuitively, this
signals that the real difficulty of the problem is for the case where the LIS
is very large, namely, of size $\widetilde{\Omega}(n)$.

We define $b_{i}$ as the size of the longest increasing subsequence ending at
element $a_{i}$ and divide the sequence into disjoint layers. More precisely,
let each layer $L_{i}=\\{a_{j}\mid b_{j}=i\\}$ be the set of elements whose
corresponding $b_{j}$ is equal to $i$. Indeed, the number of distinct layers
is equal to the size of the solution and therefore, when the solution size is
large, we expect that the size of the layers is small on average. As an
example, if the LIS of the sequence is of size $\Omega(n)$, then we expect the
average size of the layers to be $O(1)$. The following observation enables us
to decompose the LIS problem into smaller subproblems that can be updated
independently: Let $\mathsf{opt}$ be the number of layers for a sequence. If,
for some integer $t$, we color $t$ layers of the sequence uniformly at random
and perform $\mathsf{opt}/(10t)$ arbitrary operations on the sequence, with
probability at least $1/2$ there exists a longest increasing subsequence in
the new sequence that has exactly $t$ colored elements.

A formal proof for the above claim is given in Section 3. Since the element
values are decreasing in each layer of the original sequence, no layer can
contribute more than one element to any increasing subsequence. Moreover,
since the solution size for the original sequence is $\mathsf{opt}$, after
$\mathsf{opt}/(10t)$ operations, the size of the LIS changes by at most an
additive $\mathsf{opt}/(10t)$ term. Therefore, if we fix a longest increasing
subsequence in the new array (after all the operations are performed) and
denote its size by $\mathsf{opt}^{\prime}$, at least
$\mathsf{opt}-\mathsf{opt}/(10t)$ layers of the original sequence contribute
to $\mathsf{opt}^{\prime}$. Since we color $t$ layers uniformly at random,
this proves that, with probability at least $1/2$, all of the colored layers
contribute to $\mathsf{opt}^{\prime}$.

Let us go back to our previous discussion. In a block-based algorithm, we can
in time $O(n\log n)$ construct the layers and sample $t$ layers uniformly at
random. For the next $g(n)=\mathsf{opt}/(10t)$ operations, we can be sure that
with probability at least $1/2$ we have a longest increasing subsequence that
goes through all sampled layers. For now, we ignore the bad event and assume
for simplicity that this property always holds. Thus, we only need to keep
partial solutions between consecutive sampled layers. Since our aim is to
design a dynamic algorithm for the case that the size of the longest
increasing subsequence is large, we expect that the layer sizes are small.
Hence, assume that for every pair of elements $a_{i}$ and $a_{j}$ that belong
to two consecutive sampled layers we are given the size of the longest
increasing subsequence starting from $a_{i}$ and ending at $a_{j}$, and for
every element of the first sampled layer we have the size of the longest
increasing subsequence ending at that element. Similarly, assume that for each
element of the last sampled layer, the size of the longest increasing
subsequence starting from that element is available. It follows that based on
this information, we can recover the LIS of the whole sequence (ignoring the
bad event). In the extreme case that the solution size $\mathsf{opt}$ is
$\Omega(n)$, we expect the layer sizes to be $O(1)$ on average, which makes
the total size of the information to be stored small.

The benefit of the above approach is obvious for the dynamic setting: If we
only care about local solutions between consecutive sampled layers, whenever
an operation is performed, we only need to update the local solutions. For
this purpose, we only consider elements located between the two consecutive
sampled layers. We remark that the positions of such elements in the sequence
does not necessarily form an interval. On average, the expected number of such
elements is $O(n/t)$. We bring an example to clarify the advantage of this
approach: Assume that the LIS of the original sequence is equal to $\Omega(n)$
and the size of each layer is bounded by $O(1)$. If we set $t=\sqrt{n}$ and
sample $t$ layers uniformly at random, we expect to have a solution that goes
through all the sampled layers with constant probability for up to
$\sqrt{n}/10$ steps. Thus, we set $g(n)=\sqrt{n}/10$ and assume that our
block-based algorithm is only responsible for performing $g(n)$ operations.
For simplicity, we ignore the bad event that a solution may not go through all
the sampled layers. Since the size of each layer is $O(1)$, every time an
operation arrives, we need to update the solution for at most $O(1)$ pairs of
elements, and this can be done in time $\widetilde{O}(\sqrt{n})$ since with
high probability there are at most $\widetilde{O}(\sqrt{n})$ layers between
two consecutive sampled layers (each having $O(1)$ elements). Thus, the update
time is $\widetilde{O}(\sqrt{n})$ and once the solutions between consecutive
sampled layers are provided, we can find the longest increasing subsequence of
the entire sequence in time $\widetilde{O}(\sqrt{n})$. Therefore, with
preprocessing time $f(n)=\widetilde{O}(n)$ and $g(n)=\Omega(\sqrt{n})$, we can
update the solution in time $h(n)=\widetilde{O}(\sqrt{n})$, which leads to a
dynamic algorithm with update time $\widetilde{O}(\sqrt{n})$.

$\frac{n}{2\log n}$$\frac{n}{4\log n}$$\frac{n}{8\log
n}$$\dotsc$$\dotsc$$\frac{n}{4\log n}$$\frac{n}{8\log n}$ Figure 1: The sizes
of the layers in an example are shown in the figure. The middle layer has the
largest size and the sizes decrease exponentially as the layers move to the
sides.

Roughly speaking, if we only aim to obtain a dynamic algorithm with sublinear
update time, the assumption that the solution size is $\widetilde{\Omega}(n)$
does not overly simplify the problem since otherwise we can use the algorithm
of Chen, Chu, and Pinsker [CCP13] whose update time is sublinear in that case.
The probability $1/2$ that a solution may fail to go through all the sampled
layers (failure probability) can be conveniently reduced to $1-n^{-\Omega(1)}$
via standard techniques at the price of an $O(\log n)$ multiplicative overhead
to the runtimes. However, one of the assumptions above does, in fact,
oversimplify the problem and may give rise to fundamental issues in general.
Even if we assume the solution size is $\widetilde{\Omega}(n)$, we can only
guarantee that the size of the layers is small on average and not in the worst
case. To further clarify this issue, consider the example given in Figure 1.

The example of Figure 1 shows why the above idea alone does not provide a
sublinear-time algorithm. Although the size of the LIS is
$\widetilde{\Omega}(n)$ and thus the average layer size is $\widetilde{O}(1)$,
the two sampled layers that sandwich the middle layer do not yield an easier
subproblem. Either the size of one of the sampled layers is large or the
number of layers included between them is large. More precisely, the size of
the larger sampled layer multiplied by the number of layers between them is
$\widetilde{\Omega}(n)$. Therefore, regardless of whether we naively use the
patience sorting algorithm to update the local solutions or we use the more
sophisticated algorithm of Chen, Chu, and Pinsker [CCP13], the time required
to update the local solutions for such sampled layers is
$\widetilde{\Omega}(n)$.

$7$$3$$1$$9$$4$$6$$10$$11$$12$$13$$14$$5$$15$$8$$2$$7$$3$$1$$9$$4$$2$$6$$5$$10$$8$$11$$12$$13$$14$$15$$L_{1}$$L_{2}$$L_{3}$$L_{4}$$L_{5}$$L_{6}$$L_{7}$$L_{8}$$L_{9}$
Figure 2: This example shows how the baskets are made from the sampled layers.
Layers colored in yellow are the sampled layers.

To resolve this issue, we devise a heavy-light decomposition technique to deal
with different subproblems. In our algorithm, we make a basket out of
consecutive layers that end with a sampled layer. Thus, we refer to each of
the sampled layers as a boundary layer. For simplicity, we omit some of the
details of our algorithm here and only state the overall ideas. (For instance,
in our algorithm we do not sample the layers completely at random to make the
boundary layers.) Each basket then becomes one subproblem. We define a basket
to be light if the total number of elements included in it as well as the size
its boundary layer are both small. In other words, for each of the light
baskets, we can store and update the local solutions in sublinear time. A
basket is heavy if either its boundary size is large or it contains a large
number of elements. In the example of Figure 1, the basket that contains the
middle layer is a heavy basket. For such baskets, we do not store local
solutions but, instead, we maintain global information: for each element of a
heavy basket, we store the size of the longest increasing subsequence of the
entire sequence ending that element.

Because the solutions for heavy baskets are not local, once an operation
arrives, after updating the local solution for the corresponding basket (if it
is light), we need to propagate the effect of the change. That is, if the
local solution for a light basket is affected by a modification, we need to
update our solution for all the heavy baskets. To keep the update time
sublinear, we make one more observation: It is possible to update the solution
for a heavy basket in time proportional to the number of layers included in
it. For this purpose, we use the ideas of the work by Chen, Chu, and Pinsker
[CCP13] that design balanced trees to obtain a dynamic solution for LIS with
update time proportional to the solution size. In the interest of space, here
we omit several details of our algorithm; we prove in Section 3 that the
combination of these ideas gives us an exact dynamic algorithm for LIS with
update time $\widetilde{O}(n^{4/5})$.

######  Theorem 3 (restated informally).

There exists a randomized algorithm for dynamic LIS that has update time
$\widetilde{O}(n^{4/5})$ and maintains the value of LIS correctly with
probability at least $1-n^{-10}$ at each step.

One technical difficulty that arises in the algorithm of Theorem 3 is
modifying the global information stored within heavy baskets. Although we
prove that, with a desirable probability, the longest increasing subsequence
of the whole array contains an element from each of the sampled layers, this
does not hold for all increasing subsequences. Thus, it is likely that, for
some element $a_{i}$ in a heavy basket, our algorithm maintains an incorrect
value for the longest increasing subsequence ending at $a_{i}$. We discuss
this in Section 3 and explain how to overcome the issue.

In Section 3.1, we further improve the update time of our dynamic algorithm
down to $\widetilde{O}(n^{2/3})$ using advanced methods based on efficient
algorithms for handling Monge and unit-Monge matrices. The high-level
structure of the algorithm is similar to what is explained before, but the
light baskets are processed more efficiently.

######  Theorem 7 (restated informally).

There exists a randomized algorithm for dynamic LIS that has update time
$\widetilde{O}(n^{2/3})$ and maintains the value of LIS correctly with
probability at least $1-n^{-10}$ at each step.

###  2.2 $(1-o(1))$-Approximation Algorithm with $O(n^{o(1)})$ Update Time

Our $(1-o(1))$-approximation algorithm for dynamic LIS is based on the notion
of grid packing introduced by Mitzenmacher and Seddighin [MS20]. However, as
we discuss later in this section, a constant factor loss in the original grid
packing technique is inevitable. We address this issue by introducing the
extended variant of grid packing, which is the basis of our
$(1-o(1))$-approximation algorithm. We explain this in Section 2.2.1. The
generalization is natural and inspired by previous work on longest increasing
subsequence [IMS17]. However, the more novel and technically challenging
component of our algorithm is the application of extended grid packing to
dynamic LIS. Since previous applications of grid packing are based on a bound
that cannot be guaranteed for a $(1-o(1))$-approximate solution of extended
grid packing, we design a completely different approach for applying extended
grid packing to dynamic LIS. We elaborate more on this in Section 2.2.3. In
what follows, we denote the approximation factor of our algorithm by
$1-\epsilon$, but we allow subconstant $\epsilon$.

####  2.2.1 Background: Grid Packing

Grid packing is related to the notion of window-compatible solutions proposed
by Boroujeni, Ehsani, Ghodsi, HajiAghayi, and Seddighin [BEG+18] for
approximating edit distance within a constant factor. The problem can be
thought of as a game between us and an adversary. In this problem, we have a
table of size $m\times m$. Our goal is to introduce a number of segments on
the table. Each segment covers a consecutive set of cells either in a row or
in a column. A segment $A$ precedes a segment $B$ if every cell of $A$ is
strictly higher than every cell of $B$ and also every cell of $A$ is strictly
to the right of every cell of $B$. Two segments are non-conflicting if one of
them precedes the other one. Otherwise, we call them conflicting. The segments
we introduce can overlap, and there is no restriction on the number of
segments or the length of each segment. However, we would like to minimize the
maximum number of segments that cover each cell.

Figure 3: Segments are shown on the grid. The pair (black, orange) is
conflicting since the yellow cell (covered by the black segment) is on the
same row as the blue cell (covered by the orange segment). The following pairs
are non-conflicting: (green, black), (green, orange), (green, blue), (red,
orange), (red, blue), (black, blue).

After we choose the segments, an adversary puts a non-negative number on each
cell of the table. The score of a subset of cells of the table would be the
sum of their values and the overall score of the table is the maximum score of
a path of length $2m-1$ from the bottom-left corner to the top-right corner.
In such a path, we always either move up or to the right.

The score of a segment is the sum of the numbers on the cells it covers. We
obtain the maximum sum of the scores of a non-conflicting set of segments. The
score of the table is an upper bound on the score of any set of non-
conflicting segments. We would like to choose segments so that the ratio of
the score of the table and our score is bounded by a constant, no matter how
the adversary puts the numbers on the table. More precisely, we call a
solution $(\alpha,\beta)$-approximate, if at most $\alpha$ segments cover each
cell and it guarantees a $1/\beta$ fraction of the score of the table for us
for any assignment of numbers to the table cells.

Mitzenmacher and Seddighin [MS20] prove the following theorem: For any
$m\times m$ table and any $0<\kappa<1$, there exists a grid packing solution
with guarantee $(O_{\kappa}(m^{\kappa}\log m),O(1/\kappa))$. That is, each
cell is covered by at most $O_{\kappa}(m^{\kappa}\log m)$ segments and the
ratio of the table’s score over our score is bounded by $O(1/\kappa)$ in the
worst case.

######  Theorem 1 (from [MS20]).

For any $0<\kappa<1$, the grid packing problem on an $m\times m$ table admits
an $(O_{\kappa}(m^{\kappa}\log m),O(1/\kappa))$-approximate solution.

####  2.2.2 Extension: Grid Packing with Multisegments

The general framework of grid packing remains the same for our extension: The
problem can be thought of as a game played on an $m\times m$ table against an
adversary and the goal is to introduce some multisegments (a generalization of
segments explained below) such that after the adversary puts their numbers on
the table cells, the score we obtain is comparable to table’s score. However,
extended grid packing differs from grid packing in two ways: First, we
introduce a new notion that we call a multisegment and we allow the use of
multisegments instead of segments. Second, we do not enforce any bound on the
number of multisegments that cover each cell. That is, we only have one
objective which is maximizing the ratio of our score and the score of the
table. Without the bound, algorithmically utilizing extended grid packing for
LIS becomes more challenging as previous solutions require a cap on the
maximum number of segments covering each cell. Nevertheless, we show in
Section 4.2 how to apply extended grid packing in absence of this bound.

We bring an example in Section 4 to prove that by just using the segments in
the grid packing problem, there is no way to obtain more than a $2/3$ fraction
of the table’s score, even if there is no bound on the number of segments that
cover any cell. This example motivates our generalization, which we discuss in
the following: For a horizontal/vertical segment, we define its first cell as
its leftmost/bottommost cell and its last cell as the rightmost/topmost cell
of the segment. A $\Delta$-multisegment is defined as a combination of
$\Delta$ segments $s_{1},s_{2},\ldots,s_{\Delta}$ where, for each $1\leq
i\leq\Delta-1$, the last cell of segment $s_{i}$ coincides with the first cell
of segment $s_{i+1}$. (By definition, $1$-multisegments are the same as
segments.) We say that a multisegment covers a cell if any of its segments
covers that cell. Moreover, two multisegments $S_{1}$ and $S_{2}$ are non-
conflicting if, for each segment $x$ of $S_{1}$ and each segment $y$ of
$S_{2}$, the segments $x$ and $y$ are non-conflicting. To avoid confusion, we
use uppercase letters for multisegments and lowercase letters for segments.
Based on this definition, for any $1\leq i<\Delta$, an $i$-multisegment is
also a $\Delta$-multisegment (we may add $\Delta-i$ single cell segments to an
$i$-multisegment to make it compatible with the definition of
$\Delta$-multisegment without any change in its shape).

Figure 4: All polylines except for the green one are valid multisegments.
Yellow and gray multisegments are non-conflicting, while the rest of the
multisegment pairs are conflicting.

We define an extended version of the grid packing problem as a game between us
and an adversary. Similar to grid packing, we first introduce a number of
multisegments and then the adversary puts nonnegative numbers on the cells of
the table. Then, table’s score is formulated as the largest sum the adversary
can collect from the values of the cells by moving from the bottom-left corner
to the top-right corner of the table. Our score is the largest sum we can
collect by non-conflicting multisegments where the value of a multisegment is
equal to the total sum of the numbers of the cells it covers.

As we show in Lemma 32, if we consider all possible $\Delta$-multisegments in
our solution, our score is always at least a $\frac{\Delta-1}{\Delta}$
fraction of the table’s score. Notice that by introducing all such
multisegments, a cell may be covered by $m^{\Theta(\Delta)}$ multisegments.

######  Lemma 32 (restated).

Let $\Delta$ be a positive integer. If we introduce all $\Delta$-multisegments
in the extended grid packing problem, our score will be least a
$\frac{\Delta-1}{\Delta}$ fraction of the table’s score regardless of the
values of the table cells.

Lemma 32 alone does not suffice to improve the dynamic LIS algorithm of
Mitzenmacher and Seddighin [MS20] since the algorithm relies on a bound on the
number of segments that cover each cell. We remedy this issue by presenting a
more clever algorithm that does not require this bound.

####  2.2.3 Application of Extended Grid Packing

We refer the reader to previous work [MS20, MS21] for discussions on how to
use grid packing for approximating LIS. Roughly speaking, they consider the
point-based representation of the problem and construct an $m\times m$ grid
whose rows and columns evenly divide the points. Next, they use the grid
packing technique and, for each of the selected segments, they construct a
partial solution that maintains an approximation to the LIS of the points
covered by that segment. Thus, every time a change is made, their algorithm
has to update the solution for all segments that cover the modified point.
Therefore, previous techniques require a bound on the number of segments that
cover each cell of the grid to make sure the update time is sublinear. In
order to obtain a score arbitrarily close to the score of the table, we need
to include a lot of multisegments in our solution for extended grid packing,
many of which cover the same cells of the table. This renders the previous
approach incompatible with the new construction. To address this issue, we
introduce a new method that allows using all the $\Delta$-multisegments (for a
specific value $\Delta$).

At a high-level, the advantage of our new algorithm over the previous
technique is that we adaptively decide which multisegments to use in the
construction of a global solution. Previous applications are non-adaptive in
this sense: They consider all segments of the grid packing solution and, for
each segment, they maintain a partial solution for the points covered by that
segment. Our solution for extended grid packing uses $m^{O(\Delta)}$
multisegments (for a $(1-\epsilon)$-approximate solution, we require
$\Delta=\Omega(1/\epsilon)$) which is too many to even loop over. Thus, we
need to determine which multisegments have the potential to contribute to our
overall solution before combining the partial solutions. We make such
decisions adaptively as we query the subproblems in order to verify if a
multisegment can be used in our solution. Thus, as we modify the sequence, the
multisegments that may contribute to the global solution are subject to
change.

In order to apply extended grid packing, we generalize the dynamic LIS
problem. Instead of asking the size of the longest increasing subsequence
after each operation, we define a query to our algorithm in the following way:
a rectangle whose sides are parallel to the axis lines is given to us, and our
algorithm should output an estimation to the size of the longest increasing
subsequence of the points in the rectangle. This obviously generalizes the
problem since if the rectangle contains all of the points, then the answer is
the LIS of the entire sequence. This generalization has two benefits: (i)
Instead of defining each subproblem as the points covered by each segment (as
Mitzenmacher and Seddighin [MS20] do in previous work), we can define each
subproblem as the points covered by a row or a column. When the LIS of the
points covered by a segment is desired, we can simply query the corresponding
part of the subproblem which is covered by the segment. (This does not hold
for multisegments in general, but we show how to approximate the LIS of a
multisegment in Section 4.) This way, every operation changes at most two
subproblems (one row and one column), and thus there is no need to have a
bound on the number of segments that cover a point. (ii) The second and more
important benefit of this approach is that we can distinguish between the
query time and update time. More precisely, in previous work we make no
distinction between query time and update time since we only look for the LIS
of the whole sequence. Therefore, after each operation, the only question that
we ask is for the LIS of the entire sequence. With our generalization, we may
make multiple queries after an operation, and therefore answering a query may
require a different runtime. One of the key points of our algorithm is that
our query time is much smaller than our update time, and this allows us to
recursively run multiple queries in each of the subproblems without incurring
too much cost in the running time.

Generalized queries, of course, make the problem substantially more
complicated. Even in the stating setting (when there are no operations to be
performed on the sequence), answering this type of queries is not easy. If we
only seek to find the LIS of the entire sequence, patience sorting can solve
the problem in nearly linear time. However, if we are allowed to preprocess
the sequence and then have to handle queries for the LIS of rectangles, the
problem becomes more challenging. The authors are not aware of any linear-time
(or even quadratic-time) preprocessing algorithm supporting exact queries in
polylogarithmic time. As another application of extended grid packing, we show
in Section 4 how to answer the queries in polylogarithmic time with nearly
linear-time preprocessing by losing a $1-\epsilon$ factor in the
approximation.

A key ingredient of our algorithm is a discretization technique that
significantly improves the running time. Roughly speaking, the number of
$\Delta$-multisegments grows as $m^{\Theta(\Delta)}$ for an $m\times m$ grid
as we increase $\Delta$. Obviously, we cannot afford to consider all such
multisegments in our solution. Thus, we need to adaptively decide which
multisegments to use in a solution for LIS. To this end, we use a
discretization technique that narrows down the space of search fromall
$m^{\Theta(\Delta)}$ multisegments to an
$m^{O(1)}(\log_{1+\epsilon}n)^{O(\Delta)}$-sized subset at the expense of
losing a $1-\epsilon$ factor in the approximation. This method is technically
involved, but enables us to estimate the solution of a query in
polylogarithmic time. We explain the details of our algorithm in Section 4.

######  Theorem 35 (restated informally).

There exists an algorithm for dynamic LIS that approximates the solution
within a $1-o(1)$ multiplicative factor and updates the sequence in time
$O(n^{o(1)})$.

##  3 Exact Algorithm for Dynamic LIS

We present an exact dynamic algorithm for LIS with sublinear update time. Our
method is based on a heavy-light decomposition of regions of the array
combined with combinatorial analysis of increasing subsequences.

We use the notion of block-based algorithms [MS20] to simplify the
explanation. This lets us include preprocessing steps which may violate the
worst-case update times. Yet, it follows from [MS20] that a block-based
algorithm can be turned into a dynamic algorithm whose worst-case update time
is equal to the block-based algorithm’s amortized update time. More precisely,
a block-based algorithm starts with a sequence $a$ of size $n$. It is allowed
to preprocess the sequence in time $f(n)$. After the preprocessing step, the
algorithm is required to execute $g(n)$ operations, each in worst-case time
$h(n)$. After $g(n)$ operations, the block-based algorithm terminates. It
follows from previous work [MS20] that such an algorithm can be transformed
into a dynamic algorithm for LIS with worst-case update time
$O(f(n)/g(n)+h(n))$.

$7$$3$$1$$9$$4$$6$$10$$11$$12$$13$$14$$5$$15$$8$$2$$7$$3$$1$$9$$4$$2$$6$$5$$10$$8$$11$$12$$13$$14$$15$$L_{1}$$L_{2}$$L_{3}$$L_{4}$$L_{5}$$L_{6}$$L_{7}$$L_{8}$$L_{9}$$\infty$
Figure 5: In this example we have $w=3$ and $r=2$. The boundary layers are
colored in yellow. The last basket contains a dummy layer with a single
element with value $\infty$. We assume that the position of this element is to
the right of all existing elements.

We construct a block-based algorithm in the following way: In the
preprocessing step, we spend time $O(n\log n)$ and compute the size of the
longest increasing subsequence that ends at any element $a_{j}$. Let $b_{j}$
denote this value for element $a_{j}$. Let $L_{i}=\\{a_{j}\mid b_{j}=i\\}$ be
the set of elements whose corresponding solution has size $i$. We refer to
each $L_{i}$ as a _layer_. In the preprocessing step, we construct _baskets_
each of which consists of the elements of several consecutive layers. Keep in
mind that the elements of a basket are not necessarily consecutive in terms of
their position in the sequence. However, we maintain as an invariant that
every increasing subsequence visits the baskets in the increasing order.

In order to construct the baskets, we define a parameter $w$ that we set
later. All baskets, except for the first and the last baskets contain $w$
consecutive layers. We define the boundary of a basket as the last layer which
is included in that basket. We make the baskets in a way that the total size
of the boundaries is bounded by $O(n/w)$. Let us be more precise about this.
Since each element of the sequence is included in exactly one of the layers,
then we have $\sum|L_{i}|=n$. Therefore, if we choose an integer value $r$ in
range $[0,w-1]$ uniformly at random, then

$\mathbb{E}\left[\sum_{i\bmod w=r}|L_{i}|\right]=\frac{n}{w}.$

This implies that $\sum_{i\bmod w=r}|L_{i}|\leq 2n/w$ holds for at least
$\lceil w/2\rceil$ choices of $r$. Let $R$ be the set of all such choices for
$r$. In our algorithm, we choose a value $r$ from $R$ uniformly at random and
set $L_{r},L_{w+r},\ldots$ to be the boundaries. If $r\neq 0$, the first
basket contains all layers $L_{1},L_{2},\ldots,L_{r}$, otherwise it contains
the first $w$ layers. The second basket contains the next $w$ layers and the
same holds for the rest of the baskets. If the last basket contains fewer than
$w$ layers, we create an additional dummy layer that only contains an element
with position $n+1$ and value $\infty$ and put this in the last basket as the
boundary. Otherwise, we create a new basket that has a single element with
position $n+1$ and value infinity. This element is also the boundary of the
last basket. We denote by $d_{i}$ the size of basket $i$ (the number of
elements included in it) and by $e_{i}$ the size of the boundary of basket
$i$.

We emphasize that the layers, baskets, and their boundaries are essentially
kept intact for the lifetime of the algorithm (which is at most $g(n)$
updates) even though the optimal increasing subsequences may change. The only
exception is that each element inserted to the sequence $a$ is inserted to one
of the existing baskets, and each element removed from the sequence $a$ is
removed from its basket. The newly inserted elements are never included in the
boundary, and the algorithm declares a failure following any attempt to remove
a boundary element (which means that the algorithm ignores subsequent updates
and keeps reporting $0$ as the LIS length). Since the updates that the
algorithm encounters are independent of the random choice of $r$, any single
update leads to a failure with probability at most $1/|R|<2/w$, which makes
the overall failure probability limited to $2g(n)/w$.

Instead of maintaining the LIS, our algorithm actually maximizes the length of
an increasing subsequence that includes one element from each boundary (except
for the last one consisting of $a_{n+1}=\infty$). Before we describe how this
is achieved, let us argue why this is meaningful.

######  Lemma 2.

Let $U$ be an arbitrary longest increasing subsequence after at most $g(n)$
updates. Then, with probability at least $1-4g(n)/w$, subsequence $U$ contains
an element form each boundary layer (except for the last one consisting of
$a_{n+1}=\infty$).

###### Proof.

Note that $|U|\geq\mathsf{opt}-g(n)$, where $\mathsf{opt}$ denotes the LIS
length during the initialization. Moreover, at most $g(n)$ elements of $U$ may
have been added after the initialization, which means that at least
$|U|-2g(n)$ elements were present in the original sequence. Any increasing
subsequence contains at most one element from each layer, thus $U$ may miss up
to $2g(n)$ out of the $\mathsf{opt}$ initial layers constructed during
initialization. Any layer $L_{i}$ is a boundary layer if $i\bmod w=r$, which
happens with probability $1/|R|\leq 2/w$ and thus the probability that $U$
misses a boundary layer is at most $4g(n)/w$. ∎

Since the failure probability is $2g(n)/w$, Lemma 2 implies that each answer
reported by the algorithm is correct with probability at least $1-6g(n)/w$. We
set $g(n)=w/12$ to make sure that this is at least $1/2$. (To further boost
the success probability, our final algorithm will maintain $O(\log n)$
instances of the algorithm presented here; see the proof of Theorem 3 for
details.)

Let us proceed with the details of our algorithm. It follows from our
construction that each basket contains at most $w$ consecutive layers (the
equality holds with the exception of the first and the last baskets).
Moreover, the total size of the boundaries is bounded by $2n/w+1$ (the
additional $+1$ term is due to the dummy layer). Let $w\leq s\leq n$ be a
parameter that we set later. We use parameter $s$ to define a bound on the
size of the baskets that we call light. We categorize the baskets based on the
number of their elements and their boundary size:

  * •

We call a basket light, if its size is bounded by $s$, the size of its
boundary (the number of elements in its last layer) is bounded by $s/w$, and
the size of the boundary of its previous basket (if any) is bounded by $s/w$.

  * •

If a basket is not light, then we call it heavy. That is, a heavy basket
either has a size more than $s$ or a boundary size more than $s/w$ or its
previous basket has a boundary of size more than $s/w$.

Since the total number of elements is bounded by $n$ and the total size of all
boundaries is bounded by $2n/w+1$, then the number of heavy baskets is bounded
by $5n/s+1$.

Throughout our algorithm, we maintain a local data structure for each light
basket $i$ that stores the following information: If $i=1$, then for each
element $a_{y}$ of basket $1$, we store the size of the longest increasing
subsequence that ends at $a_{y}$. If $i>1$, then for each boundary element
$a_{x}$ of basket $i-1$ and each element $a_{y}$ of basket $i$, we store the
size of the longest increasing subsequence that starts at $a_{x}$ and ends at
$a_{y}$. Except for the initial element $a_{x}$, any element that may
contribute to such a subsequence is certainly inside basket $i$.

In the preprocessing step, we initialize all these data structures. We can
initialize the local data structure for basket $i>1$ in time
$O(e_{i-1}d_{i}\log n)$ by running patience sorting for each boundary element
of basket $i-1$ separately. The size of each light basket is bounded by $s$
and the total boundary size (across all baskets) is at most $2n/w+1$,
therefore the total time for initializing all light baskets $i>1$ is $O(ns\log
n/w)$. Initializing basket $1$ (if it is light) costs $O(d_{1}\log n)=O(s\log
n)$ time, and this does not change the overall preprocessing time
asymptotically.

We also keep some information for each heavy basket, but that information is
not local. In other words, it depends on the elements of the previous baskets
as well. In contrast, the data structure that we keep for each light basket is
completely local. Let $a_{i}$ be an element in basket $j$. We call an
increasing subsequence ending at element $a_{i}$ basket-compatible if it
includes one element from the boundary of each basket $1,2,\ldots,j-1$. For
every element $a_{i}$, we denote by $b^{\prime}_{i}$ the size of the longest
basket-compatible increasing subsequence that ends at $a_{i}$. Initially, we
have $b_{i}=b^{\prime}_{i}$ for all elements but as we make modifications to
the sequence, the values $b^{\prime}_{i}$ may diverge from $b_{i}$.

For each heavy basket, we partition its elements into disjoint sets. Each set
contains elements whose $b^{\prime}_{i}$’s are equal. Initially, each of these
sets is one of the layers included in the basket. As we modify the sequence,
the values $b^{\prime}_{i}$ change and thus these sets may no longer coincide
with the layers. Nevertheless, there is no extra preprocessing cost for heavy
baskets since these sets are initially equal to the layers.

When an operation arrives, we first locate the basket to which it relates. We
only consider element addition and element removal as element substitution can
be simulated by the first two operations. Element removal corresponds to the
basket that contains the element. Element addition corresponds to the basket
with lowest index such that none of its boundary elements is both to the left
of the added element and has a smaller value. In other words, when a new
element is added, we find the basket with lowest index such that none of its
boundary elements can be used to update the solution for the added element.
(This way, we maintain the invariant that every increasing subsequence visits
the baskets in the increasing order.) If the corresponding basket is light,
then we update the local data structure in time $O(s(s/w)\log n)=O(s^{2}\log
n/w)$ (recall that the size of each light basket is bounded by $s$ and the
previous basket has its boundary size bounded by $s/w$). If the operation
corresponds to a heavy basket, we do not make any local changes.

After local changes, we compute a global solution for all baskets in the
following way: starting from basket 1, for each boundary element $a_{i}$, we
compute $b^{\prime}_{i}$. After we do this for basket 1, we move on to basket
2 and proceed to the last basket. The computed value for the dummy element
minus 1 is the value that we report to the output.

Recall that $e_{i}$ denotes the size of the boundary of basket $i$. For a
light basket, we can use the local data structure and update the solution for
its boundary elements in time $O(e_{i-1}e_{i})$. Since basket $i$ is light,
then we have $e_{i}\leq s/w$ and since the total size of the boundaries is
bounded by $2n/w+1$ (i.e., $\sum e_{j}\leq 2n/w+1$), then the total runtime
for light baskets is bounded by $O(ns/w^{2})$. For each heavy basket, we use
the algorithm of Chen, Chu, and Pinsker [CCP13] to update the solution in time
$O(w\log n)$ (more details is given in the proof of Theorem 3). Thus, the
total update time for heavy baskets is $O(nw\log n/s)$ since there are at most
$5n/s+1$ heavy baskets. By setting $w=n^{0.4}$ and $s=n^{0.6}$ we obtain a
block-based algorithm with $f(n)=O(ns\log n/w)=O(n^{1.2}\log n)$,
$g(n)=w/12=n^{0.4}/12$, and $h(n)=O(s^{2}\log n/w+ns/w^{2}+nw\log
n/s)=O(n^{0.8}\log n)$. This leads to a dynamic algorithm for LIS with update
time $O(n^{0.8}\log n)$ that after each update reports the solution correctly
with probability at least $1/2$. By adding an additional $\log n$
multiplicative factor to the update time, we can improve the accuracy of the
algorithm to $1-n^{-10}$. There is one more $O(\log n)$ factor in the update
time due to the data structure that we use for accessing the elements of the
sequence.

######  Theorem 3.

There exists a randomized algorithm for the dynamic LIS problem that has
update time $O(n^{0.8}\log^{3}n)$ and maintains the value of LIS correctly
with probability at least $1-n^{-10}$.

###### Proof.

As discussed earlier we design a block-based algorithm with preprocessing time
$f(n)=O(n^{1.2}\log n)$ which is responsible for updating the solution for up
to $g(n)=n^{0.4}/12$ operations and updates the solution in worst-case time
$h(n)=O(n^{0.8}\log n)$. To this end, we set $s=n^{0.6}$, $w=n^{0.4}$, and
divide the elements into different baskets. By the discussion following Lemma
2, after each update, we report the correct value of LIS with probability at
least $1/2$.

To bring the failure probability down to $n^{-10}$, we repeat the same
procedure $20\log n$ times. That is, we choose $20\log n$ different values $r$
from $R$ and each time we make the baskets according to different boundaries.
Every time we output the maximum solution that we obtain from all the $20\log
n$ algorithms. Also, since we use a balanced tree to access the elements of
the sequence, another $O(\log n)$ factor is also involved in the runtime which
makes the overall update time $O(n^{0.8}\log^{3}n)$.

Another thing to note here is the algorithm we use for the heavy baskets. It
has been shown by Chen, Chu, and Pinsker [CCP13] that we can solve dynamic LIS
with update time $O(\mathsf{opt}\log n)$, where $\mathsf{opt}$ is the size of
the solution. In their algorithm, they divide the elements into subsets
$L^{\prime}_{1},L^{\prime}_{2},\ldots,L^{\prime}_{\mathsf{opt}}$ such that for
all the elements in subset $L^{\prime}_{i}$ the longest increasing subsequence
ending at them has size $i$. We use $L^{\prime}$ to denote these subsets since
we use $L_{i}$ for the layers of our algorithm. The stark difference between
$L^{\prime}_{i}$ and $L_{i}$ is that in our algorithm, $L_{i}$’s remain intact
as operations arrive but in their algorithm each $L^{\prime}_{i}$ gets updated
after changing the sequence.

$L^{\prime}_{1}\ =\ \langle 1\rangle$$L^{\prime}_{2}\ =\ \langle
5,2\rangle$$L^{\prime}_{3}\ =\ \langle 4\rangle$$\langle 1,\ 5,\ 2,\
\color[rgb]{0.494117647058824,0.827450980392157,0.129411764705882}\definecolor[named]{pgfstrokecolor}{rgb}{0.494117647058824,0.827450980392157,0.129411764705882}3\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\
,\ 4,\ 6,\ 7,\ 9,\ 10,\ 8\rangle$$\langle 1,\ 5,\ 2\ ,\ 4,\ 6,\ 7,\ 9,\ 10,\
8\rangle$$L^{\prime}_{4}\ =\ \langle 6\rangle$$L^{\prime}_{5}\ =\ \langle
7\rangle$$L^{\prime}_{6}\ =\ \langle 9,8\rangle$$L^{\prime}_{7}\ =\ \langle
10\rangle$$3$ Figure 6: This example illustrates how an element addition is
handled in the algorithm of Chen, Chu, and Pinsker [CCP13]. Inserting element
$3$ to the array changes the levels of the elements. Upward arrows show that
the level of the corresponding element increases after we add $3$ to the
array.

For completeness, we explain the algorithm of Chen, Chu, and Pinsker [CCP13]
in Appendix B. Their algorithm is based on the following observation: when an
operation is performed to the sequence, each element may only move between
consecutive subsets and, moreover, the elements that move form an interval. In
other words, if three elements $a_{i}>a_{j}>a_{k}$ belong to a subset, it is
impossible for elements $a_{i}$ and $a_{k}$ to move to another subset while
$a_{j}$ remains in the same subset after the update. They show that based on
these two properties, after each operation, we can update the solution in time
$O(\mathsf{opt}\log(n/\mathsf{opt}))$.

We use the same idea for heavy baskets. More precisely, for each heavy basket,
we divide the elements into subsets
$L^{\prime}_{\alpha},L^{\prime}_{\alpha+1},\ldots$ where for an $a_{j}$ in
element in a subset $L^{\prime}_{i}$ the size of the longest basket-compatible
increasing subsequence ending at $a_{j}$ is equal to $i$. We emphasize that
these subsets are different from $L_{1},L_{2},\ldots$ since they do not change
as we perform operations to the sequence. It is obvious that after each
operation, elements can only move between consecutive subsets of $L^{\prime}$
in a heavy basket. Moreover, if in a subset $L^{\prime}_{i}$ of a heavy basket
some elements move, the moving elements form an interval. To see this, we show
a reduction from the longest basket-compatible increasing subsequence to the
longest increasing subsequence. We know that this property holds for the
longest increasing subsequence. Now, from our sequence, we make another
sequence $a^{\prime}$, where $a^{\prime}$ is the same as $a$ except that we
copy each boundary element $n$ times and put the copies next to each other. To
make the values distinct, we add $i\epsilon$ to the $i$’th copy of each
boundary element. It follows that for each element $a^{\prime}_{i}$ of the new
sequence, if we find the longest increasing subsequence ending at
$a^{\prime}_{i}$ and remove the copied elements from the solution, we obtain
the longest basket-compatible increasing subsequence that ends at its
corresponding element in sequence $a$. This means that since performing a
single operation in $a^{\prime}$ preserves the interval property of moving
elements, the same also holds for $a$ when we are concerned with basket-
compatible increasing subsequences.

Initially, the values $b^{\prime}_{i}$ across elements in any single basket
span $w$ consecutive integers. Each operation changes the value
$b^{\prime}_{i}$ by at most one, therefore at any time the values
$b^{\prime}_{i}$ across elements in any single basket span at most
$w+2g(n)\leq\frac{14}{12}w$ consecutive integers. Hence, the cost of updating
any heavy basket is $O(w\log n)$, which yields $O(nw\log n/s)$ across all the
heavy baskets.

Thus, as discussed earlier, we obtain a block-based algorithm with
$f(n)=O(ns\log n/w)=O(n^{1.2}\log n)$, $g(n)=w/12=n^{0.4}/12$,
$h(n)=O(s^{2}\log n/w+ns/w^{2}+nw\log n/s)=O(n^{0.8}\log n)$. This leads to a
dynamic algorithm for LIS with update time $O(n^{0.8}\log n)$ that after each
update reports the solution correctly with probability at least $1/2$. Two
multiplicative $O(\log n)$ factors are added to the update time due to the
data structure we use to access the elements of the sequence and $20\log n$
different algorithms that we run in parallel to improve the failure
probability down to $n^{-10}$. ∎

###  3.1 An Improved Dynamic Algorithm with Update Time
$\widetilde{O}(n^{2/3})$

We further improve the update time of our dynamic algorithm by exploiting
structural insights expressed in terms of _Monge_ matrices, i.e., matrices
$M\in\mathbb{R}^{\ell\times m}$ such that $M[x,y]+M[x+1,y+1]\leq
M[x+1,y]+M[x,y+1]$ holds for $x\in[1\mathinner{.\,.}\ell)$ and
$y\in[1\mathinner{.\,.}m)$. Monge matrices arise in our algorithm due to the
following observation: For every basket $i>1$, the maximum lengths of
increasing subsequences starting at the boundary of basket $i-1$ and ending at
the boundary of basket $i$ can be embedded in an _anti-Monge_ matrix (obtained
by negating the entries of a Monge matrix). Recall that the algorithm of
Theorem 3 maintains these lengths for all light baskets $i>1$. We develop the
following two components to handle such baskets more efficiently:

  * •

In $\widetilde{O}(e_{i-1}+d_{i})$ time, we can construct an oracle that, given
elements $a_{x}$ and $a_{y}$ at the boundaries of baskets $i-1$ and $i$,
respectively, computes in $\widetilde{O}(1)$ time the size of the longest
increasing subsequence starting at $a_{x}$ and ending at $a_{y}$. This is
proven in Lemma 4, which also states that these values can be embedded in an
anti-Monge matrix $M_{i}$; the latter requires carefully setting the values
corresponding to _invalid queries_ for which $x>y$ or $a_{x}>a_{y}$.

  * •

Given the sizes $b^{\prime}_{x}$ of the longest basket-compatible increasing
subsequences ending at the boundary elements $a_{x}$ of basket $i-1$ and
assuming random access to the entries $M_{i}$, we can in
$\widetilde{O}(e_{i-1}+e_{i})$ time compute the sizes $b^{\prime}_{y}$ of the
longest basket-compatible increasing subsequences ending at the boundary
elements $a_{y}$ of basket $i$. This is proven in Lemma 6, where we rely on an
efficient algorithm for computing the $(\min,+)$-product of a Monge matrix
with a vector [AKM+87] (equivalent to the $(\max,+)$-product for an anti-Monge
matrix).

For every basket $i$, let $(a_{f_{i,j}})_{j=1}^{e_{i}}$ be the subsequence of
$(a_{i})_{i=1}^{n}$ consisting of the boundary elements of basket $i$. Recall
that each boundary was initialized as a single layer and that boundary
elements are never modified. Consequently, $(a_{f_{i,j}})_{j=1}^{e_{i}}$ forms
a decreasing subsequence.

######  Lemma 4.

For each basket $i>1$, there exists an anti-Monge matrix
$M_{i}\in\mathbb{R}^{e_{i-1}\times e_{i}}$ such that, for every
$j\in[1\mathinner{.\,.}e_{i-1}]$ and $k\in[1\mathinner{.\,.}e_{i}]$, we have:

$\displaystyle M_{i}[j,k]$ $\displaystyle=\text{length of the {LIS} from
$a_{f_{i-1,j}}$ to $a_{f_{i,k}}$}$ $\displaystyle\text{if
}f_{i-1,j}<f_{i,k}\text{ and }a_{f_{i-1,j}}<a_{f_{i,k}},$ $\displaystyle
M_{i}[j,k]$ $\displaystyle\leq-n$ otherwise.

Moreover, any entry of $M_{i}$ can be computed in $O(\log n/\log\log n)$ time
after $O((e_{i-1}+d_{i})\log^{2}n)$-time preprocessing of basket $i$ and the
boundary elements of basket $i-1$.

We derive Lemma 4 as an immediate corollary of the following theorem, stated
in terms of two arbitrary non-increasing subsequences rather than just the
subsequent boundary layers arising in our algorithm. Theorem 5 is a
generalization of a result of Tiskin [Tis13], who considered the problem of
computing so-called _semi-local_ LIS values. The key algorithmic ingredient of
Tiskin’s procedure is an efficient algorithm for computing the
$(\min,+)$-product of two _simple unit-Monge matrices_ [Tis15] (see Section
3.2 for further discussion and the proof of Theorem 5).

######  Theorem 5.

Let $(a_{i})_{i=0}^{n-1}$ be a real-valued sequence of length $n$, let
$(a_{p_{i}})_{i=0}^{k-1}$ and $(a_{q_{j}})_{j=0}^{\ell-1}$ be non-increasing
subsequences of $a$, and let $N$ be a positive integer. There exists an anti-
Monge matrix $M\in\mathbb{R}^{k\times\ell}$ such that, for every
$i\in[0\mathinner{.\,.}k)$ and $j\in[0\mathinner{.\,.}\ell)$, we have

$\displaystyle M[i,j]$ $\displaystyle=\text{length of the longest increasing
subsequence from $a_{p_{i}}$ to $a_{q_{j}}$}$ $\displaystyle\text{if
}p_{i}<q_{j}\text{ and }a_{p_{i}}<a_{q_{j}},$ $\displaystyle M[i,j]$
$\displaystyle\leq-N$ otherwise.

Moreover, any entry of $M$ can be computed in $O(\log n/\log\log n)$ time
after $O(n\log^{2}n)$-time preprocessing.

Recall that, for each $i\in[1\mathinner{.\,.}n]$, we denote by
$b^{\prime}_{i}$ the length of the longest basket-compatible increasing
subsequence ending at element $a_{i}$.

######  Lemma 6.

Consider a basket $i>1$ augmented with oracle access to the matrix $M_{i}$ of
Lemma 4. Given the values $(b^{\prime}_{f_{i-1,j}})_{j=1}^{e_{i-1}}$, the
values $(b^{\prime}_{f_{i,k}})_{k=1}^{e_{i}}$ can be computed in
$O((e_{i-1}+e_{i})\log n/\log\log n)$ time.

###### Proof.

We shall argue that
$b^{\prime}_{f_{i,k}}=\max_{j=1}^{e_{i-1}}(b^{\prime}_{f_{i-1,j}}+M_{i}[j,k]-1)$
holds for each $k\in[1\mathinner{.\,.}e_{i}]$. For a proof of the ‘$\leq$’
inequality, consider a longest basket-compatible increasing subsequence ending
at $a_{f_{i,k}}$. Since $a_{f_{i,k}}$ belongs to basket $i$, this subsequence
must include an element from the boundary of basket $i-1$, i.e.,
$a_{f_{i-1,j}}$ for some $j\in[1\mathinner{.\,.}e_{i-1}]$. Observe that every
prefix of a basket-compatible subsequence is basket-compatible. Hence, the
prefix ending at $a_{f_{i-1,j}}$ is of length at most
$b^{\prime}_{f_{i-1,j}}$. Furthermore, since $f_{i-1,j}\neq f_{i,k}$, the
suffix from $a_{f_{i-1,j}}$ to $a_{f_{i,k}}$ is of length at most
$M_{i}[j,k]$. The total length of the subsequence is therefore at most
$b^{\prime}_{f_{i-1,j}}+M_{i}[j,k]-1$ (note that the prefix and the suffix
share $a_{f_{i-1,j}}$). Consequently,
$b^{\prime}_{f_{i,k}}\leq\max_{j=1}^{e_{i-1}}(b^{\prime}_{f_{i-1,j}}+M_{i}[j,k]-1)$.

For a proof of the converse inequality, let us fix
$j\in[1\mathinner{.\,.}e_{i-1}]$. Note that if $M_{i}[j,k]\leq-n$, then

$b^{\prime}_{f_{i-1,j}}+M_{i}[j,k]-1\leq f_{i-1,j}-n-1<0<i\leq
b^{\prime}_{f_{i,k}}.$

Hence, we may assume that $f_{i-1,j}<f_{i,k}$ and $a_{f_{i-1,j}}<a_{f_{i,k}}$.
In particular, there exists an increasing subsequence from $a_{f_{i-1,j}}$ to
$a_{f_{i,k}}$ of length $M_{i}[j,k]\geq 2$. Combined with a basket-compatible
increasing subsequence of length $b^{\prime}_{f_{i-1,j}}$ ending at
$a_{f_{i-1,j}}$, this yields a basket-compatible increasing subsequence of
length $b^{\prime}_{f_{i-1,j}}+M_{i}[j,k]-1$ ending at $a_{f_{i,k}}$. Thus,
$b^{\prime}_{f_{i,k}}\geq b^{\prime}_{f_{i-1,j}}+M_{i}[j,k]-1$.

We conclude that the sought values $(b^{\prime}_{f_{i,k}})_{k=1}^{e_{i}}$ can
be expressed as the result of the $(\max,+)$-product of matrix $M_{i}$ with
vector $(b^{\prime}_{f_{i-1,j}}-1)_{j=1}^{e_{i-1}}$. Since $M_{i}$ is an anti-
Monge matrix, the SMAWK algorithm [AKM+87] can be applied to compute such a
product in $O(e_{i-1}+e_{i})$ time using $O(e_{i-1}+e_{i})$ queries accessing
the elements $M_{i}$; see [Tis13, Theorem 3.10]. The oracle of Lemma 4
provides $O(\log n/\log\log n)$-time access to $M_{i}$, so the total running
time is $O((e_{i-1}+e_{i})\log n/\log\log n)$. ∎

Our final algorithm for dynamic LIS applies Lemmas 4 and 6 for all light
baskets.

######  Theorem 7.

There exists a randomized algorithm for the dynamic LIS problem that has
update time $O(n^{2/3}\log^{4}n)$ and maintains the value of LIS correctly
with probability at least $1-n^{-10}$.

###### Proof.

Our algorithm is based on the same framework as that of Theorem 3, and thus
its correctness follows from Theorem 3. Here, we discuss the runtime. One
thing to keep in mind is that the matrices $M_{i}$ that we construct for light
baskets are accessed via oracle calls rather than being explicitly stored in
memory. For each light basket $i>0$, we build the oracle of Lemma 4 when the
basket is created and then every time it is modified.

Similar to Theorem 3, we design a block-based algorithm that starts with an
array of length $n$, performs the operations for $g(n)$ steps, and spends
(worst-case) time $h(n)$ for each operation. Assuming we have random access to
the elements of the sequence, we manage to make our algorithm work for
$f(n)=O(n\log^{3}n)$, $g(n)=n^{1/3}/12$, and $h(n)=O(n^{2/3}\log^{3}n)$, which
leads to a dynamic algorithm with update time $O(n^{2/3}\log^{3}n)$. An
additional $O(\log n)$ multiplicative factor appears in the runtime due to the
data structure that we use for accessing the sequence elements, and thus the
overall update time is bounded by $O(n^{2/3}\log^{4}n)$.

Using Corollary 4, we achieve the preprocessing time of $O(n\log^{3}n)$ since,
for each basket $i$ (regardless of whether it is light or heavy), the
preprocessing step can be implemented in time $O((e_{i-1}+d_{i})\log^{2}n)$
and therefore the total preprocessing time is $O(n\log^{3}n)$ (recall that we
run $O(\log n)$ parallel instances of our algorithm with different choices of
boundary layers to keep the error rate small). Compared to the algorithm of
Theorem 3, the update time is improved in two ways: whenever an update
modifies a light basket, we recompute the data structure of Lemma 4 from
scratch; this costs $O((e_{i-1}+d_{i})\log^{2}n)=O(s\log^{2}n)$ time per local
update. Similar to before, after local updates, we iteratively update the size
of LIS in an iterative manner. More precisely, starting from basket $1$, we
determine the size of the longest (basket-compatible) increasing subsequence
that ends at each boundary element of the basket. Lemma 6 implies that the
cost of processing a light basket is bounded by $O((e_{i-1}+e_{i})\log n)$.
Since the total size of the boundary layers is bounded by $O(n/w)$, this
amounts to a total cost of $O(n/w\log n)$ per instance. Similar to before, the
cost of processing a heavy basket is $O(w\log n)$ and, since we have at most
$O(n/s)$ such baskets in every instance, this amounts to a total cost of
$O(nw/s\log n)$ per instance. All the update times are multiplied by a factor
$O(\log n)$ since we solve the problem for $O(\log n)$ simultaneous instances.
Thus, the overall update time of our algorithm is bounded by
$O(s\log^{3}n+n/w\log^{2}n+nw/s\log^{2}n)$. By setting $s=n^{2/3}$ and
$w=n^{1/3}$, we obtain a block-based algorithm with preprocessing time
$f(n)=O(n\log^{3}n)$, $g(n)=w/12=\Omega(n^{1/3})$, and
$h(n)=O(n^{2/3}\log^{3}n)$, which in turn gives a dynamic algorithm with
worst-case update time $O(n^{2/3}\log^{3}n)$. ∎

###  3.2 LIS Oracle via Unit-Monge Matrices (Proof of Theorem 5)

Observe that Theorem 5 yields a data structure that, after
$O(n\log^{2}n)$-time preprocessing of a sequence $(a_{i})_{i=0}^{n-1}$ and its
two non-increasing subsequences $(a_{p_{i}})_{i=0}^{k-1}$ and
$(a_{q_{j}})_{j=0}^{\ell-1}$, supports the following queries in $O(\log
n/\log\log n)$ time: given $i\in[0\mathinner{.\,.}k)$ and
$j\in[0\mathinner{.\,.}\ell)$, compute the length of the longest increasing
subsequence of $a$ starting at $a_{p_{i}}$ and ending at $a_{q_{j}}$. Tiskin
[Tis13, Section 8.1] considered closely related semi-local LIS values and, in
particular, proved the following result:

######  Theorem 8 (Tiskin [Tis13]).

A sequence $(a_{i})_{i=0}^{n-1}$ can be preprocessed in $O(n\log^{2}n)$ to
support the following queries in $O(\log n/\log\log n)$ time: given indices
$i,j\in[0\mathinner{.\,.}n)$, compute the length of the longest increasing
subsequence of the sequence $a_{i},a_{i+1},\ldots,a_{j}$.

Note that the increasing subsequences in Theorem 8 do not have to contain
$a_{i}$ or $a_{j}$, whereas the increasing subsequences in Theorem 5 must
start at $a_{p_{i}}$ and end at $a_{q_{j}}$. To see that the latter setting is
more general, consider a sequence $(b_{i})_{i=0}^{3n-1}$ whose entries are
defined as follows for $i\in[0\mathinner{.\,.}3n)$:

$b_{i}=\begin{cases}-\infty&\text{if }i\bmod 3=0,\\\ a_{(i-1)/3}&\text{if
}i\bmod 3=1,\\\ +\infty&\text{if }i\bmod 3=2.\end{cases}$

Observe that any increasing subsequence of $a_{i},a_{i+1},\ldots,a_{j}$ yields
an increasing subsequence of $b_{3i+1},b_{3i+2},\ldots,b_{3j+1}$, which can be
extended with $b_{3i}=-\infty$ and $b_{3j+2}=+\infty$. Conversely, we obtain
an increasing subsequence of $a_{i},a_{i+1},\ldots,a_{j}$ by trimming the
endpoints of any increasing subsequence of $b$ starting at $b_{3i}=-\infty$
and ending at $b_{3j+2}=+\infty$. Thus, Theorem 8 can be derived from Theorem
5 applied to the sequence $(b_{i})_{i=0}^{3n-1}$ and its two subsequences
$(b_{3i})_{i=0}^{n-1}$ and $(b_{3j+2})_{j=0}^{n-1}$.

In order to prove Theorem 5, we carefully adapt the techniques of [Tis13].
Unfortunately, this requires generalizing the definitions of most
combinatorial objects and, consequently, repeating most of the proofs. The
only component that we managed to use in a black-box fashion is an efficient
procedure for computing the min-plus product of two simple unit-Monge matrices
[Tis13, Tis15].

####  3.2.1 Preliminaries

We start by introducing the terminology behind the definition of unit-Monge
matrices and their space-efficient representation. We mostly follow [Tis13,
Chapters 2 and 3], except that we always use integers to index matrix rows and
columns.

The $(\min,+)$ product of matrices $A\in\mathbb{R}^{n\times p}$ and
$B\in\mathbb{R}^{p\times m}$ is a matrix $A\odot B\in\mathbb{R}^{n\times m}$
with entries defined as follows for $i\in[0\mathinner{.\,.}n)$ and
$j\in[0\mathinner{.\,.}m)$:

$(A\odot B)[i,j]=\min_{k\in[0\mathinner{.\,.}p)}\left(A[i,k]+B[k,j]\right).$

For a matrix $A\in\mathbb{R}^{n\times m}$, the _distribution matrix_
$A^{\Sigma}\in\mathbb{R}^{(n+1)\times(m+1)}$ has its entries defined as
follows for $i\in[0\mathinner{.\,.}n]$ and $j\in[0\mathinner{.\,.}m]$:

$A^{\Sigma}[i,j]=\sum_{i^{\prime}\in[i\mathinner{.\,.}n),\;j^{\prime}\in[0\mathinner{.\,.}j)}A[i^{\prime},j^{\prime}].$

For a matrix $A\in\mathbb{R}^{(n+1)\times(m+1)}$, the _density matrix_
$A^{\square}\in\mathbb{R}^{n\times m}$ has its entries defined as follows for
$i\in[0\mathinner{.\,.}n)$ and $j\in[0\mathinner{.\,.}m)$:

$A^{\square}[i,j]=A[i+1,j]+A[i,j+1]-A[i,j]-A[i+1,j+1].$

The _seaweed product_ of matrices $A\in\mathbb{R}^{n\times p}$ and
$B\in\mathbb{R}^{p\times m}$ is a matrix $A\boxdot B=(A^{\Sigma}\odot
B^{\Sigma})^{\square}\in\mathbb{R}^{n\times m}$.

Note that every matrix $A\in\mathbb{R}^{n\times m}$ satisfies
$A=(A^{\Sigma})^{\square}$. A matrix $A\in\mathbb{R}^{(n+1)\times(m+1)}$ is
called _simple_ if $A=(A^{\square})^{\Sigma}$ or, equivalently, if $A[n,j]=0$
for $j\in[0\mathinner{.\,.}m]$ and $A[i,0]=0$ for $i\in[0\mathinner{.\,.}n]$.

A matrix $P\in\\{0,1\\}^{n\times n}$ is a _permutation matrix_ if each row and
each column contains exactly one entry equal to $1$. Note that an $n\times n$
permutation matrix can be represented with a permutation
$\sigma:[0\mathinner{.\,.}n)\to[0\mathinner{.\,.}n)$ such that $P[i,j]=1$ if
and only if $j=\sigma(i)$.

######  Theorem 9 (Tiskin [Tis13, Tis15]).

For any two $n\times n$ permutation matrices $P_{A},P_{B}$, the seaweed
product $P_{C}:=P_{A}\boxdot P_{B}$ is an $n\times n$ permutation matrix.
Moreover, given the permutations representing $P_{A}$ and $P_{B}$, the
permutation representing $P_{C}$ can be constructed in $O(n\log n)$ time.

A matrix $M\in\mathbb{R}^{n\times m}$ is a _Monge_ matrix if $M^{\square}$ has
non-negative entries, an _anti-Monge_ matrix if $M^{\square}$ has non-positive
entries, and a _unit-Monge_ matrix if $M^{\square}$ is a permutation matrix.
Note that an $n\times n$ simple unit-Monge matrix $M$ satisfies $M=P^{\Sigma}$
for the permutation matrix $P=M^{\square}$ and thus admits an $O(n)$-space
representation based on the permutation representing $P$.

######  Fact 10 ([Tis13, Theorem 2.15]).

Let $P$ be an $n\times n$ permutation matrix. There is a data structure of
size $O(n)$ that, given indices $i,j\in[0\mathinner{.\,.}n]$, computes
$P^{\Sigma}[i,j]$ in $O(\log n/\log\log n)$-time. Moreover, the data structure
can be constructed in $O(n\sqrt{\log n})$ time given the permutation
representing $P$.

###### Proof.

Consider a set $\mathcal{P}:=\\{(i,j)\in[0\mathinner{.\,.}n)^{2}:P[i,j]=1\\}$
consisting of exactly $n$ points on the plane. Observe that, for every
$i,j\in[0\mathinner{.\,.}n]$, we have
$P^{\Sigma}[i,j]=|\mathcal{P}\cap([i\mathinner{.\,.}n)\times[0\mathinner{.\,.}j))|$.
Thus, a query asking for $P^{\Sigma}[i,j]$ can be interpreted as an orthogonal
range counting query on $\mathcal{P}$.

As proved by Chan and Pătraşcu [CP10], these queries can be answered in
$O(\log n/\log\log n)$ time using a data structure of size $O(n)$ that can be
built in $O(n\sqrt{\log n})$ time given $\mathcal{P}$. This set can be
expressed as $\\{(i,\sigma(i)):i\in[0\mathinner{.\,.}n)\\}$ in terms of the
permutation $\sigma$ representing $P$. ∎

####  3.2.2 Grids and Alignment Graphs

In [Tis13, Section 4.3], Tiskin defines an alignment dag of two strings $X$
and $Y$, capturing the structure of the dynamic-programming algorithm for
computing their longest common subsequence. In order to derive the semi-local
score matrix, encoding, in particular, the LCS values between $X$ and the
substrings of $Y$, as well as between $X$ and the substrings of $Y$, he then
extends $X$ with wildcard characters and carefully handles pairs of
unreachable vertices (intuitively corresponding to substrings of negative
length). These complications would be very troublesome in our more general
setting, but they can be avoided using undirected edges of cost 0 and 1
instead of directed arcs of score 1 and 0, respectively. The price that we pay
for this more streamlined approach is a more complicated proof that our
alignment graph still encodes all local LCS values. Another (minor) difference
is that our construction is parameterized by an arbitrary set
$S\subseteq[0\mathinner{.\,.}n)\times[0\mathinner{.\,.}m)$ rather than a set
of the form $\\{(x,y):X[x]=Y[y]\\}$ defined in terms of two strings $X$ and
$Y$.

For $n,m\in\mathbb{Z}_{\geq 0}$, we define the _grid_
$\mathcal{G}^{n,m}=[0\mathinner{.\,.}n]\times[0\mathinner{.\,.}m]$ consisting
of $(n+1)(m+1)$ _points_.

######  Definition 11.

Given $n,m\in\mathbb{Z}_{\geq 0}$ and $S\subseteq\mathcal{G}^{n-1,m-1}$, we
define an undirected _alignment graph_ $\mathsf{AG}^{n,m}(S)$ with vertices
$\mathcal{G}^{n,m}$ and weighted edges:

  * •

$(x,y)\stackrel{{\scriptstyle 1}}{{\longleftrightarrow}}(x+1,y)$ for every
$(x,y)\in\mathcal{G}^{n-1,m}$,

  * •

$(x,y)\stackrel{{\scriptstyle 1}}{{\longleftrightarrow}}(x,y+1)$ for every
$(x,y)\in\mathcal{G}^{n,m-1}$,

  * •

$(x,y)\stackrel{{\scriptstyle 0}}{{\longleftrightarrow}}(x+1,y+1)$ for every
$(x,y)\in S$.

Note that an _alignment graph_ $G=\mathsf{AG}^{n,m}(S)$ induces a metric
$\mathrm{dist}_{G}:\mathcal{G}^{n,m}\times\mathcal{G}^{n,m}\to\mathbb{Z}_{\geq
0}$. In order to characterize this metric, we define a strict partial order
$\prec$ on $\mathbb{Z}^{2}$ with $(x,y)\prec(x^{\prime},y^{\prime})$ if and
only if $x<x^{\prime}$ and $y<y^{\prime}$. The underlying partial order
$\preceq$ satisfies $(x,y)\preceq(x^{\prime},y^{\prime})$ if and only if
$(x,y)=(x^{\prime},y^{\prime})$ or $(x,y)\prec(x^{\prime},y^{\prime})$. Note
that this is _not_ equivalent to $x\leq x^{\prime}$ and $y\leq y^{\prime}$.

A set $C\subseteq\mathbb{Z}^{2}$ is called a _chain_ if every two distinct
elements of $C$ are comparable with $\prec$. Observe that a finite set $C$ is
a chain if and only if its elements can be arranged in a sequence
$(x_{i},y_{i})_{i=0}^{|C|-1}$ such that both $(x_{i})_{i=0}^{|C|-1}$ and
$(y_{i})_{i=0}^{|C|-1}$ are (strictly) increasing sequences. Hence, we also
refer to such a sequence as a chain. Similarly, a set
$A\subseteq\mathcal{G}^{n,m}$ is called an _antichain_ if no two elements of
$A$ are comparable with $\prec$. Observe that a finite set $A$ is an antichain
if and only if its elements can be arranged in a sequence
$(x_{i},y_{i})_{i=0}^{|A|-1}$ such that $(x_{i})_{i=0}^{|A|-1}$ is non-
decreasing and $(y_{i})_{i=0}^{|A|-1}$ is non-increasing. Hence, we also refer
to such a sequence as an antichain.

For $S\subseteq\mathbb{Z}^{2}$, we denote by $\mathsf{LIS}(S)$ the maximum
size of a chain contained in $S$. Observe that $A\subseteq\mathbb{Z}^{2}$ is a
non-empty antichain if and only if $\mathsf{LIS}(A)=1$.

######  Lemma 12.

Let $p=(x,y)$ and $p^{\prime}=(x^{\prime},y^{\prime})$ be vertices of an
alignment graph $G=\mathsf{AG}^{n,m}(S)$.

  * •

If $x\leq x^{\prime}$ and $y\leq y^{\prime}$, then
$\mathrm{dist}_{G}(p,p^{\prime})=|x^{\prime}-x|+|y^{\prime}-y|-2\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))$.

  * •

If $x\leq x^{\prime}$ and $y\geq y^{\prime}$, then
$\mathrm{dist}_{G}(p,p^{\prime})=|x^{\prime}-x|+|y^{\prime}-y|$.

  * •

If $x\geq x^{\prime}$ and $y\leq y^{\prime}$, then
$\mathrm{dist}_{G}(p,p^{\prime})=|x^{\prime}-x|+|y^{\prime}-y|$.

  * •

If $x\geq x^{\prime}$ and $y\geq y^{\prime}$, then
$\mathrm{dist}_{G}(p,p^{\prime})=|x^{\prime}-x|+|y^{\prime}-y|-2\mathsf{LIS}(S\cap([x^{\prime}\mathinner{.\,.}x)\times[y^{\prime}\mathinner{.\,.}y)))$.

###### Proof.

Note that the cases in the lemma statement are not disjoint. However, if
multiple cases are applicable, then $x=x^{\prime}$ or $y=y^{\prime}$, and the
provided formulae are consistent due to $\mathsf{LIS}(\emptyset)=0$.

Let us first bound $\mathrm{dist}_{G}(p,p^{\prime})$ from above by induction
on $|x-x^{\prime}|+|y-y^{\prime}|$. In the base case of
$|x-x^{\prime}|+|y-y^{\prime}|=0$, we have $p=p^{\prime}$ and thus
$\mathrm{dist}_{G}(p,p^{\prime})=0=|x-x^{\prime}|+|y-y^{\prime}|$ holds as
claimed.

Next, suppose that $|x-x^{\prime}|+|y-y^{\prime}|>0$. By symmetry between the
coordinates, we may assume $|x-x^{\prime}|>0$. Moreover, since $G$ is
undirected and the claimed formulae for $\mathrm{dist}_{G}$ are symmetric, we
may further assume $x^{\prime}>x$. Let us consider a point
$p^{\prime\prime}=(x+1,y)$ and note that $G$ contains an edge
$p\stackrel{{\scriptstyle 1}}{{\longleftrightarrow}}p^{\prime\prime}$.
Furthermore, the inductive assumption, yields
$\mathrm{dist}_{G}(p^{\prime\prime},p^{\prime})\leq|x^{\prime}-x-1|+|y^{\prime}-y|=|x^{\prime}-x|+|y^{\prime}-y|-1$.
Hence, $\mathrm{dist}_{G}(p,p^{\prime})\leq
1+\mathrm{dist}_{G}(p^{\prime\prime},p^{\prime})\leq
1+|x^{\prime}-x|+|y^{\prime}-y|-1=|x^{\prime}-x|+|y^{\prime}-y|$. This
completes the inductive step provided that $y\geq y^{\prime}$ or
$S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime}))=\emptyset$.

It remains to consider the complementary case when $y^{\prime}>y$ and
$S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime}))\neq\emptyset$.
Let $C$ be a maximum chain contained in
$S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime}))$, let
$\mkern 1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern 1.0mu=(\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu,\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu)$ be the largest element
in $C$ (with respect to $\prec$), and let $\mkern
1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern 1.0mu^{\prime}=(\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+1,\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu+1)$. The inductive
assumption yields $\mathrm{dist}_{G}(p,\mkern
1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern 1.0mu)\leq|x-\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu|+|y-\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu|$ and, since
$C\setminus\\{\mkern 1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern 1.0mu\\}$
is a chain contained in $S\cap([\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu+1\mathinner{.\,.}x^{\prime})\times[\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern
1.0mu+1\mathinner{.\,.}y^{\prime}))$, that $\mathrm{dist}_{G}(\mkern
1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern
1.0mu^{\prime},p^{\prime})\leq|\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+1-x^{\prime}|+|\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu+1-y^{\prime}|-2(|C|-1)$.
By definition of $G$, there is an edge $\mkern
1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern 1.0mu\stackrel{{\scriptstyle
0}}{{\longleftrightarrow}}\mkern
1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern 1.0mu^{\prime}$. Hence,
$\mathrm{dist}_{G}(p,p^{\prime})\leq\mathrm{dist}_{G}(p,\mkern
1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern
1.0mu)+0+\mathrm{dist}_{G}(\mkern
1.0mu\overline{\mkern-1.0mup\mkern-1.0mu}\mkern
1.0mu^{\prime},p^{\prime})\leq|x-\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu|+|y-\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu|+|\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu+1-x^{\prime}|+|\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern
1.0mu+1-y^{\prime}|-2(|C|-1)=|x-x^{\prime}|+|y-y^{\prime}|-2|C|$. This
completes the inductive proof of the upper bound on $\mathrm{dist}_{G}$.

In order to bound $\mathrm{dist}_{G}$ from below, we need to prove a lower
bound on the cost of every walk $W$ from $p$ to $p^{\prime}$. We proceed by
induction on the number of edges in $W$. If $p=p^{\prime}$, then the cost of
$W$ is at least $0$ because all edge weights in $G$ are non-negative. Thus, we
may assume $p\neq p^{\prime}$, which means that the walk $W$ has at least one
edge. By symmetry between the coordinates and since $G$ is undirected, we may
further assume $x^{\prime}>x$. Let the first edge of the walk $W$ be
$p\stackrel{{\scriptstyle c}}{{\longleftrightarrow}}p^{\prime\prime}$ and let
$W^{\prime}$ be the complementary walk from
$p^{\prime\prime}:=(x^{\prime\prime},y^{\prime\prime})$ to $p^{\prime}$.

Note that $x^{\prime\prime}\leq x+1\leq x^{\prime}$. If $y^{\prime\prime}\geq
y^{\prime}$ and $y\geq y^{\prime}$, then the inductive assumption guarantees
that the cost of $W^{\prime}$ is at least
$|x^{\prime}-x^{\prime\prime}|+|y^{\prime}-y^{\prime\prime}|=x^{\prime}-x^{\prime\prime}+y^{\prime\prime}-y^{\prime}$,
and it suffices to prove that the cost of $W$ is at least
$|x^{\prime}-x|+|y^{\prime}-y|=x^{\prime}-x+y-y^{\prime}$, i.e., that
$c\geq(x^{\prime}-x+y-y^{\prime})-(x^{\prime}-x^{\prime\prime}+y^{\prime\prime}-y^{\prime})=x^{\prime\prime}-x+y-y^{\prime\prime}$.
We consider two possibilities:

  * •

If $c=1$, then $|x^{\prime\prime}-x|+|y^{\prime\prime}-y|=1$, so
$c=1=|x^{\prime\prime}-x|+|y^{\prime\prime}-y|\geq
x^{\prime\prime}-x+y-y^{\prime\prime}$.

  * •

If $c=0$, then $x-y=x^{\prime\prime}-y^{\prime\prime}$, so
$c=0=(x^{\prime\prime}-y^{\prime\prime})-(x-y)=x^{\prime\prime}-x+y-y^{\prime\prime}$.

Thus, it remains to consider the complementary case when
$y^{\prime\prime}<y^{\prime}$ or $y<y^{\prime}$. Due to
$|y^{\prime\prime}-y|\leq 1$, this yields $y^{\prime\prime}\leq y^{\prime}$
_and_ $y\leq y^{\prime}$. Consequently, the inductive assumption guarantees
that the cost of $W^{\prime}$ is at least
$x^{\prime}-x^{\prime\prime}+y^{\prime}-y^{\prime\prime}-2\mathsf{LIS}(S\cap([x^{\prime\prime}\mathinner{.\,.}x^{\prime})\times[y^{\prime\prime}\mathinner{.\,.}y^{\prime})))$,
and it suffices to prove that the cost of $W$ is at least
$x^{\prime}-x+y^{\prime}-y-2\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))$.
We consider three possibilities:

  * •

If $p^{\prime\prime}=(x+1,y+1)$, then $c=0$ and $(x,y)\in S$. Every chain in
$S\cap([x+1\mathinner{.\,.}x^{\prime})\times[y+1\mathinner{.\,.}y^{\prime}))$
can be extended with $(x,y)$, so
$\mathsf{LIS}(S\cap([x^{\prime\prime}\mathinner{.\,.}x^{\prime})\times[y^{\prime\prime}\mathinner{.\,.}y^{\prime})))\leq\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))-1$.
Hence, the cost of $W$ is at least
$0+x^{\prime}-x-1+y^{\prime}-y-1-2(\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))-1)=x^{\prime}-x+y^{\prime}-y-2\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))$,
as claimed.

  * •

If $p^{\prime\prime}\in\\{(x+1,y),(x,y+1)\\}$, then $c=1$ and
$\mathsf{LIS}(S\cap([x^{\prime\prime}\mathinner{.\,.}x^{\prime})\times[y^{\prime\prime}\mathinner{.\,.}y^{\prime})))\leq\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))$
by monotonicity of $\mathsf{LIS}$. Hence, the cost of $W$ is at least
$1+x^{\prime}-x+y^{\prime}-y-1-2\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))=x^{\prime}-x+y^{\prime}-y-2\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))$,
as claimed.

  * •

If $p^{\prime\prime}\in\\{(x-1,y-1),(x-1,y),(x,y-1)\\}$, then
$c=2-(x-x^{\prime\prime})-(y-y^{\prime\prime})$ and
$\mathsf{LIS}(S\cap([x^{\prime\prime}\mathinner{.\,.}x^{\prime})\times[y^{\prime\prime}\mathinner{.\,.}y^{\prime})))\leq\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))+1$
because
$(\\{x-1\\}\times[y\mathinner{.\,.}y^{\prime}))\cup([x\mathinner{.\,.}x^{\prime})\times\\{y-1\\})$
is an antichain. Hence, the cost of $W$ is at least
$c+x^{\prime}-x^{\prime\prime}+y^{\prime}-y^{\prime\prime}-2(\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))+1)=x^{\prime}-x+y^{\prime}-y-2\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))$,
as claimed.

This completes the inductive proof of the lower bound on $\mathrm{dist}_{G}$.
∎

####  3.2.3 Cut-Paths, Grid Slices, and Slice Alignment Graphs

The semi-local LCS and LIS values, studied by Tiskin in [Tis13, Chapters 4 and
8, respectively], are encoded by the distances between the boundary vertices
of the underlying alignment graph $\mathsf{AG}^{n,m}(S)$. The challenge in
proving Theorem 5 is that we need to encode the distances between vertices on
two arbitrary antichains in $\mathcal{G}^{n,m}$. For this, we maximally extend
these antichains and extract a _slice_ of the alignment graph lying “between”
the two antichains. As shown in Lemma 17, such a restriction does not affect
the distances between vertices within the slice.

We partition $\mathcal{G}^{n,m}$ into $n+m+1$ _diagonals_
$\mathcal{D}^{n,m}_{d}$ defined as follows for $d\in[0\mathinner{.\,.}n+m]$:

$\mathcal{D}^{n,m}_{d}:=\\{(x,y)\in\mathcal{G}^{n,m}:x-y=d-m\\}.$

######  Definition 13.

A _cut-path_ in $\mathcal{G}^{n,m}$ is an antichain
$\pi=(\pi_{d})_{d=0}^{n+m}$ such that $\pi_{d}\in\mathcal{D}^{n,m}_{d}$.

The following fact characterizes cut-paths in an alignment graph.

######  Fact 14.

Let $\pi$ be a cut-path in $\mathcal{G}^{n,m}$ and let
$G=\mathsf{AG}^{n,m}(S)$ for $S\subseteq\mathcal{G}^{n-1,m-1}$. Then, $\pi$ is
a path in $G$ (traversing weight-$1$ edges only) and, for every
$a,b\in[0\mathinner{.\,.}n+m]$, we have
$\mathrm{dist}_{G}(\pi_{a},\pi_{b})=|a-b|$. Moreover, $\pi$ separates
$\\{(x,y)\in\mathcal{G}^{n,m}:(x,y)\prec\pi_{x-y+m}\\}$ from
$\\{(x,y)\in\mathcal{G}^{n,m}:(x,y)\succ\pi_{x-y+m}\\}$.

###### Proof.

Let $\pi=(x_{d},y_{d})_{d=0}^{n+m}$. Consider subsequent points $\pi_{d}$ and
$\pi_{d+1}$ for $d\in[0\mathinner{.\,.}n+m)$. Note that $x_{d+1}\geq x_{d}$
and $y_{d+1}\leq y_{d}$ since $\pi$ is an antichain. Moreover,
$x_{d+1}-y_{d+1}=1+x_{d}-y_{d}$ because $\pi_{d}\in\mathcal{D}^{n,m}_{d}$ and
$\pi_{d+1}\in\mathcal{D}^{n,m}_{d+1}$. Consequently, $x_{d+1}\leq x_{d}+1$ and
$y_{d+1}\geq y_{d}-1$. Thus,
$(x_{d+1},y_{d+1})\in\\{(x_{d}+1,y_{d}),(x_{d},y_{d}-1)\\}$. In either case,
$G$ contains an edge $\pi_{d}\stackrel{{\scriptstyle
1}}{{\longleftrightarrow}}\pi_{d+1}$. Hence, $\pi$ is indeed a path traversing
weight-$1$ edges only.

If $a,b\in[0\mathinner{.\,.}n+m]$ with $a\geq b$, then $x_{a}\geq x_{b}$ and
$y_{a}\leq y_{b}$ since $\pi$ is an antichain. Consequently, Lemma 12 yields
$\mathrm{dist}(\pi_{a},\pi_{b})=|x_{b}-x_{a}|+|y_{b}-y_{a}|=x_{a}-x_{b}+y_{b}-y_{a}=(x_{a}-y_{a}+m)-(x_{b}-y_{b}+m)=a-b$
because $\pi_{a}\in\mathcal{D}^{n,m}_{a}$ and
$\pi_{b}\in\mathcal{D}^{n,m}_{b}$.

It remains to prove the final claim that $\pi$ separates
$\\{(x,y)\in\mathcal{G}^{n,m}:(x,y)\prec\pi_{x-y+m}\\}$ from
$\\{(x,y)\in\mathcal{G}^{n,m}:(x,y)\succ\pi_{x-y+m}\\}$. For a proof by
contradiction, suppose that there is an edge
$(x,y)\longleftrightarrow(x^{\prime},y^{\prime})$ in $G$ such that
$(x,y)\in\mathcal{D}^{n,m}_{d}$ satisfies $(x,y)\prec\pi_{d}$ and
$(x^{\prime},y^{\prime})\in\mathcal{D}^{n,m}_{d^{\prime}}$ satisfies
$(x^{\prime},y^{\prime})\succ\pi_{d^{\prime}}$. If $d\leq d^{\prime}$, then
$x<x_{d}\leq x_{d^{\prime}}<x^{\prime}$, so $x^{\prime}\geq x+2$, which is
clearly impossible. Similarly, if $d\geq d^{\prime}$, then $y<y_{d}\leq
y_{d^{\prime}}<y^{\prime}$, so $y^{\prime}\geq y+2$, which is also impossible.
∎

Not only each cut-path is an antichain, but also each maximal antichain in
$\mathcal{G}^{n,m}$ is a cut-path. We will need the following constructive
version of the latter statement:

######  Fact 15.

There is an $O(n+m)$-time algorithm that, given an antichain
$(x_{i},y_{i})_{i=0}^{k-1}$ in $\mathcal{G}^{n,m}$, constructs supersequence
that forms a cut-path in $\mathcal{G}^{n,m}$.

###### Proof.

Without loss of generality, we assume that $(x_{0},y_{0})=(0,m)$ and
$(x_{k-1},y_{k-1})=(n,0)$. If this is not the case, we extend the input
antichain accordingly. The cut-path $\pi$ is defined as follows:

$\pi_{d}=\begin{cases}(x_{i-1},x_{i-1}+m-d)&\text{for
}d\in[x_{i-1}-y_{i-1}+m\mathinner{.\,.}x_{i-1}-y_{i}+m]\text{ and
}i\in[1\mathinner{.\,.}k),\\\ (y_{i}+d-m,y_{i})&\text{for
}d\in[x_{i-1}-y_{i}+m\mathinner{.\,.}x_{i}-y_{i}+m]\text{ and
}i\in[1\mathinner{.\,.}k).\end{cases}$

Note that the intervals $[x_{i-1}-y_{i-1}+m\mathinner{.\,.}x_{i-1}-y_{i}+m]$
and $[x_{i-1}-y_{i}+m\mathinner{.\,.}x_{i}-y_{i}+m]$ for
$i\in[1\mathinner{.\,.}k)$ are non-empty because the sequence
$(x_{i})_{i=0}^{k-1}$ is non-decreasing and the sequence $(y_{i})_{i=0}^{k-1}$
is non-increasing. Moreover, due to $(x_{0},y_{0})=(0,m)$ and
$(x_{k-1},y_{k-1})=(n,0)$, these intervals cover $[0\mathinner{.\,.}n+m]$. Two
subsequent intervals intersect only at their boundaries, where the values are
set consistently: $\pi_{d}=(x_{i},y_{i})$ for $d=x_{i}-y_{i}+m$ and
$i\in[0\mathinner{.\,.}k)$, as well as $\pi_{d}=(x_{i-1},y_{i})$ for
$d=x_{i-1}-y_{i}+m$ for $i\in[1\mathinner{.\,.}k)$. Hence, $\pi$ is a well-
defined supersequence of $(x_{i},y_{i})_{i=0}^{k-1}$. Moreover, it is easy to
check that $\pi_{d}\in\mathcal{D}^{n,m}_{d}$ and $\pi$ is an antichain (the
first coordinates are non-decreasing and the second coordinates are non-
increasing). ∎

We extend the the partial order on points to a partial order on cut-paths,
with $\pi\preceq\pi^{\prime}$ if and only if $\pi_{d}\preceq\pi^{\prime}_{d}$
holds for each $d\in[0\mathinner{.\,.}n+m]$. Given two cut-paths
$\pi\preceq\pi^{\prime}$, we define _grid slices_

$\displaystyle\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime}]$
$\displaystyle=\\{(x,y)\in\mathcal{G}^{n,m}:\pi_{x-y+m}\preceq(x,y)\preceq\pi^{\prime}_{x-y+m}\\},$
$\displaystyle\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime})$
$\displaystyle=\\{(x,y)\in\mathcal{G}^{n,m}:\pi_{x-y+m}\preceq(x,y)\prec\pi^{\prime}_{x-y+m}\\}.$

######  Definition 16.

Let $\pi\preceq\pi^{\prime}$ be cut-paths in $\mathcal{G}^{n,m}$ and let
$S\subseteq\mathcal{G}^{n-1,m-1}$. We define the _slice alignment graph_
$\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$ as the subgraph of
$\mathsf{AG}^{n,m}(S)$ induced by
$\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime}]$.

######  Lemma 17.

Let $\pi\preceq\pi^{\prime}$ be cut-paths in $\mathcal{G}^{n,m}$ and let
$S\subseteq\mathcal{G}^{n-1,m-1}$. Moreover, let $G=\mathsf{AG}^{n,m}(S)$ and
$G^{\prime}=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$. Then, for every
$p,q\in\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime}]$, we have
$\mathrm{dist}_{G}(p,q)=\mathrm{dist}_{G^{\prime}}(p,q)$.

###### Proof.

Since $G^{\prime}$ is a subgraph of $G$, we trivially have
$\mathrm{dist}_{G}(p,q)\leq\mathrm{dist}_{G^{\prime}}(p,q)$. For the converse
inequality, we proceed by induction on the minimum number of edges on a
shortest path $\Pi$ from $p$ to $q$ in $G$. If $\Pi$ traverses at most one
edge, then $\Pi$ is also a path in $G^{\prime}$ and thus
$\mathrm{dist}_{G^{\prime}}(p,q)=\mathrm{dist}_{G}(p,q)$. If $\Pi$ contains an
internal vertex $r\in\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime}]$ then,
by the inductive assumption applied to the prefix of $\Pi$ from $p$ to $r$ and
the suffix of $\Pi$ from $r$ to $q$, we have
$\mathrm{dist}_{G^{\prime}}(p,q)\leq\mathrm{dist}_{G^{\prime}}(p,r)+\mathrm{dist}_{G^{\prime}}(r,q)=\mathrm{dist}_{G}(p,r)+\mathrm{dist}_{G}(r,q)=\mathrm{dist}_{G}(p,q)$.
Thus, we may assume that all internal vertices of $\Pi$ are outside
$\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime}]$ and that $\Pi$ has at
least one internal vertex $r$.

Let $\mathcal{L}=\\{(x,y)\in\mathcal{G}^{n,m}:(x,y)\prec\pi_{x-y+m}\\}$ and
$\mathcal{R}=\\{(x,y)\in\mathcal{G}^{n,m}(x,y)\succ\pi^{\prime}_{x-y+m}\\}$.
Observe that $\mathcal{G}^{n,m}$ forms a disjoint union of $\mathcal{L}$,
$\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime}]$, and $\mathcal{R}$.
Moreover, by 14, each edge leaving $\mathcal{L}$ has its other endpoint in
$\pi$, whereas each edge leaving $\mathcal{R}$ has its other endpoint in
$\pi^{\prime}$. Consequently, if $r\in\mathcal{L}$, then $p=\pi_{a}$ and
$q=\pi_{b}$ for some $a,b\in[0\mathinner{.\,.}n+m]$. However, 14 then implies
$\mathrm{dist}_{G^{\prime}}(p,q)=|b-a|=\mathrm{dist}_{G}(p,q)=|b-a|$ because
the path following $\pi$ is contained in $G^{\prime}$. Symmetrically, if
$r\in\mathcal{R}$, then $p=\pi^{\prime}_{a}$ and $q=\pi^{\prime}_{b}$ for some
$a,b\in[0\mathinner{.\,.}n+m]$ and, by 14,
$\mathrm{dist}_{G^{\prime}}(p,q)=|b-a|=\mathrm{dist}_{G}(p,q)$ because the
path following $\pi^{\prime}$ is contained in $G^{\prime}$. ∎

####  3.2.4 Distance and Seaweed Matrices

In [Tis13, Definitions 4.8 and 4.11], Tiskin uses his alignment dag to define
the semi-local score matrix and the seaweed matrix. Maximum-score paths in his
alignment dag correspond to shortest paths in our (undirected) alignment
graph, so we introduce a distance matrix instead of the semi-local score
matrix. Both approaches lead to the same seaweed matrix (we stick to the
original name even though we do not interpret this matrix in terms of seaweed
braids). Consequently, [Tis13, Theorem 4.10] can be seen as a special case of
Lemma 19 below, restricted to the two cut-paths $\pi$, $\pi^{\prime}$
following the boundary of $\mathsf{AG}^{n,m}(S)$ so that
$\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)=\mathsf{AG}^{n,m}(S)$.

######  Definition 18.

Given a slice alignment graph $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$, we
introduce two matrices $D_{G},M_{G}\in\mathbb{R}^{(n+m+1)\times(n+m+1)}$ with
entries defined as follows for $a,b\in[0\mathinner{.\,.}n+m]$:

$D_{G}[a,b]=\mathrm{dist}_{G}(\pi_{a},\pi^{\prime}_{b})\quad\text{and}\quad
M_{G}[a,b]=\tfrac{1}{2}(D_{G}[a,b]-a+b).$

Additionally, we set $P_{G}:=M_{G}^{\square}$ (note that also
$P_{G}=\frac{1}{2}D_{G}^{\square}$). The matrices $D_{G}$ and $P_{G}$ are
called the _distance matrix_ and the _seaweed matrix_ of $G$, respectively.

######  Lemma 19.

For every slice alignment graph $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$,
the matrix $D_{G}$ is a Monge matrix and the matrix $M_{G}$ is a simple unit-
Monge matrix.

###### Proof.

Note that $G$ is a planar graph and that the (cyclic) sequence of vertices on
its outer face is
$\pi^{\prime}_{0}=\pi_{0},\pi_{1},\ldots,\pi_{n+m-1},\pi_{n+m}=\pi^{\prime}_{n+m},\pi^{\prime}_{n+m-1},\ldots,\pi^{\prime}_{1}$.
As first explicitly observed by Fakcharoenphol and Rao [FR06, Section 2.3],
this yields that $D_{G}$ is a Monge matrix. Due to
$M_{G}^{\square}=\frac{1}{2}D_{G}^{\square}$, the matrix $M_{G}$ is thus also
a Monge matrix.

Next, let us characterize entries $D_{G}[a,b]$ with $a\in\\{0,n+m\\}$ or
$b\in\\{0,n+m\\}$. In each case, we use 14.

  * •

If $a=0$, then
$D_{G}[a,b]=\mathrm{dist}_{G}(\pi_{0},\pi^{\prime}_{b})=\mathrm{dist}_{G}(\pi^{\prime}_{0},\pi^{\prime}_{b})=b$.

  * •

If $a=n+m$, then
$D_{G}[a,b]=\mathrm{dist}_{G}(\pi_{n+m},\pi^{\prime}_{b})=\mathrm{dist}_{G}(\pi^{\prime}_{n+m},\pi^{\prime}_{b})=n+m-b$.

  * •

If $b=0$, then
$D_{G}[a,b]=\mathrm{dist}_{G}(\pi_{a},\pi^{\prime}_{0})=\mathrm{dist}_{G}(\pi_{a},\pi_{0})=a$.

  * •

If $b=n+m$, then
$D_{G}[a,b]=\mathrm{dist}_{G}(\pi_{a},\pi^{\prime}_{n+m})=\mathrm{dist}_{G}(\pi_{a},\pi_{n+m})=n+m-a$.

This yields the following characterization of the corresponding entries
$M_{G}[a,b]=\frac{1}{2}(D_{G}[a,b]-a+b)$:

  * •

If $a=0$, then $M_{G}[a,b]=\frac{1}{2}(b-a+b)=b$.

  * •

If $a=n+m$, then $M_{G}[a,b]=\frac{1}{2}(n+m-b-a+b)=0$.

  * •

If $b=0$, then $M_{G}[a,b]=\frac{1}{2}(a-a+b)=0$.

  * •

If $b=n+m$, then $M_{G}[a,b]=\frac{1}{2}(n-m-a-a+b)=n-m-a$.

In particular, $M_{G}[a,b]=0$ if $a=n+m$ or $b=0$, and therefore $M_{G}$ is a
simple matrix, i.e., $M_{G}=P_{G}^{\Sigma}$, where $P_{G}=M_{G}^{\square}$.
Consequently, it remains to prove that $P_{G}$ is a permutation matrix.

Since $M_{G}$ is a Monge matrix, we note that the entries of $P_{G}$ are non-
negative. Moreover, Lemmas 12 and 17 yield $D_{G}[a,b]\equiv(a-b)\pmod{2}$, so
$M_{G}$ and $P_{G}$ are integer matrices. Let us compute the sum of entries in
each row and column of $P_{G}$. For a row $a\in[0\mathinner{.\,.}n+m)$, we
have

$\sum_{b\in[0\mathinner{.\,.}n+m)}P_{G}[a,b]=\sum_{b\in[0\mathinner{.\,.}n+m)}(M_{G}[a+1,b]+M_{G}[a,b+1]-M_{G}[a,b]-M_{G}[a+1,b+1])=\\\
M_{G}[a+1,0]+M_{G}[a,n+m]-M_{G}[a,0]-M_{G}[a+1,n+m]=0+(n-m-a)-0-(n-m-(a+1))=1.$

Similarly, for a column $b\in[0\mathinner{.\,.}n+m)$, we have

$\sum_{a\in[0\mathinner{.\,.}n+m)}P_{G}[a,b]=\sum_{a\in[0\mathinner{.\,.}n+m)}(M_{G}[a+1,b]+M_{G}[a,b+1]-M_{G}[a,b]-M_{G}[a+1,b+1])=\\\
M_{G}[n+m,b]+M_{G}[0,b+1]-M_{G}[0,b]-M_{G}[n+m,b+1]=0+(b+1)-b-0=1.$

Thus, the entries in each row and each column of $P_{G}$ sum up to $1$. Since
$P_{G}$ is a non-negative integer matrix, this means that each row and each
column contains exactly one entry $P_{G}[a,b]=1$, and the remaining entries
satisfy $P_{G}[a,b]=0$. In other words, $P_{G}$ is a permutation matrix and
$M_{G}$ is a unit-Monge matrix. ∎

####  3.2.5 Composition of Slice Alignment Graphs

In [Tis13, Section 4.5], Tiskin uses Theorem 9 to efficiently retrieve the
seaweed matrix for a pair of strings $(XX^{\prime},Y)$ in terms of two seaweed
matrices for $(X,Y)$ and $(X^{\prime},Y)$. A direct generalization of his
approach lets us combine the seaweed matrices of two slice alignment graphs
sharing a cut-path.

######  Lemma 20.

Let $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$ be a slice alignment graph, let
$\pi^{\prime\prime}$ be a cut-path satisfying
$\pi\preceq\pi^{\prime\prime}\preceq\pi^{\prime}$, and let
$G_{L}=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime\prime},S\cap\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime\prime}))$
and
$G_{R}=\mathsf{SAG}^{n,m}(\pi^{\prime\prime},\pi^{\prime},S\cap\mathcal{G}^{n,m}[\pi^{\prime\prime}\mathinner{.\,.}\pi^{\prime}))$.
Then, $D_{G}=D_{G_{L}}\odot D_{G_{R}}$ and $P_{G}=P_{G_{L}}\boxdot P_{G_{R}}$.
In particular, given the permutations representing $P_{G_{L}}$ and
$P_{G_{R}}$, the permutation representing $P_{G}$ can be constructed in
$O((n+m)\log(n+m))$ time.

###### Proof.

First, observe that $G_{L}$ and $G_{R}$ are subgraphs of $G$ induced by
$\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime\prime}]$ and
$\mathcal{G}^{n,m}[\pi^{\prime\prime}\mathinner{.\,.}\pi^{\prime}]$,
respectively. Consequently, for every $a,b,c\in[0\mathinner{.\,.}n+m]$, we
have

$D_{G}[a,b]=\mathrm{dist}_{G}(\pi_{a},\pi^{\prime}_{b})\leq\mathrm{dist}_{G}(\pi_{a},\pi^{\prime\prime}_{c})+\mathrm{dist}_{G}(\pi^{\prime\prime}_{c},\pi^{\prime}_{b})\leq\mathrm{dist}_{G_{L}}(\pi_{a},\pi^{\prime\prime}_{c})+\mathrm{dist}_{G_{R}}(\pi^{\prime\prime}_{c},\pi^{\prime}_{b})\\\
=D_{G_{L}}[a,c]+D_{G_{R}}[c,b].$

Therefore, $D_{G}[a,b]\leq(D_{G_{L}}\odot D_{G_{R}})[a,b]$.

For a proof of the converse inequality, consider a shortest path from
$\pi_{a}$ to $\pi^{\prime}_{b}$. By 14, this path passes through a vertex
$\pi^{\prime\prime}_{c}$ for some $c\in[0\mathinner{.\,.}n+m]$. Moreover, by
Lemma 17, we have
$\mathrm{dist}_{G_{L}}(p,\pi^{\prime\prime}_{c})=\mathrm{dist}_{G}(p,\pi^{\prime\prime}_{c})$
and
$\mathrm{dist}_{G_{R}}(\pi^{\prime\prime}_{c},q)=\mathrm{dist}_{G_{L}}(\pi^{\prime\prime}_{c},q)$.
Consequently,

$D_{G}[a,b]=\mathrm{dist}_{G}(\pi_{a},\pi^{\prime}_{b})=\mathrm{dist}_{G}(\pi_{a},\pi^{\prime\prime}_{c})+\mathrm{dist}_{G}(\pi^{\prime\prime}_{c},\pi^{\prime}_{b})=\mathrm{dist}_{G_{L}}(\pi_{a},\pi^{\prime\prime}_{c})+\mathrm{dist}_{G_{R}}(\pi^{\prime\prime}_{c},\pi^{\prime}_{b})\\\
=D_{G_{L}}[a,c]+D_{G_{R}}[c,b]\geq(D_{G_{L}}\odot D_{G_{R}})[a,b].$

This completes the proof that $D_{G}=D_{G_{L}}\odot D_{G_{R}}$.

Next, we note that $M_{G}=M_{G_{L}}\odot M_{G_{R}}$ because the following
holds for every $a,b\in[0\mathinner{.\,.}n+m]$:

$\displaystyle(M_{G_{L}}\odot M_{G_{R}})[a,b]$
$\displaystyle=\min_{c\in[0\mathinner{.\,.}n+m]}(M_{G_{L}}[a,c]+M_{G_{R}}[c,b])$
$\displaystyle=\min_{c\in[0\mathinner{.\,.}n+m]}(\tfrac{1}{2}(D_{G_{L}}[a,c]-a+c)+\tfrac{1}{2}(D_{G_{R}}[c,b]-c+b))$
$\displaystyle=\tfrac{1}{2}\left(\min_{c\in[0\mathinner{.\,.}n+m]}(D_{G_{L}}[a,c]+D_{G_{R}}[c,b])-a+b\right)$
$\displaystyle=\tfrac{1}{2}\left((D_{G_{L}}\odot D_{G_{R}})[a,b]-a+b\right)$
$\displaystyle=\tfrac{1}{2}(D_{G}[a,b]-a+b)$ $\displaystyle=M_{G}[a,b].$

Consequently, $P_{G}=M_{G}^{\square}=(M_{G_{L}}\odot
M_{G_{R}})^{\square}=(P_{G_{L}}^{\Sigma}\odot
P_{G_{R}}^{\Sigma})^{\square}=P_{G_{L}}\boxdot P_{G_{R}}$ holds as claimed.
The algorithmic claim thus follows from Theorem 9. ∎

####  3.2.6 Removing Empty Rows and Columns

The main feature of the alignment graphs $\mathsf{AG}^{n,m}(S)$ originating
from LIS instances (as opposed arbitrary LCS instances) is that $|S|=O(n+m)$.
Moreover, the divide-and-conquer approach suggested by Lemma 20 allows further
reducing $|S|$ in each recursive call. Nevertheless, the grid dimensions
remain the same. In this section, we show that removing empty rows and columns
(not containing any element of $S$) changes the seaweed matrix in a very
predictable way, as described in Lemma 24. The procedure of Lemma 27 uses this
characterization to efficiently reverse the impact of the removal on the
seaweed matrix. This lets our divide-and-conquer algorithm reduce the grid
dimensions on par with decreasing $|S|$. Tiskin uses a similar reduction in
[Tis13, Algorithm 8.2], but the analogue of Lemma 24 is much simpler for
alignment graphs (compared to slice alignment graphs). We also note that Lemma
24 follows from the interpretation of seaweed matrices in terms of seaweed
braids: it is a simple observation that the seaweeds originating from empty
rows or columns are never combed away. Nevertheless, we opted for a more
tedious proof avoiding the seaweed monoid (which we would need to formally
link to the seaweed matrices of slice alignment graphs).

For $X\subseteq\mathbb{R}$ and $x\in\mathbb{R}$, define
$\mathsf{rk}_{X}(x)=|\\{x^{\prime}\in X:x^{\prime}<x\\}|$. Given
$X\subseteq[0\mathinner{.\,.}n)$ and $Y\subseteq[0\mathinner{.\,.}m)$, define
a mapping $\mathsf{d}_{X,Y}:\mathcal{G}^{n,m}\to\mathcal{G}^{|X|,|Y|}$ with

$\mathsf{d}_{X,Y}(x,y)=(\mathsf{rk}_{X}(x),\mathsf{rk}_{Y}(y)).$

We extend $\mathsf{d}_{X,Y}$ to map cut-paths in $\mathcal{G}^{n,m}$ to cut-
paths in $\mathcal{G}^{|X|,|Y|}$.

######  Definition 21.

Let $\pi$ be a cut-path in $\mathcal{G}^{n,m}$, let
$X\subseteq[0\mathinner{.\,.}n)$ and $Y\subseteq[0\mathinner{.\,.}m)$. The
sequence $\mathsf{d}_{X,Y}(\pi)$ is obtained from
$\mathsf{d}_{X,Y}(\pi_{0}),\ldots,\mathsf{d}_{X,Y}(\pi_{n+m})$ by removing
duplicate adjacent elements.

######  Observation 22.

Let $\pi$ be a cut-path in $\mathcal{G}^{n,m}$. For every
$x\in[0\mathinner{.\,.}n)$, there exists a unique index
$d\in[0\mathinner{.\,.}n+m)$, denoted $\mathsf{xi}(\pi,\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu)$, such that
$x_{d}=x<x_{d+1}$. Moreover, for every $y\in[0\mathinner{.\,.}m)$, there
exists a unique index $d\in[0\mathinner{.\,.}n+m)$, denoted
$\mathsf{yi}(\pi,y)$, such that $y_{d+1}=y<y_{d}$.

######  Fact 23.

Let $\pi$ be a cut-path in $\mathcal{G}^{n,m}$,
$X\subseteq[0\mathinner{.\,.}n)$, and $Y\subseteq[0\mathinner{.\,.}m)$. Then,
$\widetilde{\pi}:=\mathsf{d}_{X,Y}(\pi)$ is a cut-path in
$\mathcal{G}^{|X|,|Y|}$ and, for $d\in[0\mathinner{.\,.}n+m]$, we have
$\mathsf{d}_{X,Y}(\pi_{d})=\widetilde{\pi}_{\mathsf{rk}_{R}(d)}$, where
$R=\\{\mathsf{xi}(\pi,x):x\in X\\}\cup\allowbreak\\{\mathsf{yi}(\pi,y):y\in
Y\\}$.

###### Proof.

Let $\pi=(x_{d},y_{d})_{d=0}^{n+m}$. Observe that $x_{d+1}\neq x_{d}$ if and
only if $d=\mathsf{xi}(\pi,x_{d})$, so
$\mathsf{rk}_{X}(x_{d+1})\neq\mathsf{rk}_{X}(x_{d})$ if and only if
$d\in\\{\mathsf{xi}(\pi,x):x\in X\\}$. Similarly, $y_{d+1}\neq y_{d}$ if and
only if $d=\mathsf{yi}(\pi,y_{d+1})$, so
$\mathsf{rk}_{Y}(y_{d+1})\neq\mathsf{rk}_{Y}(y_{d})$ if and only if
$d\in\\{\mathsf{yi}(\pi,y):y\in Y\\}$. Hence,
$\mathsf{d}_{X,Y}(\pi_{d+1})\neq\mathsf{d}_{X,Y}(\pi_{d})$ if and only if
$d\in R$, and therefore
$\mathsf{d}_{X,Y}(\pi_{d})=\widetilde{\pi}_{\mathsf{rk}_{R}(d)}$. In
particular, $\widetilde{\pi}$ has $|X|+|Y|+1$ elements.

Denote
$\widetilde{\pi}=(\widetilde{x}_{d},\widetilde{y}_{d})_{d=0}^{|X|+|Y|}$. Since
$(x_{d})_{d=0}^{n+m}$ is non-increasing, so is
$(\mathsf{rk}_{X}(x_{d}))_{d=0}^{n+m}$ and its subsequence
$(\widetilde{x}_{d})_{d=0}^{|X|+|Y|}$. Symmetrically, since
$(y_{d})_{d=0}^{n+m}$ is non-decreasing, so is
$(\mathsf{rk}_{Y}(y_{d}))_{d=0}^{n+m}$ and its subsequence
$(\widetilde{y}_{d})_{d=0}^{|X|+|Y|}$. Consequently, $\widetilde{\pi}$ is an
antichain. Moreover, since each diagonal in $\mathcal{G}^{|X|,|Y|}$ is a
chain, $\widetilde{\pi}$ contains exactly one entry from each diagonal, and
thus it must be a cut-path. ∎

######  Lemma 24.

Let $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$ be a slice alignment graph and
let $X\subseteq[0\mathinner{.\,.}n)$ and $Y\subseteq[0\mathinner{.\,.}m)$ be
such that $S\subseteq X\times Y$. Then,
$\widetilde{G}:=\mathsf{SAG}^{|X|,|Y|}(\mathsf{d}_{X,Y}(\pi),\mathsf{d}_{X,Y}(\pi^{\prime}),\\{\mathsf{d}_{X,Y}(p):p\in
S\\})$ is a well-defined slice alignment graph. Moreover,

$P_{G}[a,b]=\begin{cases}P_{\widetilde{G}}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]&\text{if
}a\in R\text{ and }b\in R^{\prime},\\\ 1&\text{if }a=\mathsf{xi}(\pi,x)\text{
and }b=\mathsf{xi}(\pi^{\prime},x)\text{ for some }x\in\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu,\\\ 1&\text{if
}a=\mathsf{yi}(\pi,y)\text{ and }b=\mathsf{yi}(\pi^{\prime},y)\text{ for some
}y\in\mkern 1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu,\\\
0&\text{otherwise,}\end{cases}$

where $R=\\{\mathsf{xi}(\pi,x):x\in
X\\}\cup\allowbreak\\{\mathsf{yi}(\pi,y):y\in Y\\}$,
$R^{\prime}=\\{\mathsf{xi}(\pi^{\prime},x):x\in
X\\}\cup\allowbreak\\{\mathsf{yi}(\pi^{\prime},y):y\in Y\\}$, $\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu=[0\mathinner{.\,.}n)\setminus X$, and $\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu=[0\mathinner{.\,.}m)\setminus Y$.

###### Proof.

Denote $\pi=(x_{d},y_{d})_{d=0}^{n+m}$ and
$\pi^{\prime}=(x^{\prime}_{d},y^{\prime}_{d})_{i=0}^{n+m}$, as well as
$\mathsf{dx}_{\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu}(\pi)=\widetilde{\pi}=(\widetilde{x}_{d},\widetilde{y}_{d})_{d=0}^{|X|+|Y|}$
and $\mathsf{dx}_{\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu}(\pi^{\prime})=\widetilde{\pi}^{\prime}=(\widetilde{x}^{\prime}_{d},\widetilde{y}^{\prime}_{d})_{d=0}^{|X|+|Y|}$.

By 23, both $\widetilde{\pi}$ and $\widetilde{\pi}^{\prime}$ are cut-paths in
$\mathcal{G}^{|X|,|Y|}$. In order to prove that $\widetilde{G}$ is well-
defined, we need to show that
$\widetilde{\pi}_{d}\preceq\widetilde{\pi}^{\prime}_{d}$ holds for every
$d\in[0\mathinner{.\,.}|X|+|Y|)$. Let us choose $a,b\in[0\mathinner{.\,.}n+m]$
so that $\widetilde{\pi}_{d}=\mathsf{d}_{X,Y}(x_{a},y_{a})$ and
$\widetilde{\pi}^{\prime}_{d}=\mathsf{d}_{X,Y}(x^{\prime}_{b},y^{\prime}_{b})$.
If $a\leq b$, then we have
$\widetilde{x}_{d}=\mathsf{rk}_{X}(x_{a})\leq\mathsf{rk}_{X}(x_{b})\leq\mathsf{rk}_{X}(x^{\prime}_{b})=\widetilde{x}^{\prime}_{d}$.
Similarly, if $a\geq b$, then we have
$\widetilde{y}_{d}=\mathsf{rk}_{Y}(y_{a})\leq\mathsf{rk}_{Y}(y_{b})\leq\mathsf{rk}_{Y}(y^{\prime}_{b})=\widetilde{y}^{\prime}_{d}$.
In either case, due to
$\widetilde{\pi}_{d},\widetilde{\pi}^{\prime}_{d}\in\mathcal{D}^{|X|,|Y|}_{d}$,
this implies $\widetilde{\pi}_{d}\preceq\widetilde{\pi}^{\prime}_{d}$.
Consequently, $\widetilde{\pi}\preceq\widetilde{\pi}^{\prime}$ and
$\widetilde{G}$ is well-defined.

######  Claim 25.

Let $p=(x,y)$ and $q=(x^{\prime},y^{\prime})$ be points in
$\mathcal{G}^{n,m}[\pi\mathinner{.\,.}\pi^{\prime}]$ such that
$\mathsf{d}_{X,Y}(p),\mathsf{d}_{X,Y}(q)\in\mathcal{G}^{|X|,|Y|}[\widetilde{\pi}\mathinner{.\,.}\widetilde{\pi}^{\prime}]$.
Then,
$\mathrm{dist}_{G}(p,q)=\mathrm{dist}_{\widetilde{G}}(\mathsf{d}_{X,Y}(p),\mathsf{d}_{X,Y}(q))+|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu}(x)-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime})|+|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y)-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y^{\prime})|$.

###### Proof.

Denote $(\widetilde{x},\widetilde{y})=\mathsf{d}_{X,Y}(p)$,
$(\widetilde{x}^{\prime},\widetilde{y}^{\prime})=\mathsf{d}_{X,Y}(q)$, and
$\widetilde{S}=\\{\mathsf{dx}_{\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu}(r):r\in S\\}$. The
assumption $S\subseteq X\times Y$ implies that $\mathsf{d}_{X,Y}$ restricted
to $S$ is a monotonically increasing bijection mapping $S$ to $\widetilde{S}$,
i.e., $\mathsf{d}_{X,Y}$ preserves chains. Consequently, if $x\leq x^{\prime}$
and $y\leq y^{\prime}$, then
$\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime})))=\mathsf{LIS}(\widetilde{S}\cap([\widetilde{x}\mathinner{.\,.}\widetilde{x}^{\prime})\times[y\mathinner{.\,.}y^{\prime})))$,
so Lemmas 12 and 17 yield

$\mathrm{dist}_{G}(p,q)-\mathrm{dist}_{\widetilde{G}}(\mathsf{dx}_{\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu}(p),\mathsf{dx}_{\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu}(q))=(|x^{\prime}-x|+|y^{\prime}-y|-2\mathsf{LIS}(S\cap([x\mathinner{.\,.}x^{\prime})\times[y\mathinner{.\,.}y^{\prime}))))-\\\
(|\widetilde{x}^{\prime}-\widetilde{x}|+|y^{\prime}-y|-2\mathsf{LIS}(\widetilde{S}\cap([\widetilde{x}\mathinner{.\,.}\widetilde{x}^{\prime})\times[y\mathinner{.\,.}y^{\prime}))))=|x^{\prime}-x|-|\widetilde{x}^{\prime}-\widetilde{x}|+|y^{\prime}-y|-|\widetilde{y}^{\prime}-\widetilde{y}|.$

Similarly, if $x\leq x^{\prime}$ and $y\geq y^{\prime}$, then Lemmas 12 and 17
yield

$\mathrm{dist}_{G}(p,q)-\mathrm{dist}_{\widetilde{G}}(\mathsf{dx}_{\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu}(p),\mathsf{dx}_{\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu}(q))=(|x^{\prime}-x|+|y^{\prime}-y|)-(|\widetilde{x}^{\prime}-\widetilde{x}|+|y^{\prime}-y|)=\\\
|x^{\prime}-x|-|\widetilde{x}^{\prime}-\widetilde{x}|+|y^{\prime}-y|-|\widetilde{y}^{\prime}-\widetilde{y}|.$

The cases involving $x\geq x^{\prime}$ are symmetric. Furthermore,

$|x^{\prime}-x|-|\widetilde{x}^{\prime}-\widetilde{x}|=|x^{\prime}-x|-|\mathsf{rk}_{X}(x^{\prime})-\mathsf{rk}_{X}(x)|=|x^{\prime}-\mathsf{rk}_{X}(x^{\prime})-x+\mathsf{rk}_{X}(x)|=|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu}(x)|.$

Symmetrically,

$|y^{\prime}-y|-|\widetilde{y}^{\prime}-\widetilde{y}|=|y^{\prime}-y|-|\mathsf{rk}_{Y}(y^{\prime})-\mathsf{rk}_{Y}(y)|=|y^{\prime}-\mathsf{rk}_{Y}(y^{\prime})-y+\mathsf{rk}_{Y}(y)|=|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y)|,$

so $\mathrm{dist}_{G}(p,q)-\mathrm{dist}_{\widetilde{G}}(\mathsf{dx}_{\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu}(p),\mathsf{dx}_{\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu}(q))=|x^{\prime}-x|-|\widetilde{x}^{\prime}-\widetilde{x}|+|y^{\prime}-y|-|\widetilde{y}^{\prime}-\widetilde{y}|=|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x)|+|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y)|$ holds as claimed.
∎

Next, we use 23 and 25 to characterize the entries of $D_{G}$ in terms of
$D_{\widetilde{G}}$. For every $a,b\in[0\mathinner{.\,.}n+m]$, we have

$D_{G}[a,b]=\mathrm{dist}_{G}(\pi_{a},\pi^{\prime}_{b})=\mathrm{dist}_{\widetilde{G}}(\mathsf{d}_{X,Y}(\pi_{a}),\mathsf{d}_{X,Y}(\pi^{\prime}_{b}))+|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a})|+|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y_{a})|\\\
=D_{\widetilde{G}}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]+|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a})|+|\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y_{a})|.$

Let us decompose $D_{G}=T_{\widetilde{G}}+T_{X}+T_{Y}$ into three matrices
corresponding to the three terms above.

######  Claim 26.

For every $a,b\in[0\mathinner{.\,.}n+m)$, we have

$\displaystyle T_{\widetilde{G}}^{\square}[a,b]$
$\displaystyle=\begin{cases}D_{G}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]&\text{if
}a\in R\text{ and }b\in R^{\prime},\\\ 0&\text{otherwise.}\end{cases}$
$\displaystyle T_{X}^{\square}[a,b]$
$\displaystyle=\begin{cases}2\phantom{{}_{G}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]\;}&\text{if
}a=\mathsf{xi}(\pi,x)\text{ and }b=\mathsf{xi}(\pi^{\prime},x)\text{ for some
}x\in\mkern 1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu,\\\
0&\text{otherwise.}\end{cases}$ $\displaystyle T_{Y}^{\square}[a,b]$
$\displaystyle=\begin{cases}2\phantom{{}_{G}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]\;}&\text{if
}a=\mathsf{yi}(\pi,y)\text{ and }b=\mathsf{yi}(\pi^{\prime},y)\text{ for some
}y\in\mkern 1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu,\\\
0&\text{otherwise.}\end{cases}$

###### Proof.

If $a\in R$ and $b\in R^{\prime}$, then
$\mathsf{rk}_{R}(a+1)=\mathsf{rk}_{R}(a)+1$ and
$\mathsf{rk}_{R^{\prime}}(b+1)=\mathsf{rk}_{R^{\prime}}(b)+1$, so
$T_{\widetilde{G}}^{\square}[a,b]=D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a)+1,\mathsf{rk}_{R^{\prime}}(b)]+D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)+1]-D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]-D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a)+1,\mathsf{rk}_{R^{\prime}}(b)+1]=D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]$.
If $a\notin R$, then $\mathsf{rk}_{R}(a+1)=\mathsf{rk}_{R}(a)$, so
$T_{\widetilde{G}}^{\square}[a,b]=D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]+D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b+1)]-D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b)]-D_{\widetilde{G}}^{\square}[\mathsf{rk}_{R}(a),\mathsf{rk}_{R^{\prime}}(b+1)]=0$.
Finally, if $b\notin R^{\prime}$, then
$\mathsf{rk}_{R^{\prime}}(b+1)=\mathsf{rk}_{R^{\prime}}(b)$, which
symmetrically yields $T_{\widetilde{G}}^{\square}[a,b]=0$.

Next, observe that if $\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a})\geq\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu}(x^{\prime}_{b+1})$,
then $T_{X}^{\square}[a,b]=(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a+1})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b}))+(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b+1}))-(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b}))-(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a+1})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu}(x^{\prime}_{b+1}))=0$.
Symmetrically, if $\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b})\geq\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu}(x_{a+1})$, then
$T_{X}^{\square}[a,b]=(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a+1}))+(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b+1})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a}))-(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a}))-(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b+1})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu}(x_{a+1}))=0$. In the
remaining case, we have $\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a})<\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b+1})\leq\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b})+1<\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a+1})+1\leq\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu}(x_{a})+2$. Since all
the ranks are integers, this yields $\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a+1})=\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x_{a})+1=\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu}(x^{\prime}_{b})+1=\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu}(x^{\prime}_{b+1})$.
Consequently, $a=\mathsf{xi}(\pi,x_{a})$,
$b=\mathsf{xi}(\pi^{\prime},x^{\prime}_{b})$, and
$x_{a}=x^{\prime}_{b}\in\mkern 1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu$. In this case, we have $T_{X}^{\square}[a,b]=1+1-0-0=2$, as claimed.

Finally, observe that if $\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b})\leq\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y_{a+1})$, then
$T_{Y}^{\square}[a,b]=(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a+1})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b}))+(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b+1}))-(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b}))-(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a+1})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y^{\prime}_{b+1}))=0$.
Symmetrically, if $\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a})\leq\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y^{\prime}_{b+1})$,
then $T_{Y}^{\square}[a,b]=(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a+1}))+(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b+1})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a}))-(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a}))-(\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b+1})-\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y_{a+1}))=0$. In the
remaining case, we have $\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a})>\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b+1})\geq\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b})-1>\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a+1})-1\geq\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y_{a})+2$. Since all
the ranks are integers, this yields $\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a+1})=\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y_{a})-1=\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu}(y^{\prime}_{b})-1=\mathsf{rk}_{\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu}(y^{\prime}_{b+1})$.
Consequently, $a=\mathsf{yi}(\pi,y_{a+1})$,
$b=\mathsf{yi}(\pi^{\prime},y^{\prime}_{b+1})$, and
$y_{a+1}=y^{\prime}_{b+1}\in\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu$. In this case, we have
$T_{Y}^{\square}[a,b]=1+1-0-0=2$, as claimed. ∎

26 completes the proof due to
$P_{G}=\frac{1}{2}D_{G}^{\square}=\frac{1}{2}(T_{\widetilde{G}}^{\square}+T_{X}^{\square}+T_{Y}^{\square})$
and $P_{\widetilde{G}}=\frac{1}{2}D_{\widetilde{G}}^{\square}$. ∎

Next, we develop an algorithmic counterpart of Lemma 24.

######  Lemma 27.

Let $G=\mathsf{SAG}^{n,m}(\pi,\pi^{\prime},S)$ be a slice alignment graph, let
$X\subseteq[0\mathinner{.\,.}n)$ and $Y\subseteq[0\mathinner{.\,.}m)$ be such
that $S\subseteq X\times Y$, and let
$\widetilde{G}=\mathsf{SAG}^{|X|,|Y|}(\mathsf{d}_{X,Y}(\pi),\mathsf{d}_{X,Y}(\pi^{\prime}),\\{\mathsf{d}_{X,Y}(p):p\in
S\\})$. Given the cut-paths $\pi,\pi^{\prime}$, the sets $X,Y$, and the
permutation representing $P_{\widetilde{G}}$, the permutation representing
$P_{G}$ can be constructed in $O(n+m)$ time.

###### Proof.

Let $\sigma:[0\mathinner{.\,.}n+m)\to[0\mathinner{.\,.}n+m)$ be the
permutation underlying $P_{G}$ and let
$\widetilde{\sigma}:[0\mathinner{.\,.}|X|+|Y|)\to[0\mathinner{.\,.}|X|+|Y|)$
be the permutation underlying $P_{\widetilde{G}}$. By Lemma 24, we have
$\sigma(\mathsf{xi}(\pi,\mkern 1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern
1.0mu))=\mathsf{xi}(\pi^{\prime},\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu)$ for $\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu\in\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern 1.0mu$ and
$\sigma(\mathsf{yi}(\pi,\mkern 1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern
1.0mu))=\mathsf{yi}(\pi^{\prime},\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu)$ for $\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu\in\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern 1.0mu$. In order to fill these
values of $\sigma$, we just need to construct the functions
$\mathsf{xi}(\pi,\cdot),\mathsf{xi}(\pi^{\prime},\cdot):[0\mathinner{.\,.}n)\to[0\mathinner{.\,.}n+m)$
and
$\mathsf{yi}(\pi,\cdot),\mathsf{yi}(\pi^{\prime},\cdot):[0\mathinner{.\,.}m)\to[0\mathinner{.\,.}n+m)$.
By the characterization of Observation 22, $\mathsf{xi}(\pi,\cdot)$ and
$\mathsf{yi}(\pi,\cdot)$ can be constructed by scanning $\pi$. An analogous
scan of $\pi^{\prime}$ yields $\mathsf{yi}(\pi^{\prime},\cdot)$ and
$\mathsf{yi}(\pi^{\prime},\cdot)$.

The first phase of the algorithm thus results in the values of $\sigma$ for
arguments in $\\{\mathsf{xi}(\pi,\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu):\mkern
1.0mu\overline{\mkern-1.0mux\mkern-1.0mu}\mkern 1.0mu\in\mkern
1.0mu\overline{\mkern-1.0muX\mkern-1.0mu}\mkern
1.0mu\\}\cup\\{\mathsf{yi}(\pi,\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu):\mkern
1.0mu\overline{\mkern-1.0muy\mkern-1.0mu}\mkern 1.0mu\in\mkern
1.0mu\overline{\mkern-1.0muY\mkern-1.0mu}\mkern
1.0mu\\}=[0\mathinner{.\,.}n+m]\setminus R$. In the second phase, will
retrieve from $\widetilde{\sigma}$ the values of $\sigma$ for arguments in
$R$. By Lemma 24, for every $a,b\in[0\mathinner{.\,.}|X|+|Y|]$, we have
$P_{\widetilde{G}}[a,b]=P_{G}[r_{a},r^{\prime}_{b}]$, where
$r_{0},\ldots,r_{|X|+|Y|}$ are the elements of $R$ in the increasing order and
$r^{\prime}_{0},\ldots,r^{\prime}_{|X|+|Y|}$ are the elements of $R^{\prime}$
in the increasing order. In particular,
$\sigma(r_{a})=r^{\prime}_{\widetilde{\sigma}(a)}$ for every