# Vertebrate interval graphs

Rain Jiang  Kai Jiang  Minghui Jiang
Home School, USA  dr.minghui.jiang at gmail.com

###### Abstract

A vertebrate interval graph is an interval graph in which the maximum size of
a set of independent vertices equals the number of maximal cliques. For any
fixed $v\geq 1$, there is a polynomial-time algorithm for deciding whether a
vertebrate interval graph admits a vertex partition into two induced subgraphs
with claw number at most $v$. In particular, when $v=2$, whether a vertebrate
interval graph can be partitioned into two proper interval graphs can be
decided in polynomial time.

##  1 Introduction

In any graph, the maximum size of a set of independent vertices is at most the
number of maximal cliques. It is natural to consider graphs with the property
that these two numbers are equal. Golumbic [7] noted that “we cannot expect to
discover much about the structure” of graphs with this property alone, and
instead defined _trivially perfect graphs_ as graphs with the stronger,
hereditary property that the maximum size of a set of independent vertices
equals the number of maximal cliques in every induced subgraph.

Trivially perfect graphs are also known as comparability graphs of trees, and
as intersection graphs of nested intervals. An _interval graph_ is the
intersection graph of a family of open intervals. A trivially perfect graph is
an interval graph with an interval representation in which no interval
partially overlaps another interval.

Figure 1: Left: intervals representing a trivially perfect graph. Middle:
intervals representing a vertebrate interval graph. Right: intervals
representing an invertebrate interval graph.

In this paper, we introduce _vertebrate interval graphs_ as a subclass of
interval graphs and a superclass of trivially perfect graphs. Specifically, an
interval graph is _vertebrate_ if the maximum size of a set of independent
vertices equals the number of maximal cliques in the graph, and is
_invertebrate_ otherwise. Here the equality of the two numbers for a
vertebrate interval graph is not hereditary: it holds for the graph as a
whole, but not necessarily for its induced subgraphs. Refer to Figure 1 for
some examples.

The _claw number_ $\psi(G)$ of a graph $G$ is the largest number $v\geq 0$
such that $G$ contains $K_{1,v}$ as an induced subgraph [2]. In particular, a
graph with claw number $0$ is an empty graph with no edges. A graph with claw
number at most $1$ is a disjoint union of cliques, also known as a _cluster
graph_. Every cluster graph is clearly also an interval graph, with claw
number at most $1$. A _proper interval graph_ is the intersection graph of a
family of open intervals in which no one properly contains another. A _unit
interval graph_ is the intersection graph of a family of open intervals of the
same length. It is well-known [4] that an interval graph is a proper interval
graph if and only if it is a unit interval graph, and if and only if it does
not contain $K_{1,3}$ as an induced subgraph. Thus a proper / unit interval
graph is an interval graph of claw number at most $2$.

A _$k$ -partition_ of a graph refers to a partition of its vertices into $k$
subsets, and the resulting $k$ vertex-disjoint induced subgraphs. For $k\geq
2$ and $v\geq 1$, $k$-Partition$(v)$ is the problem of deciding whether a
given graph admits a vertex partition into $k$ induced subgraphs with claw
number at most $v$. Certain generic results on vertex-partitioning [1, 6]
imply that $k$-Partition$(v)$ in general graphs is NP-hard for all $k\geq 2$
and $v\geq 1$.

The subchromatic number of a graph is the smallest number $k$ such that the
graph admits a $k$-partition into cluster graphs [3]. For any fixed $k$,
whether an interval graph with $n$ vertices has subchromatic number at most
$k$ can be decided in $O(k\cdot n^{2k+1})$ time [5, Theorem 5.4]. Thus for
$k\geq 2$, $k$-Partition$(1)$ in interval graphs admits an algorithm running
in $O(k\cdot n^{2k+1})$ time. It is unknown [9] whether there exist $k\geq 2$
and $v\geq 2$ such that $k$-Partition$(v)$ in interval graphs admits an
polynomial-time algorithm.

In this paper, we show that vertebrate interval graphs have sufficient
“structure” so that $2$-Partition$(v)$ can be solved in polynomial time for
all $v\geq 1$:

######  Theorem 1.

For $v\geq 1$, $2$-Partition$(v)$ in vertebrate interval graphs admits an
algorithm running in $2^{O(v^{2})}n^{O(v)}$ time.

In particular, for $v=2$, whether a vertebrate interval graph admits a vertex
partition into two proper interval graphs can be decided in polynomial time.

##  2 Preliminaries

Denote by $m(G)$ the number of maximal cliques in a graph $G$. Besides $m(G)$
and the claw number $\psi(G)$ mentioned earlier, there are two other common
graph parameters. An _independent set_ (respectively, a _clique_) is a set of
pairwise non-adjacent (respectively, adjacent) vertices in a graph. The
_independence number_ $\alpha(G)$ is the maximum number of vertices in an
independent set in $G$. The _vertex-clique-partition number_ $\vartheta(G)$ is
the minimum number of parts in a vertex partition of $G$ into cliques.

It is easy to see that for any graph $G$,
$\psi(G)\leq\alpha(G)\leq\vartheta(G)\leq m(G)$. If $G$ is an interval graph,
then $\alpha(G)=\vartheta(G)$ [8]. By our definition,
$\alpha(G)=\vartheta(G)=m(G)$ for any vertebrate interval graph $G$.

The equality $\alpha(G)=\vartheta(G)$ for every interval graph $G$ has a
simple constructive proof. Recall that interval graphs can be recognized in
linear time [8]. Let $\mathcal{I}$ be any family of open intervals whose
intersection graph is $G$. Assume without loss of generality that all
endpoints of intervals in $\mathcal{I}$ are integers. We can find an
independent set and a vertex clique partition at the same time by a standard
_sweepline algorithm_ :

> Initialize $\mathcal{I}^{\prime}\leftarrow\mathcal{I}$ and $i\leftarrow 1$.
> While $\mathcal{I}^{\prime}$ is not empty, let $T_{i}=(l_{i},r_{i})$ be an
> interval in $\mathcal{I}^{\prime}$ whose right endpoint $r_{i}$ is minimum,
> let $\mathcal{I}^{\prime}_{i}$ (respectively, $\mathcal{I}_{i}$) be the
> subfamily of intervals in $\mathcal{I}^{\prime}$ (respectively,
> $\mathcal{I}$) that contain the subinterval $S_{i}=(r_{i}-1,r_{i})$ of
> $T_{i}$, then update
> $\mathcal{I}^{\prime}\leftarrow\mathcal{I}^{\prime}\setminus\mathcal{I}^{\prime}_{i}$
> and $i\leftarrow i+1$.

Let $m$ be the maximum round $i$ such that $\mathcal{I}^{\prime}$ is not
empty. Then $S_{i}\subseteq
T_{i}\in\mathcal{I}^{\prime}_{i}\subseteq\mathcal{I}_{i}$ for $1\leq i\leq m$.
Note that the $m$ intervals $T_{i}$ correspond to an independent set in $G$,
and that the $m$ subfamilies $\mathcal{I}^{\prime}_{i}$ correspond to a
partition of the vertices of $G$ into cliques. So we have
$\alpha(G)=\vartheta(G)=m$. Moreover, if $G$ is a vertebrate interval graph,
then $\alpha(G)=\vartheta(G)=m(G)=m$, and the $m$ subfamilies
$\mathcal{I}_{i}$ correspond to the $m$ maximal cliques in $G$, which cover
all vertices and all edges.

After running the sweepline algorithm on an arbitrary interval representation
$\mathcal{I}$ of a vertebrate interval graph $G$, we can then obtain a
possibly more compact interval representation $\mathcal{J}$ of $G$, by
converting each interval $I\in\mathcal{I}$ to an interval $J\in\mathcal{J}$ as
follows. Suppose that $a$ and $b$, respectively, are the smallest and largest
integers $i$, $1\leq i\leq m$, such that $I\in\mathcal{I}_{i}$. Then
$I\in\mathcal{I}_{i}$ if and only if $a\leq i\leq b$. Let $J=(a-1,b)$.

Note that all intervals in $\mathcal{J}$ have integer endpoints in $[0,m]$.
Moreover, for each interval $I\in\mathcal{I}$, the length of the corresponding
interval $J\in\mathcal{J}$ is equal to the number of maximal cliques
$\mathcal{I}_{i}$ such that $I\in\mathcal{I}_{i}$. In particular, each
interval $T_{i}\in\mathcal{I}$ corresponds to a unit interval
$T^{\prime}_{i}=(i-1,i)$ in $\mathcal{J}$, and each interval $J\in\mathcal{J}$
of length $\ell\geq 2$ is the concatenation of $\ell$ disjoint unit intervals
$T^{\prime}_{i}$ in $\mathcal{J}$. It is easy to verify that $\mathcal{I}$ and
$\mathcal{J}$ represent the same graph $G$.

Let $\mathcal{U}$ be the subfamily of $m$ unit intervals $T^{\prime}_{i}$ in
$\mathcal{J}$. We call $\mathcal{J}$ a _vertebrate representation_ of $G$, and
call $\mathcal{U}$ the _backbone_ of $\mathcal{J}$. Because of the unit
intervals composing the backbone, the maximum length of an interval in
$\mathcal{J}$ is exactly $\psi(G)$. In summary, we have the following
proposition:

######  Proposition 1.

Every vertebrate interval graph $G$ has an interval representation
$\mathcal{J}$ with integer endpoints in $[0,m(G)]$ and with maximum interval
length $\psi(G)$, which includes the $m(G)$ unit intervals $(i-1,i)$ for
$1\leq i\leq m(G)$.

##  3 Algorithm for $2$-Partition$(v)$ in vertebrate interval graphs

In this section we prove Theorem 1. Fix any $v\geq 1$. We will present a
polynomial-time algorithm for $2$-Partition$(v)$ based on dynamic programming.

Let $G$ be a vertebrate interval graph with $n$ vertices. Obtain a vertebrate
representation $\mathcal{J}$ of $G$ with integer endpoints in $[0,m]$, where
$m=m(G)$ is the number of maximal cliques in $G$. Let
$\mathcal{U}\subseteq\mathcal{J}$ be the subfamily of $m$ disjoint unit
intervals $(i-1,i)$, $1\leq i\leq m$, forming the backbone.

We say that a family of intervals is _good_ if it represents an interval graph
with claw number at most $v$, and that a $2$-partition of a family of
intervals is _good_ if each part is good. For any two subfamilies
$\mathcal{R}$ and $\mathcal{S}$ of $\mathcal{J}$, we write
$\mathcal{R}\mid\mathcal{S}$ if each interval in $\mathcal{R}$ intersects at
most $v$ disjoint intervals in $\mathcal{S}$ other than itself. Then a
$2$-partition $(\mathcal{P},\mathcal{Q})$ of $\mathcal{J}$ is good if and only
if $\mathcal{P}\mid\mathcal{P}$ and $\mathcal{Q}\mid\mathcal{Q}$.

For any good $2$-partition of $\mathcal{J}$, if there are two duplicate
intervals in different parts, then we can always relocate them to the same
part while keeping the $2$-partition good. Thus we can assume without loss of
generality that $\mathcal{J}$ includes no duplicates.

###  3.1 Basic properties of good $2$-partitions

For any subfamily $\mathcal{S}$ of $\mathcal{J}$, denote by
$\mathcal{S}_{\leq}$ the subfamily of intervals in $\mathcal{S}$ of length at
most $v$, and by $\mathcal{S}_{>}$ the subfamily of intervals in $\mathcal{S}$
of length greater than $v$. For $0\leq l\leq r\leq m$, denote by
$\mathcal{S}(l,r)$ the subfamily of intervals in $\mathcal{S}$ that are
contained in the interval $(l,r)$. In particular, when $l=r$, both $(l,r)$ and
$\mathcal{S}(l,r)$ are empty. We write
$(\mathcal{P},\mathcal{Q})\succ\mathcal{S}$ if $(\mathcal{P},\mathcal{Q})$ is
a $2$-partition of $\mathcal{S}$. We say that
$(\mathcal{P},\mathcal{Q})\succ\mathcal{S}$ is _simple_ if either
$(\mathcal{P},\mathcal{Q})=(\mathcal{S}_{\leq},\mathcal{S}_{>})$ or
$(\mathcal{P},\mathcal{Q})=(\mathcal{S}_{>},\mathcal{S}_{\leq})$.

For any two subfamilies $\mathcal{R}$ and $\mathcal{S}$ of $\mathcal{J}$, we
say that two $2$-partitions
$(\mathcal{R}_{1},\mathcal{R}_{2})\succ\mathcal{R}$ and
$(\mathcal{S}_{1},\mathcal{S}_{2})\succ\mathcal{S}$ are _consistent_ if
$(\mathcal{R}_{1}\cup\mathcal{S}_{1},\mathcal{R}_{2}\cup\mathcal{S}_{2})\succ\mathcal{R}\cup\mathcal{S}$,
and write
$(\mathcal{R}_{1},\mathcal{R}_{2})\simeq(\mathcal{S}_{1},\mathcal{S}_{2})$.
For $\mathcal{R}\subseteq\mathcal{S}$, and for any $2$-partition
$(\mathcal{P},\mathcal{Q})\succ\mathcal{S}$, the $2$-partition
$(\mathcal{P}\cap\mathcal{R},\mathcal{Q}\cap\mathcal{R})\succ\mathcal{R}$ is
called the _derived_ $2$-partition of $\mathcal{R}$. Clearly, if
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ is derived from
$(\mathcal{P},\mathcal{Q})$, then
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})\simeq(\mathcal{P},\mathcal{Q})$.

For $0\leq l<r\leq s\leq m$, the interval $(l,r)$ is a _vertebrate range_ for
some $2$-partition of $\mathcal{J}(0,s)$ if the $r-l$ unit intervals in
$\mathcal{U}(l,r)$ are all in the same part. A $2$-partition of
$\mathcal{J}(0,s)$ is _basic_ if for every maximal vertebrate range $(l,r)$,
the derived $2$-partition of $\mathcal{J}(l,r)$ is simple.

######  Lemma 1.

$\mathcal{J}$ has a good $2$-partition if and only if it has a good basic
$2$-partition.

###### Proof.

Given any good $2$-partition of $\mathcal{J}$ that is not basic, we can
transform it into a good basic $2$-partition as follows. Let $(l,r)$ be a
maximal vertebrate range, such that the $r-l$ unit intervals in
$\mathcal{J}(l,r)$ are in the same part. Then the intervals of length greater
than $v$ in $\mathcal{J}(l,r)$, if any, must be in the other part. For each
interval $I$ of length at most $v$ in $\mathcal{J}(l,r)$, we simply move it to
the same part as the unit intervals if it is not already there. We claim that
this move does not introduce any star $K_{1,v+1}$. First, $I$ cannot be the
center of any star $K_{1,v+1}$, since any interval of length at most $v$
intersects at most $v$ disjoint intervals in $\mathcal{J}$. Second, if there
is a star $K_{1,v+1}$ with $I$ as a leaf after the move, then there would have
been a star $K_{1,v+1}$ even before the move, with $I$ replaced by some unit
interval contained in $I$. ∎

For any subfamily $\mathcal{S}$ of $\mathcal{J}$, and for $0\leq l\leq r\leq
m$, denote by $\alpha(\mathcal{S},l,r)$ the maximum size of a subfamily of
disjoint intervals in $\mathcal{S}$ that intersect the interval $(l,r)$. In
particular, when $l=r$, $(l,r)$ is empty, and hence
$\alpha(\mathcal{S},l,r)=0$. Note that $\alpha(\mathcal{S},l,r)$ is not
necessarily equal to $\alpha(\mathcal{S}(l,r),l,r)$.

######  Lemma 2.

For $0\leq a<s<b\leq m$, if $(\mathcal{P},\mathcal{Q})$ is a $2$-partition of
$\mathcal{J}$ with $(s-1,s)\in\mathcal{P}$ and $(s,s+1)\in\mathcal{Q}$, then
$\alpha(\mathcal{P},a,b)=\alpha(\mathcal{P}(0,s),a,s)+\alpha(\mathcal{P}(s,m),s,b)$
and
$\alpha(\mathcal{Q},a,b)=\alpha(\mathcal{Q}(0,s),a,s)+\alpha(\mathcal{Q}(s,m),s,b)$.

###### Proof.

Consider any subfamily of disjoint intervals in $\mathcal{J}$ that intersect
$(a,b)$, from the same part $\mathcal{P}$ or $\mathcal{Q}$. If this subfamily
contains an interval $(c,d)$ with $c<s<d$, then we can replace it by $(s-1,s)$
or $(s,s+1)$. ∎

For $0\leq s\leq m$, a sequence $\boldsymbol{r}=\langle
r_{0},r_{1},\ldots,r_{v},r_{v+1},r_{v+2}\rangle$ of $v+3$ integers is _$s$
-monotonic_ if

$-1=r_{v+2}\leq r_{v+1}\leq r_{v}\leq\ldots\leq r_{1}\leq r_{0}=s,$

and moreover, either $-1=r_{u+1}=r_{u}$ or $r_{u+1}<r_{u}$ holds for each $u$,
$0\leq u\leq v+1$. Denote by $\boldsymbol{0}$ the unique $0$-monotonic
sequence $\langle 0,-1,\ldots,-1\rangle$.

For $0\leq u\leq v+2$ and $0\leq s\leq m$, and for a subfamily $\mathcal{R}$
of $\mathcal{J}(0,s)$, let $i(\mathcal{R},u,s)$ be the maximum index
$i\in[0,s]$ such that $u\leq\alpha(\mathcal{R},i,s)\leq v+1$, or $-1$ if such
an index $i$ does not exist. Clearly, we always have $i(\mathcal{R},0,s)=s$
and $i(\mathcal{R},v+2,s)=-1$. Also, $i(\mathcal{R},u,s)=-1$ for
$u>\alpha(\mathcal{R},0,s)$. For $1\leq
u\leq\min\\{\alpha(\mathcal{R},0,s),v+1\\}$, we have
$i(\mathcal{R},u,s)\in[0,s]$ and $\alpha(\mathcal{R},i(\mathcal{R},u,s),s)=u$.

For $0\leq s\leq m$, we say that an $s$-monotonic sequence $\boldsymbol{r}$
_encodes_ a subfamily $\mathcal{R}$ of $\mathcal{J}(0,s)$ if
$r_{u}=i(\mathcal{R},u,s)$ for $0\leq u\leq v+2$. By definition, every
subfamily of $\mathcal{J}(0,s)$ is encoded by an $s$-monotonic sequence. If
$\boldsymbol{r}$ encodes $\mathcal{R}$, that is, if $r_{u}=i(\mathcal{R},u,s)$
for $0\leq u\leq v+2$, then from $\boldsymbol{r}$ we can recover the values of
$\alpha(\mathcal{R},i,s)$ relative to $v+1$ for all $0\leq i\leq s$ as
follows:

$\begin{array}[]{ll}\alpha(\mathcal{R},i,s)=u&\textrm{when }r_{u+1}<i\leq
r_{u}\textrm{ for }0\leq u\leq v,\\\ \alpha(\mathcal{R},i,s)\geq
v+1&\textrm{when }r_{v+2}<i\leq r_{v+1}.\end{array}$

For $0\leq i\leq s\leq m$, and for an $s$-monotonic sequence $\boldsymbol{r}$,
denote by $\alpha(\boldsymbol{r},i,s)$ the maximum index $u\in[0,v+1]$ such
that $i\leq r_{u}$. Then we immediately have the following lemma:

######  Lemma 3.

For $0\leq s\leq m$, if an $s$-monotonic sequence $\boldsymbol{r}$ encodes a
subfamily $\mathcal{R}$ of $\mathcal{J}(0,s)$, then for $0\leq i\leq s$,
either $\alpha(\mathcal{R},i,s)=\alpha(\boldsymbol{r},i,s)\in[0,v]$, or
$\alpha(\mathcal{R},i,s)\geq\alpha(\boldsymbol{r},i,s)=v+1$.

For $0\leq s\leq m$, we say that a pair of $s$-monotonic sequences
$(\boldsymbol{p},\boldsymbol{q})$ _encodes_ a $2$-partition
$(\mathcal{P},\mathcal{Q})\succ\mathcal{J}(0,s)$ if $\boldsymbol{p}$ encodes
$\mathcal{P}$ and $\boldsymbol{q}$ encodes $\mathcal{Q}$.

For $0\leq s\leq m$, denote by $\mathcal{K}_{s}$ the subfamily of intervals
$(a,b)$ in $\mathcal{J}$ with $a<s<b$. Note that the $m$ unit intervals in
$\mathcal{U}$ are the only intervals in $\mathcal{J}$ that are not included in
any $\mathcal{K}_{s}$. For $0\leq s^{\prime}<s\leq m$,
$\mathcal{J}(0,s)=\mathcal{J}(0,s^{\prime})\cup(\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s})\cup\mathcal{J}(s^{\prime},s)$.
We say that a pair of $s$-monotonic sequences
$(\boldsymbol{p},\boldsymbol{q})$ _extends_ a pair of $s^{\prime}$-monotonic
sequences $(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ by a
$2$-partition
$(\mathcal{E},\mathcal{F})\succ\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$
if, with the simple $2$-partition
$(\mathcal{C},\mathcal{D})=(\mathcal{J}_{\leq}(s^{\prime},s),\mathcal{J}_{>}(s^{\prime},s))\succ\mathcal{J}(s^{\prime},s)$,
and with $w=\alpha(\mathcal{D},s^{\prime},s)$ and
$w^{\prime}=\alpha(\mathcal{F}\cup\mathcal{D},s^{\prime},s)$,

$\displaystyle p_{u}$
$\displaystyle=\left\\{\begin{array}[]{ll}s-u&\quad\textrm{for }1\leq
u\leq\min\\{s-s^{\prime},v+1\\},\\\
p^{\prime}_{u-s+s^{\prime}}&\quad\textrm{for }s-s^{\prime}<u\leq
v+1,\end{array}\right.$ $\displaystyle q_{u}$
$\displaystyle=\left\\{\begin{array}[]{ll}i(\mathcal{F}\cup\mathcal{D},u,s)&\quad\textrm{for
}1\leq u\leq\min\\{w^{\prime},v+1\\},\\\ q^{\prime}_{u-w}&\quad\textrm{for
}w^{\prime}<u\leq v+1.\end{array}\right.$

Note that if $(\boldsymbol{p},\boldsymbol{q})$ extends
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ by
$(\mathcal{E},\mathcal{F})$, then $(\boldsymbol{p},\boldsymbol{q})$ is
uniquely determined by $(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ and
$(\mathcal{E},\mathcal{F})$.

The following lemma shows that basic $2$-partitions have a sequential
structure with respect to maximal vertebrate ranges:

######  Lemma 4.

Let $0\leq s^{\prime}<s\leq m$. Suppose that

  * •

$(\mathcal{P},\mathcal{Q})$ is a basic $2$-partition of $\mathcal{J}(0,s)$
with $(s^{\prime},s)$ as the rightmost maximal vertebrate range,

  * •

$(\mathcal{C},\mathcal{D})=(\mathcal{J}_{\leq}(s^{\prime},s),\mathcal{J}_{>}(s^{\prime},s))$
is the simple $2$-partition of $\mathcal{J}(s^{\prime},s)$ derived from
$(\mathcal{P},\mathcal{Q})$,

  * •

$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ is the basic $2$-partition of
$\mathcal{J}(0,s^{\prime})$ derived from $(\mathcal{P},\mathcal{Q})$,

  * •

$(\mathcal{E},\mathcal{F})=(\mathcal{P}\setminus(\mathcal{P}^{\prime}\cup\mathcal{C}),\mathcal{Q}\setminus(\mathcal{Q}^{\prime}\cup\mathcal{D}))$
is the $2$-partition of $\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$
derived from $(\mathcal{P},\mathcal{Q})$,

  * •

$(\boldsymbol{p},\boldsymbol{q})$ is a pair of $s$-monotonic sequences
encoding $(\mathcal{P},\mathcal{Q})$,

  * •

$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ is a pair of
$s^{\prime}$-monotonic sequences encoding
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$.

Then $(\boldsymbol{p},\boldsymbol{q})$ extends
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ by
$(\mathcal{E},\mathcal{F})$.

###### Proof.

Since
$\mathcal{U}(s^{\prime},s)\subseteq\mathcal{J}_{\leq}(s^{\prime},s)=\mathcal{C}\subseteq\mathcal{P}$,
we must have $\alpha(\mathcal{P},s^{\prime},s)=s-s^{\prime}$, and moreover,

$\begin{array}[]{ll}i(\mathcal{P},u,s)=s-u&\textrm{for }1\leq
u\leq\min\\{s-s^{\prime},v+1\\},\\\ i(\mathcal{P},u,s)<s^{\prime}&\textrm{for
}s-s^{\prime}<u\leq v+1.\end{array}$

Note that all intervals in
$\mathcal{Q}=\mathcal{Q}^{\prime}\cup\mathcal{F}\cup\mathcal{D}$ that
intersect $(s^{\prime},s)$ are in $\mathcal{F}\cup\mathcal{D}$. Thus
$\alpha(\mathcal{Q},i,s)=\alpha(\mathcal{F}\cup\mathcal{D},i,s)$ for
$s^{\prime}\leq i\leq s$. Since
$\alpha(\mathcal{F}\cup\mathcal{D},s^{\prime},s)=w^{\prime}$, it follows that
for $u\leq\min\\{w^{\prime},v+1\\}$, $i(\mathcal{F}\cup\mathcal{D},u,s)\geq
s^{\prime}$, and hence $i(\mathcal{Q},u,s)=i(\mathcal{F}\cup\mathcal{D},u,s)$.
Thus,

$\begin{array}[]{ll}i(\mathcal{Q},u,s)=i(\mathcal{F}\cup\mathcal{D},u,s)&\textrm{for
}1\leq u\leq\min\\{w^{\prime},v+1\\},\\\
i(\mathcal{Q},u,s)<s^{\prime}&\textrm{for }w^{\prime}<u\leq v+1.\end{array}$

We next elaborate on the two inequalities, $i(\mathcal{P},u,s)<s^{\prime}$ for
$s-s^{\prime}<u\leq v+1$, and $i(\mathcal{Q},u,s)<s^{\prime}$ for
$w^{\prime}<u\leq v+1$, by considering two cases.

Case 1: $s^{\prime}=0$. Then we must have $i(\mathcal{P},u,s)=-1$ for
$s-s^{\prime}<u\leq v+1$, and $i(\mathcal{Q},u,s)=-1$ for $w^{\prime}<u\leq
v+1$. On the other hand, since $(0,s^{\prime})$ is empty, we have
$\mathcal{P}^{\prime}=\mathcal{Q}^{\prime}=\emptyset$. For $s-s^{\prime}<u\leq
v+1$, we have $u-s+s^{\prime}>0$, and hence
$i(\mathcal{P}^{\prime},u-s+s^{\prime},s^{\prime})=-1$. Also, for
$w^{\prime}<u\leq v+1$, we have $u-w^{\prime}>0$. Since
$w=\alpha(\mathcal{D},s^{\prime},s)\leq\alpha(\mathcal{F}\cup\mathcal{D},s^{\prime},s)=w^{\prime}$,
it follows that $u-w>0$, and hence
$i(\mathcal{Q}^{\prime},u-w,s^{\prime})=-1$. Therefore,

$\begin{array}[]{ll}i(\mathcal{P},u,s)=-1=i(\mathcal{P}^{\prime},u-s+s^{\prime},s^{\prime})&\textrm{for
}s-s^{\prime}<u\leq v+1,\\\
i(\mathcal{Q},u,s)=-1=i(\mathcal{Q}^{\prime},u-w,s^{\prime})&\textrm{for
}w^{\prime}<u\leq v+1.\end{array}$

Case 2: $s^{\prime}>0$. Since $(s^{\prime},s)$ is the rightmost maximal
vertebrate range of $(\mathcal{P},\mathcal{Q})\succ\mathcal{J}(0,s)$ with
$\mathcal{U}(s^{\prime},s)\subseteq\mathcal{C}\subseteq\mathcal{P}$, we have
$(s^{\prime}-1,s^{\prime})\in\mathcal{Q}$ and
$(s^{\prime},s^{\prime}+1)\in\mathcal{P}$. For $0\leq i<s^{\prime}<s\leq m$,
it then follows by Lemma 2 that

$\displaystyle\alpha(\mathcal{P},i,s)$
$\displaystyle=\alpha(\mathcal{P}(0,s^{\prime}),i,s^{\prime})+\alpha(\mathcal{P}(s^{\prime},s),s^{\prime},s)=\alpha(\mathcal{P}^{\prime},i,s^{\prime})+\alpha(\mathcal{C},s^{\prime},s),$
$\displaystyle\alpha(\mathcal{Q},i,s)$
$\displaystyle=\alpha(\mathcal{Q}(0,s^{\prime}),i,s^{\prime})+\alpha(\mathcal{Q}(s^{\prime},s),s^{\prime},s)=\alpha(\mathcal{Q}^{\prime},i,s^{\prime})+\alpha(\mathcal{D},s^{\prime},s).$

Since $\alpha(\mathcal{C},s^{\prime},s)=s-s^{\prime}$ and
$\alpha(\mathcal{D},s^{\prime},s)=w$, we have

$\displaystyle\alpha(\mathcal{P},i,s)$
$\displaystyle=\alpha(\mathcal{P}^{\prime},i,s^{\prime})+s-s^{\prime},$
$\displaystyle\alpha(\mathcal{Q},i,s)$
$\displaystyle=\alpha(\mathcal{Q}^{\prime},i,s^{\prime})+w,$

which implies that

$\begin{array}[]{ll}i(\mathcal{P},u,s)=i(\mathcal{P}^{\prime},u-s+s^{\prime},s^{\prime})&\textrm{for
}s-s^{\prime}<u\leq v+1,\\\
i(\mathcal{Q},u,s)=i(\mathcal{Q}^{\prime},u-w,s^{\prime})&\textrm{for }w<u\leq
v+1.\end{array}$

In particular, since $w\leq w^{\prime}$, we have

$\begin{array}[]{ll}i(\mathcal{P},u,s)=i(\mathcal{P}^{\prime},u-s+s^{\prime},s^{\prime})&\textrm{for
}s-s^{\prime}<u\leq v+1,\\\
i(\mathcal{Q},u,s)=i(\mathcal{Q}^{\prime},u-w,s^{\prime})&\textrm{for
}w^{\prime}<u\leq v+1.\end{array}$

Since $(\boldsymbol{p},\boldsymbol{q})$ encodes $(\mathcal{P},\mathcal{Q})$
and $(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ encodes
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$, it follows that for $1\leq
u\leq v+1$,

$p_{u}=i(\mathcal{P},u,s),\quad q_{u}=i(\mathcal{Q},u,s),\quad
p^{\prime}_{u}=i(\mathcal{P}^{\prime},u,s),\quad
q^{\prime}_{u}=i(\mathcal{Q}^{\prime},u,s).$

In summary, we have proved that

$\displaystyle p_{u}$
$\displaystyle=\left\\{\begin{array}[]{ll}s-u&\quad\textrm{for }1\leq
u\leq\min\\{s-s^{\prime},v+1\\},\\\
p^{\prime}_{u-s+s^{\prime}}&\quad\textrm{for }s-s^{\prime}<u\leq
v+1,\end{array}\right.$ $\displaystyle q_{u}$
$\displaystyle=\left\\{\begin{array}[]{ll}i(\mathcal{F}\cup\mathcal{D},u,s)&\quad\textrm{for
}1\leq u\leq\min\\{w^{\prime},v+1\\},\\\ q^{\prime}_{u-w}&\quad\textrm{for
}w^{\prime}<u\leq v+1.\end{array}\right.$

Thus $(\boldsymbol{p},\boldsymbol{q})$ extends
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ by
$(\mathcal{E},\mathcal{F})$. ∎

###  3.2 Dynamic programming

We next show how to decide whether $\mathcal{J}$ admits a good $2$-partition
by dynamic programming. By Lemma 1, it suffices to check whether $\mathcal{J}$
admits a good basic $2$-partition.

For $0\leq s\leq m$, for each pair of $s$-monotonic sequences
$(\boldsymbol{p},\boldsymbol{q})$ and each $2$-partition
$(\mathcal{A},\mathcal{B})$ of $\mathcal{K}_{s}$, denote by
$Y(s,\boldsymbol{p},\boldsymbol{q},\mathcal{A},\mathcal{B})$ the predicate
whether there is a good basic $2$-partition $(\mathcal{P},\mathcal{Q})$ of
$\mathcal{J}(0,s)$ such that $(\boldsymbol{p},\boldsymbol{q})$ encodes
$(\mathcal{P},\mathcal{Q})$, $\mathcal{P}\mid\mathcal{P}\cup\mathcal{A}$,
$\mathcal{Q}\mid\mathcal{Q}\cup\mathcal{B}$, and $(s-1,s)\in\mathcal{P}$ when
$s>0$. Then, since $\mathcal{J}(0,m)=\mathcal{J}$ and
$\mathcal{K}_{m}=\emptyset$, $\mathcal{J}$ admits a good basic $2$-partition
if and only if there exists a pair of $m$-monotonic sequences
$(\boldsymbol{p},\boldsymbol{q})$ such that
$Y(m,\boldsymbol{p},\boldsymbol{q},\emptyset,\emptyset)=\mathrm{true}$.

We can compute $Y(s,\boldsymbol{p},\boldsymbol{q},\mathcal{A},\mathcal{B})$ by
dynamic programming. For the base case when $s=0$, since $\mathcal{J}(0,0)$
and $\mathcal{K}_{0}$ are both empty, we have
$Y(0,\boldsymbol{0},\boldsymbol{0},\emptyset,\emptyset)=\mathrm{true}$. For
$1\leq s\leq m$, we can compute
$Y(s,\boldsymbol{p},\boldsymbol{q},\mathcal{A},\mathcal{B})$ by the recurrence
in the following lemma:

######  Lemma 5.

For $1\leq s\leq m$, for any pair of $s$-monotonic sequences
$(\boldsymbol{p},\boldsymbol{q})$ and any $2$-partition
$(\mathcal{A},\mathcal{B})$ of $\mathcal{K}_{s}$,
$Y(s,\boldsymbol{p},\boldsymbol{q},\mathcal{A},\mathcal{B})=\mathrm{true}$ if
and only if for some $s^{\prime}$, $0\leq s^{\prime}<s$, there exist a pair of
$s^{\prime}$-monotonic sequences
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ and a $2$-partition
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$ of $\mathcal{K}_{s^{\prime}}$,
such that the following conditions are satisfied with
$(\mathcal{C},\mathcal{D})=(\mathcal{J}_{\leq}(s^{\prime},s),\mathcal{J}_{>}(s^{\prime},s))$:

  1. 1.

$Y(s^{\prime},\boldsymbol{q^{\prime}},\boldsymbol{p^{\prime}},\mathcal{B}^{\prime},\mathcal{A}^{\prime})=\mathrm{true}$.

  2. 2.

$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})\simeq(\mathcal{A},\mathcal{B})$.

  3. 3.

$(\boldsymbol{p},\boldsymbol{q})$ extends
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ by
$(\mathcal{A}^{\prime}\setminus\mathcal{A},\mathcal{B}^{\prime}\setminus\mathcal{B})\succ\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$.

  4. 4.

$\mathcal{C}\mid\mathcal{A}^{\prime}\cup\mathcal{C}\cup\mathcal{A}$ and
$\mathcal{D}\mid\mathcal{B}^{\prime}\cup\mathcal{D}\cup\mathcal{B}$.

  5. 5.

For each interval $(a,b)\in\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$,
where $0\leq a<s^{\prime}<b\leq s$,

     * •

if $(a,b)\in\mathcal{A}^{\prime}\setminus\mathcal{A}$, then
$\alpha(\boldsymbol{p^{\prime}},a,s^{\prime})+\alpha(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),s^{\prime},b)\leq
v$,

     * •

if $(a,b)\in\mathcal{B}^{\prime}\setminus\mathcal{B}$, then
$\alpha(\boldsymbol{q^{\prime}},a,s^{\prime})+\alpha(\mathcal{D}\cup(\mathcal{B}\setminus\mathcal{B}^{\prime}),s^{\prime},b)\leq
v$.

###### Proof.

We first prove the direct implication. Suppose that
$Y(s,\boldsymbol{p},\boldsymbol{q},\mathcal{A},\mathcal{B})=\mathrm{true}$.
Then there exists a good basic $2$-partition $(\mathcal{P},\mathcal{Q})$ of
$\mathcal{J}(0,s)$ such that $(\boldsymbol{p},\boldsymbol{q})$ encodes
$(\mathcal{P},\mathcal{Q})$, $\mathcal{P}\mid\mathcal{P}\cup\mathcal{A}$,
$\mathcal{Q}\mid\mathcal{Q}\cup\mathcal{B}$, and $(s-1,s)\in\mathcal{P}$.
Since $\mathcal{J}(0,s)\cap\mathcal{K}_{s}=\emptyset$, we have
$(\mathcal{P},\mathcal{Q})\simeq(\mathcal{A},\mathcal{B})$, and hence
$(\mathcal{P}\cup\mathcal{A},\mathcal{Q}\cup\mathcal{B})\succ\mathcal{J}(0,s)\cup\mathcal{K}_{s}$.

Let $(s^{\prime},s)$, $0\leq s^{\prime}<s$, be the rightmost maximal
vertebrate range for $(\mathcal{P},\mathcal{Q})$. Since
$(\mathcal{P},\mathcal{Q})$ is a good basic $2$-partition of
$\mathcal{J}(0,s)$ with $(s-1,s)\in\mathcal{P}$, and since
$(\mathcal{C},\mathcal{D})=(\mathcal{J}_{\leq}(s^{\prime},s),\mathcal{J}_{>}(s^{\prime},s))\succ\mathcal{J}(s^{\prime},s)$,
we must have $\mathcal{C}=\mathcal{P}(s^{\prime},s)$ and
$\mathcal{D}=\mathcal{Q}(s^{\prime},s)$. Let
$\mathcal{P}^{\prime}=\mathcal{P}(0,s^{\prime})$ and
$\mathcal{Q}^{\prime}=\mathcal{Q}(0,s^{\prime})$. Then
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ is a good basic $2$-partition of
$\mathcal{J}(0,s^{\prime})$.

Note that
$\mathcal{K}_{s^{\prime}}\subseteq\mathcal{J}(0,s)\cup\mathcal{K}_{s}$. Let
$\mathcal{A}^{\prime}=(\mathcal{P}\cup\mathcal{A})\cap\mathcal{K}_{s^{\prime}}$
and
$\mathcal{B}^{\prime}=(\mathcal{Q}\cup\mathcal{B})\cap\mathcal{K}_{s^{\prime}}$.
Then $(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$ is a $2$-partition of
$\mathcal{K}_{s^{\prime}}$ derived from the $2$-partition
$(\mathcal{P}\cup\mathcal{A},\mathcal{Q}\cup\mathcal{B})$ of
$\mathcal{J}(0,s)\cup\mathcal{K}_{s}$, and is consistent with both
$(\mathcal{P},\mathcal{Q})$ and $(\mathcal{A},\mathcal{B})$. In particular,
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})\simeq(\mathcal{A},\mathcal{B})$,
satisfying condition 2. Moreover, since both
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ and $(\mathcal{C},\mathcal{D})$
are derived from $(\mathcal{P},\mathcal{Q})$, it follows that
$(\mathcal{P},\mathcal{Q})$, $(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$,
$(\mathcal{A},\mathcal{B})$, $(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$,
and $(\mathcal{C},\mathcal{D})$ are pairwise consistent, and so are all
$2$-partitions derived from their combinations, for example,

$\displaystyle(\mathcal{P}^{\prime}\cup\mathcal{A}^{\prime},\mathcal{Q}^{\prime}\cup\mathcal{B}^{\prime})$
$\displaystyle\succ\mathcal{J}(0,s^{\prime})\cup\mathcal{K}_{s^{\prime}},$
$\displaystyle(\mathcal{A}^{\prime}\setminus\mathcal{A},\mathcal{B}^{\prime}\setminus\mathcal{B})$
$\displaystyle\succ\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s},$
$\displaystyle(\mathcal{A}^{\prime}\cup\mathcal{C}\cup\mathcal{A},\mathcal{B}^{\prime}\cup\mathcal{D}\cup\mathcal{B})$
$\displaystyle\succ\mathcal{K}_{s^{\prime}}\cup\mathcal{J}(s^{\prime},s)\cup\mathcal{K}_{s},$
$\displaystyle(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),\mathcal{D}\cup(\mathcal{B}\setminus\mathcal{B}^{\prime}))$
$\displaystyle\succ\mathcal{J}(s^{\prime},s)\cup(\mathcal{K}_{s}\setminus\mathcal{K}_{s^{\prime}}).$

For condition 1, recall that $(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ is
a good basic $2$-partition of $\mathcal{J}(0,s^{\prime})$, and is consistent
with
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})\succ\mathcal{K}_{s^{\prime}}$.
Let $\boldsymbol{p^{\prime}}$ and $\boldsymbol{q^{\prime}}$ be the
$s^{\prime}$-monotonic sequences encoding $\mathcal{P}^{\prime}$ and
$\mathcal{Q}^{\prime}$, respectively. Note that the following $2$-partitions
are pairwise consistent:

$\displaystyle(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})\succ\mathcal{J}(0,s^{\prime}),\qquad(\mathcal{P},\mathcal{Q})\succ\mathcal{J}(0,s)$
$\displaystyle(\mathcal{P}^{\prime}\cup\mathcal{A}^{\prime},\mathcal{Q}^{\prime}\cup\mathcal{B}^{\prime})\succ\mathcal{J}(0,s^{\prime})\cup\mathcal{K}_{s^{\prime}},\qquad(\mathcal{P}\cup\mathcal{A},\mathcal{Q}\cup\mathcal{B})\succ\mathcal{J}(0,s)\cup\mathcal{K}_{s}.$

Since $\mathcal{J}(0,s^{\prime})\subseteq\mathcal{J}(0,s)$ and
$\mathcal{J}(0,s^{\prime})\cup\mathcal{K}_{s^{\prime}}\subseteq\mathcal{J}(0,s)\cup\mathcal{K}_{s}$,
we must have

$\mathcal{P}^{\prime}\subseteq\mathcal{P},\qquad\mathcal{Q}^{\prime}\subseteq\mathcal{Q},\qquad\mathcal{P}^{\prime}\cup\mathcal{A}^{\prime}\subseteq\mathcal{P}\cup\mathcal{A},\qquad\mathcal{Q}^{\prime}\cup\mathcal{B}^{\prime}\subseteq\mathcal{Q}\cup\mathcal{B}.$

Since $\mathcal{P}\mid\mathcal{P}\cup\mathcal{A}$ and
$\mathcal{Q}\mid\mathcal{Q}\cup\mathcal{B}$, it follows that
$\mathcal{P}^{\prime}\mid\mathcal{P}^{\prime}\cup\mathcal{A}^{\prime}$ and
$\mathcal{Q}^{\prime}\mid\mathcal{Q}^{\prime}\cup\mathcal{B}^{\prime}$. Also,
by our choice of $s^{\prime}$, we have either $s^{\prime}=0$ or
$(s^{\prime}-1,s^{\prime})\in\mathcal{Q}^{\prime}$. Then
$Y(s^{\prime},\boldsymbol{q^{\prime}},\boldsymbol{p^{\prime}},\mathcal{B}^{\prime},\mathcal{A}^{\prime})=\mathrm{true}$.

Condition 3 is satisfied by Lemma 4 with
$(\mathcal{E},\mathcal{F})=(\mathcal{A}^{\prime}\setminus\mathcal{A},\mathcal{B}^{\prime}\setminus\mathcal{B})\succ\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$.

For condition 4, note that the intervals in
$\mathcal{J}(0,s)\cup\mathcal{K}_{s}$ that intersect any interval in
$\mathcal{J}(s^{\prime},s)$ are all in
$\mathcal{K}_{s^{\prime}}\cup\mathcal{J}(s^{\prime},s)\cup\mathcal{K}_{s}$.
Note that the following $2$-partitions are pairwise consistent:

$\displaystyle(\mathcal{C},\mathcal{D})\succ\mathcal{J}(s^{\prime},s),\qquad(\mathcal{P},\mathcal{Q})\succ\mathcal{J}(0,s),$
$\displaystyle(\mathcal{A}^{\prime}\cup\mathcal{C}\cup\mathcal{A},\mathcal{B}^{\prime}\cup\mathcal{D}\cup\mathcal{B})\succ\mathcal{K}_{s^{\prime}}\cup\mathcal{J}(s^{\prime},s)\cup\mathcal{K}_{s},\qquad(\mathcal{P}\cup\mathcal{A},\mathcal{Q}\cup\mathcal{B})\succ\mathcal{J}(0,s)\cup\mathcal{K}_{s}.$

Since $\mathcal{J}(s^{\prime},s)\subseteq\mathcal{J}(0,s)$ and
$\mathcal{K}_{s^{\prime}}\cup\mathcal{J}(s^{\prime},s)\cup\mathcal{K}_{s}\subseteq\mathcal{J}(0,s)\cup\mathcal{K}_{s}$,
we must have

$\mathcal{C}\subseteq\mathcal{P},\qquad\mathcal{D}\subseteq\mathcal{Q},\qquad\mathcal{A}^{\prime}\cup\mathcal{C}\cup\mathcal{A}\subseteq\mathcal{P}\cup\mathcal{A},\qquad\mathcal{B}^{\prime}\cup\mathcal{D}\cup\mathcal{B}\subseteq\mathcal{Q}\cup\mathcal{B}.$

Since $\mathcal{P}\mid\mathcal{P}\cup\mathcal{A}$ and
$\mathcal{Q}\mid\mathcal{Q}\cup\mathcal{B}$, it follows that
$\mathcal{C}\mid\mathcal{A}^{\prime}\cup\mathcal{C}\cup\mathcal{A}$ and
$\mathcal{D}\mid\mathcal{B}^{\prime}\cup\mathcal{D}\cup\mathcal{B}$.

Finally, proceed to condition 5. Note that

$(\mathcal{J}(0,s)\cup\mathcal{K}_{s})\setminus\mathcal{K}_{s^{\prime}}=\mathcal{J}(0,s^{\prime})\cup(\mathcal{J}(s^{\prime},s)\cup(\mathcal{K}_{s}\setminus\mathcal{K}_{s^{\prime}})),$

where $\mathcal{J}(0,s^{\prime})$ includes the intervals to the left of
$s^{\prime}$, and
$\mathcal{J}(s^{\prime},s)\cup(\mathcal{K}_{s}\setminus\mathcal{K}_{s^{\prime}})$
includes the intervals to the right of $s^{\prime}$. Also note that
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})\succ\mathcal{J}(0,s^{\prime})$
and
$(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),\mathcal{D}\cup(\mathcal{B}\setminus\mathcal{B}^{\prime}))\succ\mathcal{J}(s^{\prime},s)\cup(\mathcal{K}_{s}\setminus\mathcal{K}_{s^{\prime}})$.
By our choice of $s^{\prime}$, we have
$(s^{\prime},s^{\prime}+1)\in\mathcal{P}\cup\mathcal{A}$ and
$(s^{\prime}-1,s^{\prime})\in\mathcal{Q}\cup\mathcal{B}$ for the $2$-partition
$(\mathcal{P}\cup\mathcal{A},\mathcal{Q}\cup\mathcal{B})\succ\mathcal{J}(0,s)\cup\mathcal{K}_{s}$.

Consider any interval
$(a,b)\in\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}\subseteq\mathcal{J}(0,s)\cup\mathcal{K}_{s}$,
where $0\leq a<s^{\prime}<b\leq s$. If
$(a,b)\in\mathcal{A}^{\prime}\setminus\mathcal{A}$, then we have
$\alpha(\mathcal{P}\cup\mathcal{A},a,b)=\alpha(\mathcal{P}^{\prime},a,s^{\prime})+\alpha(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),s^{\prime},b)$
by Lemma 2. Since $\mathcal{P}\mid\mathcal{P}\cup\mathcal{A}$, it follows that
$\alpha(\mathcal{P}\cup\mathcal{A},a,b)\leq v$, and hence
$\alpha(\mathcal{P}^{\prime},a,s^{\prime})+\alpha(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),s^{\prime},b)\leq
v$. By Lemma 3,
$\alpha(\mathcal{P}^{\prime},a,s^{\prime})\geq\alpha(\boldsymbol{p^{\prime}},a,s^{\prime})$.
Thus
$\alpha(\boldsymbol{p^{\prime}},a,s^{\prime})+\alpha(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),s^{\prime},b)\leq
v$. Similarly, if $(a,b)\in\mathcal{B}^{\prime}\setminus\mathcal{B}$, then
$\alpha(\boldsymbol{q^{\prime}},a,s^{\prime})+\alpha(\mathcal{D}\cup(\mathcal{B}\setminus\mathcal{B}^{\prime}),s^{\prime},b)\leq
v$.

Thus conditions 1 through 5 are all satisfied.

We next prove the reverse implication. Suppose that for some $s^{\prime}$,
$0\leq s^{\prime}<s$, there exist a pair of $s^{\prime}$-monotonic sequences
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ and a $2$-partition
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$ of $\mathcal{K}_{s^{\prime}}$,
such that conditions 1 through 5 are satisfied.

By condition 1, there exists a good basic $2$-partition
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ of $\mathcal{J}(0,s^{\prime})$,
such that $(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ encodes
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$,
$\mathcal{P}^{\prime}\mid\mathcal{P}^{\prime}\cup\mathcal{A}^{\prime}$,
$\mathcal{Q}^{\prime}\mid\mathcal{Q}^{\prime}\cup\mathcal{B}^{\prime}$, and
$(s^{\prime}-1,s^{\prime})\in\mathcal{Q}^{\prime}$ when $s^{\prime}>0$.

By condition 2,
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})\simeq(\mathcal{A},\mathcal{B})$.
Since $\mathcal{J}(0,s^{\prime})\cap\mathcal{K}_{s^{\prime}}=\emptyset$, we
have
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})\simeq(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$,
and hence
$(\mathcal{P}^{\prime}\cup\mathcal{A}^{\prime},\mathcal{Q}^{\prime}\cup\mathcal{B}^{\prime})\succ\mathcal{J}(0,s^{\prime})\cup\mathcal{K}_{s^{\prime}}$.
Also, since $\mathcal{J}(0,s^{\prime})\cap\mathcal{K}_{s}=\emptyset$, we have
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})\simeq(\mathcal{A},\mathcal{B})$.
Thus $(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$,
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$, and $(\mathcal{A},\mathcal{B})$
are pairwise consistent. Moreover, $(\mathcal{C},\mathcal{D})$ is consistent
with $(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$,
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$, and $(\mathcal{A},\mathcal{B})$
because $\mathcal{J}(s^{\prime},s)$ is disjoint from
$\mathcal{J}(0,s^{\prime})$, $\mathcal{K}_{s^{\prime}}$, and
$\mathcal{K}_{s}$. Thus $(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$,
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$, $(\mathcal{A},\mathcal{B})$,
and $(\mathcal{C},\mathcal{D})$ are pairwise consistent.

Let
$\mathcal{P}=\mathcal{P}^{\prime}\cup(\mathcal{A}^{\prime}\setminus\mathcal{A})\cup\mathcal{C}$
and
$\mathcal{Q}=\mathcal{Q}^{\prime}\cup(\mathcal{B}^{\prime}\setminus\mathcal{B})\cup\mathcal{D}$.
Then $(\mathcal{P},\mathcal{Q})$ is a $2$-partition of
$\mathcal{J}(0,s)=\mathcal{J}(0,s^{\prime})\cup(\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s})\cup\mathcal{J}(s^{\prime},s)$,
and is consistent with $(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$,
$(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$, $(\mathcal{A},\mathcal{B})$,
and $(\mathcal{C},\mathcal{D})$. Moreover, $(\mathcal{P},\mathcal{Q})$ is
basic, with $(s^{\prime},s)$ as the rightmost maximal vertebrate range and
with $(s-1,s)\in\mathcal{P}$, because
$(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ is basic,
$(\mathcal{C},\mathcal{D})$ is simple,
$\mathcal{U}(s^{\prime},s)\subseteq\mathcal{C}\subseteq\mathcal{P}$, and
$(s^{\prime}-1,s^{\prime})\in\mathcal{Q}^{\prime}\subseteq\mathcal{Q}$ when
$s^{\prime}>0$.

By Lemma 4, $(\mathcal{P},\mathcal{Q})$ is encoded by a pair of $s$-monotonic
sequences that extends $(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ by
$(\mathcal{E},\mathcal{F})=(\mathcal{A}^{\prime}\setminus\mathcal{A},\mathcal{B}^{\prime}\setminus\mathcal{B})\succ\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$.
Since any pair $(\boldsymbol{p},\boldsymbol{q})$ that extends
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ by
$(\mathcal{E},\mathcal{F})$ is uniquely determined by
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ and
$(\mathcal{E},\mathcal{F})$, $(\mathcal{P},\mathcal{Q})$ must be encoded by
the pair $(\boldsymbol{p},\boldsymbol{q})$ that extends
$(\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}})$ by
$(\mathcal{E},\mathcal{F})$ in condition 3.

We next show that $\mathcal{P}\mid\mathcal{P}\cup\mathcal{A}$ and
$\mathcal{Q}\mid\mathcal{Q}\cup\mathcal{B}$. Note that
$\mathcal{J}(0,s)=\mathcal{J}(0,s^{\prime})\cup(\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s})\cup\mathcal{J}(s^{\prime},s)$.
The three subfamilies $\mathcal{J}(0,s^{\prime})$,
$\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$, and
$\mathcal{J}(s^{\prime},s)$ have neighborhoods
$\mathcal{J}(0,s^{\prime})\cup\mathcal{K}_{s^{\prime}}$,
$\mathcal{J}(0,s)\cup\mathcal{K}_{s}$, and
$\mathcal{K}_{s^{\prime}}\cup\mathcal{J}(s^{\prime},s)\cup\mathcal{K}_{s}$,
respectively.

For $\mathcal{J}(0,s^{\prime})$ and its neighborhood
$\mathcal{J}(0,s^{\prime})\cup\mathcal{K}_{s^{\prime}}$, condition 1
guarantees that
$\mathcal{P}^{\prime}\mid\mathcal{P}^{\prime}\cup\mathcal{A}^{\prime}$ and
$\mathcal{Q}^{\prime}\mid\mathcal{Q}^{\prime}\cup\mathcal{B}^{\prime}$.

For $\mathcal{J}(s^{\prime},s)$ and its neighborhood
$\mathcal{K}_{s^{\prime}}\cup\mathcal{J}(s^{\prime},s)\cup\mathcal{K}_{s}$,
condition 4 guarantees that
$\mathcal{C}\mid\mathcal{A}^{\prime}\cup\mathcal{C}\cup\mathcal{A}$ and
$\mathcal{D}\mid\mathcal{B}^{\prime}\cup\mathcal{D}\cup\mathcal{B}$.

For $\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$ and its neighborhood
$\mathcal{J}(0,s)\cup\mathcal{K}_{s}$, recall that by condition 1, we have
either $s^{\prime}=0$ or $(s^{\prime}-1,s^{\prime})\in\mathcal{Q}^{\prime}$.
If $s^{\prime}=0$, then $\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$ is
empty. Otherwise, we have
$(s^{\prime}-1,s^{\prime})\in\mathcal{Q}^{\prime}\subseteq\mathcal{Q}\cup\mathcal{B}$
and
$(s^{\prime},s^{\prime}+1)\in\mathcal{C}\subseteq\mathcal{P}\cup\mathcal{A}$
for the $2$-partition
$(\mathcal{P}\cup\mathcal{A},\mathcal{Q}\cup\mathcal{B})\succ\mathcal{J}(0,s)\cup\mathcal{K}_{s}$.

Consider any interval
$(a,b)\in\mathcal{K}_{s^{\prime}}\setminus\mathcal{K}_{s}$, where $0\leq
a<s^{\prime}<b\leq s$. If $(a,b)\in\mathcal{A}^{\prime}\setminus\mathcal{A}$,
then by Lemma 2 we have

$\alpha(\mathcal{P}\cup\mathcal{A},a,b)=\alpha(\mathcal{P}^{\prime},a,s^{\prime})+\alpha(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),s^{\prime},b).$

Condition 5 guarantees that

$\alpha(\boldsymbol{p^{\prime}},a,s^{\prime})\leq\alpha(\boldsymbol{p^{\prime}},a,s^{\prime})+\alpha(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),s^{\prime},b)\leq
v.$

By Lemma 3,
$\alpha(\mathcal{P}^{\prime},a,s^{\prime})=\alpha(\boldsymbol{p^{\prime}},a,s^{\prime})$
whenever $\alpha(\boldsymbol{p^{\prime}},a,s^{\prime})\leq v$. Thus

$\alpha(\mathcal{P}\cup\mathcal{A},a,b)=\alpha(\mathcal{P}^{\prime},a,s^{\prime})+\alpha(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),s^{\prime},b)=\alpha(\boldsymbol{p^{\prime}},a,s^{\prime})+\alpha(\mathcal{C}\cup(\mathcal{A}\setminus\mathcal{A}^{\prime}),s^{\prime},b)\leq
v.$

Similarly, if $(a,b)\in\mathcal{B}^{\prime}\setminus\mathcal{B}$, then

$\alpha(\mathcal{Q}\cup\mathcal{B},a,b)=\alpha(\mathcal{Q}^{\prime},a,s^{\prime})+\alpha(\mathcal{D}\cup(\mathcal{B}\setminus\mathcal{B}^{\prime}),s^{\prime},b)=\alpha(\boldsymbol{q^{\prime}},a,s^{\prime})+\alpha(\mathcal{D}\cup(\mathcal{B}\setminus\mathcal{B}^{\prime}),s^{\prime},b)\leq
v.$

Thus $\mathcal{A}^{\prime}\setminus\mathcal{A}\mid\mathcal{P}\cup\mathcal{A}$
and $\mathcal{B}^{\prime}\setminus\mathcal{B}\mid\mathcal{Q}\cup\mathcal{B}$.

We have shown that $\mathcal{P}\mid\mathcal{P}\cup\mathcal{A}$ and
$\mathcal{Q}\mid\mathcal{Q}\cup\mathcal{B}$. In particular,
$\mathcal{P}\mid\mathcal{P}$ and $\mathcal{Q}\mid\mathcal{Q}$, and hence
$(\mathcal{P},\mathcal{Q})$ is good. In summary, we have a good basic
$2$-partition $(\mathcal{P},\mathcal{Q})$ of $\mathcal{J}(0,s)$ such that
$(\boldsymbol{p},\boldsymbol{q})$ encodes $(\mathcal{P},\mathcal{Q})$,
$\mathcal{P}\mid\mathcal{P}\cup\mathcal{A}$,
$\mathcal{Q}\mid\mathcal{Q}\cup\mathcal{B}$, and $(s-1,s)\in\mathcal{P}$. Thus
$Y(s,\boldsymbol{p},\boldsymbol{q},\mathcal{A},\mathcal{B})=\mathrm{true}$, as
desired. ∎

###  3.3 Time complexity

We say that two intervals in $\mathcal{J}$ _overlap significantly_ if the
length of their intersection is at least $2v+1$. Construct a graph $H$ with
vertex set $\mathcal{J}$ such that two vertices in $H$ are connected by an
edge if and only if the corresponding two intervals in $\mathcal{J}$ overlap
significantly. Compute connected components in $H$, and partition
$\mathcal{J}$ into _groups_ accordingly. We say that a $2$-partition of
$\mathcal{J}$ is _group-conforming_ if no two intervals from the same group
are put in different parts.

######  Lemma 6.

Any good $2$-partition of $\mathcal{J}$ must be group-conforming.

###### Proof.

It suffices to show that any two intervals that overlap significantly must be
in the same part. Let $A$ and $B$ be two intervals in $\mathcal{J}$ such that
the length $\ell$ of their intersection $A\cap B$ is at least $2v+1$. Then
$A\cap B$ contains $\ell\geq 2v+1$ disjoint unit intervals in
$\mathcal{U}\subseteq\mathcal{J}$. If $A$ and $B$ are in two different parts
of a $2$-partition of $\mathcal{J}$, then either $A$ or $B$ would contain at
least $\lceil(2v+1)/2\rceil=v+1$ disjoint unit intervals in the same part,
forming a star $K_{1,v+1}$. ∎

######  Lemma 7.

Any integer point of the line is contained in intervals from at most
$2v^{2}+v$ groups.

###### Proof.

Fix any point $x$. For each interval of length at least $2v+1$ that contains
$x$, let its _core_ be any subinterval of length exactly $2v+1$ that still
contains $x$. If the cores of two intervals coincide, then they overlap
significantly and hence belong to the same group. Thus the number of groups
with at least one interval of length at least $2v+1$ containing $x$ is at most
the number of distinct intervals of length exactly $2v+1$ containing $x$,
which is $2v$.

On the other hand, for each $\ell$, $1\leq\ell\leq 2v$, there are $\ell-1$
distinct intervals of length $\ell$ containing $x$. In total, there are at
most $(2v)(2v-1)/2=2v^{2}-v$ such intervals, and hence there are at most
$2v^{2}-v$ distinct groups including such intervals in $\mathcal{J}$.

In summary, the point $x$ is contained in intervals from at most
$2v+2v^{2}-v=2v^{2}+v$ groups. ∎

Note that the number $m$ of maximal cliques is at most the number $n$ of
vertices in vertebrate interval graphs. For each $s$, $1\leq s\leq m\leq n$,
there are $n^{O(v)}$ pairs of $s$-monotonic sequences
$(\boldsymbol{p},\boldsymbol{q})$. By Lemma 7, each $\mathcal{K}_{s}$ includes
intervals from $O(v^{2})$ groups, and hence has $2^{O(v^{2})}$ group-
conforming $2$-partitions $(\mathcal{A},\mathcal{B})$. For two tuples
$(s,\boldsymbol{p},\boldsymbol{q},\mathcal{A},\mathcal{B})$ and
$(s^{\prime},\boldsymbol{p^{\prime}},\boldsymbol{q^{\prime}},\mathcal{A}^{\prime},\mathcal{B}^{\prime})$,
all conditions in Lemma 5 can be checked in $n^{O(1)}$ time. Thus the running
time of our dynamic programming algorithm is $2^{O(v^{2})}n^{O(v)}$. This
completes the proof of Theorem 1.

##  4 Open questions

What is the minimum number $k$ such that every interval graph with $n$
vertices admits a vertex partition into $k$ induced subgraphs that are
vertebrate interval graphs? Is there a polynomial-time algorithm for
partitioning an interval graph into the minimum number of vertebrate interval
graphs?

## References

  * [1] D. Achlioptas. The complexity of $G$-free colourability. _Discrete Mathematics_ , 165/166:21–30, 1997.
  * [2] A. Adiga and L. S. Chandran. Cubicity of interval graphs and the claw number. _Journal of Graph Theory_ , 65:323–333, 2010.
  * [3] M. O. Albertson, R. E. Jamison, S. T. Hedetniemi, and S. C. Locke. The subchromatic number of a graph. _Discrete Mathematics_ , 74:33–49, 1989.
  * [4] K. P. Bogart and D. B. West. A short proof that ‘proper = unit’. _Discrete Mathematics_ , 201:21–23, 1999.
  * [5] H. Broersma, F. V. Fomin, J. Nešetřil, and G. J. Woeginger. More about subcolorings. _Computing_ , 69:187-203, 2002.
  * [6] A. Farrugia. Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. _The Electronic Journal of Combinatorics_ , 11:#R46, 2004.
  * [7] M. C. Golumbic. Trivially perfect graphs. _Discrete Mathematics_ , 24:105–107, 1978.
  * [8] M. C. Golumbic. _Algorithmic Graph Theory and Perfect Graphs_ , Second Edition. Elsevier, 2004.
  * [9] R. Jiang, K. Jiang, and M. Jiang. Partitioning an interval graph into subgraphs with small claws. arXiv:2109.11498, 2021.