#  Max Weight Independent Set in sparse graphs with no long claws

Tara Abrishami Department of Mathematics, University of Hamburg, Germany,
<EMAIL_ADDRESS>Supported by the National Science Foundation Award Number
DMS-2303251 and the Alexander von Humboldt Foundation. Maria Chudnovsky
Department of Mathematics, Princeton University, USA,
<EMAIL_ADDRESS>Supported by NSF-EPSRC Grant DMS-2120644 and by
AFOSR grant FA9550-22-1-008. Marcin Pilipczuk Institute of Informatics,
University of Warsaw, Poland<EMAIL_ADDRESS>Supported by Polish
National Science Centre SONATA BIS-12 grant number 2022/46/E/ST6/00143. Paweł
Rzążewski Faculty of Mathematics and Information Science, Warsaw University of
Technology and Institute of Informatics, University of Warsaw, Poland,
<EMAIL_ADDRESS>This work is a part of the project BOBR that has
received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No.
948057)

###### Abstract

We revisit the recent polynomial-time algorithm for the Max Weight Independent
Set (MWIS) problem in bounded-degree graphs excluding a fixed subdivided claw
$S_{t,t,t}$ as an induced subgraph [Abrishami, Dibek, Chudnovsky, Rzążewski,
SODA 2022].

First, we show that with an arguably simpler approach we can obtain a faster
algorithm with running time $n^{\mathcal{O}(\Delta^{2})}$, where $n$ is the
number of vertices of the instance and $\Delta$ is the maximum degree. Then we
combine our technique with known results concerning tree decompositions and
provide a polynomial-time algorithm for MWIS in graphs excluding a fixed
subdivided claw as an induced subgraph and a fixed biclique as a subgraph.

##  1 Introduction

A _vertex-weighted graph_ is an undirected graph $G$ equipped with a weight
function For $X\subseteq V(G)$, $\mathbf{w}(X)$ is a shorthand for $\sum_{x\in
X}\mathbf{w}(x)$ and for a subgraph $H$ of $G$, $\mathbf{w}(H)$ is a shorthand
for $\mathbf{w}(V(H))$. By convention we use $\mathbf{w}(\emptyset)=0$.
Throughout the paper we assume that arithmetic operations on weights are
performed in unit time.

For a graph $G$, a set $I\subseteq V(G)$ is _independent_ or _stable_ if there
is no edge of $G$ with both endpoints in $I$. In the Max Weight Independent
Set (MWIS) problem we are given an undirected graph $G$ with a weight function
$\mathbf{w}:V(G)\to\mathbb{N}$, and ask for a maximum-weight independent set
in $G$. MWIS is one of canonical hard problems – it is NP-hard [22], W[1]-hard
[14], hard to approximate [21]. Thus a very natural research direction is to
consider restricted instances and try to capture the boundary between “easy”
and “hard” cases.

#### State of the art.

The study of complexity of MWIS in restricted graph classes is a central topic
in algorithmic graph theory [19, 44, 26, 18, 13, 3]. A particular attention is
given to classes that are _hereditary_ , i.e., closed under vertex deletion.
Among such classes a special role is played ones defined by forbidding certain
substructures. For graphs $G$ and $H$, we say that $G$ is _$H$ -free_ if it
does not contain $H$ as an _induced subgraph_.

As already observed by Alekseev in the early 1980s [2], MWIS remains NP-hard
in $H$-free graphs unless every component of $H$ is a subcubic tree with at
most one vertex of degree 3. In other words, every component of $H$ is either
a path or a subdivision of the _claw_ : the three-leaf star. For integers
$a,b,c\geqslant 1$, by $S_{a,b,c}$ we denote the claw whose edges were
subdivided, respectively, $a-1$, $b-1$, and $c-1$ times.

In the past few years we have witnessed rapid progress in development of
algorithms for MWIS in these remaining cases [5, 9, 15, 41, 12, 16, 34]. In
particular, it is known that MWIS for these classes can be solved in
quasipolynomial time [15, 41, 16], which is a strong indication that the
problem is not NP-hard. However, we are still very far from obtaining
polynomial-time algorithms. Such results are known only for very small
forbidden paths [26, 18] or subdivided claws [35, 42, 4, 27]. There is also a
long line of research concerning graphs excluding a fixed (but still small)
path or a subdivided claw and, simultaneously, some other small graphs, see
e.g. [25, 6, 17, 31, 33, 37, 28, 29, 20, 7, 30, 36, 38, 39, 40, 8].

In a somewhat perpendicular direction, Abrishami, Chudnovsky, Dibek, and
Rzążewski [1] proved that for every $a,b,c$, the MWIS problem can be solved in
polynomial time in $S_{a,b,c}$-free graphs of bounded degree (where the degre
of the polynomial depends on $a,b,c$, and the degree bound). Let us remark
that the algorithm of [1] is very technical, and the dependency of the
complexity on the degree bound is involved.

#### Our results.

As a warm-up, we present a polynomial-time algorithm for $S_{t,t,t}$-free
graphs of bounded degree. It is significantly simpler than the one by
Abrishami et al. [1] and has much better dependency on the maximum degree.

######  Theorem 1.

For every fixed integer $t$, there exists an algorithm that, given a vertex-
weighted graph $(G,\mathbf{w})$ on $n$ vertices with maximum degree $\Delta$
in time $n^{\mathcal{O}_{t}(\Delta^{2})}$ either finds an induced $S_{t,t,t}$
in $G$ or the maximum possible weight of an independent set in
$(G,\mathbf{w})$.

Note that picking $t=\max(a,b,c)$, theorem 1 applies to $S_{a,b,c}$-free
graphs for every $a,b,c$.

Then we proceed to the main result of the paper: we show that MWIS remains
polynomial-time solvable in $S_{t,t,t}$-free graphs, even if instead of
bounding the maximum degree, we forbid a fixed biclique _as a subgraph_.

######  Theorem 2.

For every integer $t$ there exists a polynomial-time algorithm that, given a
vertex-weighted graph $(G,\mathbf{w})$ that does not contain $S_{t,t,t}$ as an
induced subgraph nor $K_{t,t}$ as a subgraph computes the maximum possible
weight of an independent set in $(G,\mathbf{w})$.

Let us remark that by the celebrated Kövári-Sós-Turán theorem [24], classes
that exclude $K_{t,t}$ as a subgraph capture all hereditary classes of _sparse
graphs_ , where by “sparse” we mean “where every graph has subquadratic number
of edges.” Furthermore, by a simple Ramsey argument, for every positive
integer $s$ there exists an integer $t$ such that if $G$ is $K_{s}$-free and
$K_{s,s}$-free then $G$ does not contain $K_{t,t}$ as a subgraph. Hence,
Theorem 2 can equivalently be stated as $G$ being $S_{t,t,t}$-free,
$K_{t}$-free, and $K_{t,t}$-free.

#### Our techniques.

As in the previous works [1, 12, 16], the crucial tool in handling
$S_{t,t,t}$-free graphs is an _extended strip decomposition_. Its technical
definition can be found in preliminaries; for now, it suffices to say that it
is a wide generalization of the preimage graph of a line graph (recall that
line graphs are $S_{1,1,1}$-free) that allows for recursion for the MWIS
problem: An extended strip decomposition of a graph $G$ identifies some
induced subgraphs of $G$ as _particles_ and, knowing the maximum possible
weight of an independent set in each particle, one can compute in polynomial
time the maximum possible weight of an independent set in $G$. (We remark that
this computation involves advanced combinatorial techniques as it relies on a
reduction to the maximum weight matching problem in an auxiliary graph.) In
other words, finding an extended strip decomposition with small particles
compared to $|V(G)|$ is equally good for the MWIS problem as splitting the
graph into small connected components.

The starting point is the following theorem of [34].

######  Theorem 3 ([34, Theorem 2] in a semi-weighted setting).

For every fixed integer $t$, there exists a polynomial-time algorithm that,
given an $n$-vertex graph $G$ with a set $U\subseteq V(G)$, either:

  * •

outputs an induced copy of $S_{t,t,t}$ in $G$, or

  * •

outputs a set $\mathcal{P}$ consisting of at most $11\log n+6$ induced paths
in $G$, each of length at most $t+1$, and a rigid extended strip decomposition
of $G-N[\bigcup{\mathcal{P}}]$ with every particle containing at most $|U|/2$
vertices of $U$.

(A rigid extended strip decomposition is an extended strip decomposition that
does not have some unnecessary empty sets.) Let us remark that the result
stated in [34, Theorem 2] is for unweighted graphs (i.e., $U=V(G)$ using the
notation from theorem 3), but the statement of theorem 3 can be easily derived
from the proof, see also [16].

Consider the setting of Theorem 1, i.e., the graph $G$ has maximum degree
$\Delta$. Apply Theorem 3 to $G$ with $U=V(G)$. An induced $S_{t,t,t}$ in $G$
can be returned outright, so assume we get the second outcome. Let
$X=\bigcup{\mathcal{P}}$; note that $|X|=\mathcal{O}(t\log n)$ and thus
$|N[X]|=\mathcal{O}(t\Delta\log n)$. It is tempting now to exhaustively branch
on $N[X]$ (i.e., guess the intersection of the sought independent set with
$N[X]$) and recurse on the particles of the extended strip decomposition of
$G-N[X]$. However, implementing this strategy directly gives quasipolynomial
running time bound of $n^{\mathcal{O}(t\Delta\log n)}$, as the branching step
yields up to $2^{|N[X]|}=n^{\mathcal{O}(t\Delta)}$ subcases and the depth of
the recursion is $\mathcal{O}(\log n)$.

Our main new idea now is to perform this branching lazily, by considering a
more general _border_ version of the problem, where the input graph is
additionally equipped with a set of _terminals_ and we ask for a maximum
weight of an independent set for every possible behavior on the terminals.

Input: A vertex-weighted graph $(G,\mathbf{w})$ with a set $T\subseteq V(G)$
of _terminals_. Task: Compute
$f_{G,\mathbf{w},T}:2^{T}\to\mathbb{N}\cup\\{-\infty\\}$ defined for every
$I_{T}\subseteq T$ as
$f_{G,\mathbf{w},T}(I_{T})=\max\\{\mathbf{w}(I)~{}|~{}I\subseteq V(G)\wedge
I\mathrm{\ is\ independent}\wedge I\cap T=I_{T}\\}.$ Border MWIS

A similar application of a border version of the problem to postpone branching
in recursion appeared for example in the technique of recursive understanding
[23, 10].

Let us return to our setting, where we have a set $X$ of size
$\mathcal{O}(t\log n)$ and an extended strip decomposition of $G-N[X]$ with
particles of size at most half of the size of $V(G)$. We would like to remove
$N[X]$ from the graph, indicate $N(N[X])$ as terminals and solve Border MWIS
in $(G-N[X],\mathbf{w},T:=N(N[X]))$ using the extended strip decomposition for
recursion. Note that, thanks to the bounded degree assumption, the size of
$T=N(N[X])$ is bounded by $\mathcal{O}(t\Delta^{2}\log n)$.

This approach _almost_ works: the only problem is that, as the recursion
progresses, the set of terminals accummulates and its size can grow beyond the
initial $\mathcal{O}(t\Delta^{2}\log n)$ bound. Luckily, this can be remedied
in a standard way: we alternate recursive steps where Theorem 3 is invoked
with $U=V(G)$ with steps where Theorem 3 is invoked with $U=T$. In this
manner, we can maintain a bound of $\mathcal{O}(t\Delta^{2}\log n)$ on the
number of terminals in every recursive call. Note that this bound also
guarantees that the size of the domain of the requested function
$f_{G,\mathbf{w},T}$ is of size $n^{\mathcal{O}(t\Delta^{2})}$, which is
within the promised time bound.

We remark that this approach is arguably significantly simpler and more direct
than the decomposition techniques used in [1] and, furthermore, results in a
much better dependency on $\Delta$ in the exponent in the final running time
bound.

Let us now move to the more general setting of Theorem 2. Here, the starting
point are recent results of Weißauer [43] and Lozin and Razgon [32] that show
that in the $S_{t,t,t}$-free case, excluding a biclique as a subgraph is not
that much different than bounding the maximum degree.

A _$k$ -block_ in a graph is a set of $k$ vertices, no two of which can be
separated by deleting fewer than $k$ vertices. The following result was shown
by Weißauer (we refer to preliminaries for standard definitions of tree
decompositions and torsos).

######  Theorem 4 (Weißauer [43]).

Let $G$ be a graph and $k\geqslant 2$ be an integer. If $G$ has no
$(k+1)$-block, then $G$ admits a tree decomposition with adhesion less than
$k$, in which every torso has at most $k$ vertices of degree larger than
$2k(k-1)$.

Even though the statement of the result in [43] is just existential, the proof
actually yields a polynomial-time algorithm to compute such a tree
decomposition.

It turns out that $S_{t,t,t}$-free graphs with no large bicliques have no
large blocks.

######  Lemma 5 (Lozin, Razgon [32]).

For any $t$ and $s$ there exists $k$ such that the following holds. Every
$S_{t,t,t}$-free graph with no subgraph isomorphic to $K_{s,s}$ has no
$k$-block.

Combining theorem 4 and lemma 5 we immediately obtain the following.

######  Corollary 6.

For any $t$ there exists $k$ such that the following holds. Given an
$S_{t,t,t}$-free graph with no subgraph isomorphic to $K_{t,t}$, in polynomial
time one can compute a tree decomposition with adhesion less than $k$, in
which every torso has at most $k$ vertices of degree larger than $2k(k-1)$.

To prove Theorem 2 using Corollary 6 we need to carefully combine explicit
branching on the (bounded number of) vertices of large degree in a single bag
with — as in the bounded degree case — applying Theorem 3 to the remainder of
the graph and indicating $N(N[\bigcup\mathcal{P}])$ as the terminal set of the
border problem passed to the recursive calls. Finally, one requires some care
to combine this with the information passed over adhesions in the tree
decomposition.

##  2 Preliminaries

Our algorithms take a vertex-weighted graph $(G,\mathbf{w})$ as an input. In
the recursion, we will be working on various induced subgraphs of $G$ with
vertex weight inherited from $\mathbf{w}$. Somewhat abusing notation, we will
keep $\mathbf{w}$ for the weight function in any induced subgraph of $G$.

#### Tree decompositions.

Let $G$ be a graph. A _tree decomposition_ of $G$ is a pair
$(\mathcal{T},\beta)$ where $\mathcal{T}$ is a tree and
$\beta:V(\mathcal{T})\to 2^{V(G)}$ is a function satisfying the following: (i)
for every $uv\in E(G)$ there exists $t\in V(\mathcal{T})$ with
$u,v\in\beta(t)$, and (ii) for every $v\in V(G)$ the set $\\{t\in
V(\mathcal{T})~{}|~{}v\in\beta(t)\\}$ induces a connected nonempty subtree of
$\mathcal{T}$. For every $t\in V(\mathcal{T})$ and $st\in E(\mathcal{T})$, the
set $\beta(t)$ is the _bag_ at node $t$ and the set
$\sigma(st):=\beta(s)\cap\beta(t)$ is the _adhesion_ at edge $st$. The
critical property of a tree decomposition $(\mathcal{T},\beta)$ is that if
$st\in E(\mathcal{T})$ and $V_{s}$ and $V_{t}$ are two connected components of
$\mathcal{T}-\\{st\\}$ that contain $s$ and $t$, respectively, then
$\sigma(st)$ separates $\bigcup_{x\in V_{s}}\beta(x)\setminus\sigma(st)$ from
$\bigcup_{x\in V_{t}}\beta(x)\setminus\sigma(st)$ in $G$.

The _torso_ of a bag $\beta(t)$ in a tree decomposition $(\mathcal{T},\beta)$
is a graph $H$ with $V(H)=\beta(t)$ and $uv\in E(H)$ if $uv\in E(G)$ or there
exists a neighbor $s\in N_{\mathcal{T}}(t)$ with $u,v\in\sigma(st)$. That is,
the torso of $\beta(t)$ is created from $G[\beta(t)]$ by turning the adhesion
$\sigma(st)$ into a clique for every neighbor $s$ of $t$ in $\mathcal{T}$.

#### Extended strip decompositions.

We follow the notation of [34, 16]. For a graph $H$, by $T(H)$ we denote the
set of triangles in $H$. An _extended strip decomposition_ of a graph $G$ is a
pair $(H,\eta)$ that consists of:

  * •

a simple graph $H$,

  * •

a _vertex set_ $\eta(x)\subseteq V(G)$ for every $x\in V(H)$,

  * •

an _edge set_ $\eta(xy)\subseteq V(G)$ for every $xy\in E(H)$, and its subsets
$\eta(xy,x),\eta(xy,y)\subseteq\eta(xy)$,

  * •

a _triangle set_ $\eta(xyz)\subseteq V(G)$ for every $xyz\in T(H)$,

which satisfy the following properties:

  1. 1.

The family $\\{\eta(o)~{}|~{}o\in V(H)\cup E(H)\cup T(H)\\}$ is a partition of
$V(G)$.

  2. 2.

For every $x\in V(H)$ and every distinct $y,z\in N_{H}(x)$, the set
$\eta(xy,x)$ is complete to $\eta(xz,x)$.

  3. 3.

Every $uv\in E(G)$ is contained in one of the sets $\eta(o)$ for $o\in
V(H)\cup E(H)\cup T(H)$, or is as follows:

     * •

$u\in\eta(xy,x),v\in\eta(xz,x)$ for some $x\in V(H)$ and $y,z\in N_{H}(x)$, or

     * •

$u\in\eta(xy,x),v\in\eta(x)$ for some $xy\in E(H)$, or

     * •

$u\in\eta(xyz)$ and $v\in\eta(xy,x)\cap\eta(xy,y)$ for some $xyz\in T(H)$.

An extended strip decomposition $(H,\eta)$ is _rigid_ if for every $xy\in
E(H)$, the sets $\eta(xy)$, $\eta(xy,x)$, and $\eta(xy,y)$ are nonempty, and
for every isolated $x\in V(H)$, the set $\eta(x)$ is nonempty. Note that if
$(H,\eta)$ is a rigid extended strip decomposition of $G$, then $|V(H)|$ is
bounded by $|V(G)|$.

For an extended strip decomposition $(H,\eta)$ of a graph $G$, we identify
five _types_ of _particles_.

vertex particle: $\displaystyle\quad A_{x}:=\eta(x)\text{ for each }x\in
V(H),$ edge interior particle: $\displaystyle\quad
A_{xy}^{\perp}:=\eta(xy)\setminus(\eta(xy,x)\cup\eta(xy,y))\text{ for each
}xy\in E(H),$ half-edge particle: $\displaystyle\quad
A_{xy}^{x}:=\eta(x)\cup\eta(xy)\setminus\eta(xy,y)\text{ for each }xy\in
E(H),$ full edge particle: $\displaystyle\quad
A_{xy}^{xy}:=\eta(x)\cup\eta(y)\cup\eta(xy)\cup\bigcup_{z~{}:~{}xyz\in
T(H)}\eta(xyz)\text{ for each }xy\in E(H),$ triangle particle:
$\displaystyle\quad A_{xyz}:=\eta(xyz)\text{ for each }xyz\in T(H).$

As announced in the introduction, to solve MWIS in $G$ it suffices to know the
solution to MWIS in particles. The proof of the following lemma follows
closely the lines of proofs of analogous statements of [1, 12] and is included
for completeness in Appendix A.

######  Lemma 7.

Given a Border MWIS instance $(G,\mathbf{w},T)$, an extended strip
decomposition $(H,\eta)$ of $G$, and a solution $f_{G[A],\mathbf{w},T\cap A}$
to the Border MWIS instance $(G[A],\mathbf{w},T\cap A)$ for every particle $A$
of $(H,\eta)$, one can in time $2^{|T|}$ times a polynomial in $|V(G)|+|V(H)|$
compute the solution $f_{G,\mathbf{w},T}$ to the input $(G,\mathbf{w},T)$.

We need the following simple observations.

######  Lemma 8.

Let $G$ be a $K_{t}$-free graph and let $(H,\eta)$ be a rigid extended strip
decomposition of $G$. Then the maximum degree of $H$ is at most $t-1$.

######  Proof.

Let $x\in V(H)$. Observe that the sets $\\{\eta(xy,x)~{}|~{}y\in N_{H}(x)\\}$
are nonempty and complete to each other in $G$. Hence, $G$ contains a clique
of size equal to the degree of $x$ in $H$. $\square$

######  Lemma 9.

Let $G$ be a graph and let $(H,\eta)$ be an extended strip decomposition of
$G$ such that the maximum degree of $H$ is at most $d$. Then, every vertex of
$G$ is in at most $\max(4,2d+1)$ particles.

######  Proof.

Pick $v\in V(G)$ and observe that:

  * •

If $v\in\eta(x)$ for some $x\in V(H)$, then $v$ is in the vertex particle of
$x$ and in one half-edge and one full-edge particle for every edge of $H$
incident with $x$. Since there are at most $d$ such edges, $v$ is in at most
$2d+1$ particles.

  * •

If $v\in\eta(xy)$ for some $xy\in E(H)$, then $v$ is in at most four particles
for the edge $xy$.

  * •

If $v\in\eta(xyz)$ for some $xyz\in T(H)$, then $v$ is in the triangle
particle for $xyz$ and in three full edge particles, for the three sides of
the triangle $xyz$.

$\square$

##  3 Bounded-degree graphs: Proof of Theorem 1

This section is devoted to the proof of Theorem 1.

Let $t$ be a positive integer and let $(G,\mathbf{w})$ be the input vertex-
weighted graph. We denote $n:=|V(G)|$ and $\Delta$ to be the maximum degree of
$G$. Let

$\ell:=\lceil 11\log n+6\rceil(t+2)=\mathcal{O}(t\log n)$

be an upper bound on the size of $\bigcup\mathcal{P}$ for any application of
Theorem 3 for any induced subgraph of $G$.

We describe a recursive algorithm that takes as input an induced subgraph
$G^{\prime}$ of $G$ with weights $\mathbf{w}$ and a set of terminals
$T\subseteq V(G^{\prime})$ of size at most $4\ell\Delta^{2}$ and solves Border
MWIS on $(G^{\prime},\mathbf{w},T)$. The root call is for $G^{\prime}:=G$ and
$T:=\emptyset$; indeed, note that $f_{G,\mathbf{w},\emptyset}(\emptyset)$ is
the maximum possible weight of an independent set in $G$.

Let $(G^{\prime},\mathbf{w},T)$ be an input to a recursive call. First, the
algorithm initializes $f_{G^{\prime},\mathbf{w},T}(I_{T}):=-\infty$ for every
$I_{T}\subseteq T$.

If $|V(G^{\prime})|\leqslant 4\Delta^{2}\ell$, the algorithm proceeds by
brute-force: it enumerates independent sets $I\subseteq V(G^{\prime})$ and
updates $f_{G^{\prime},\mathbf{w},T}(I\cap T)$ with $\mathbf{w}(I)$ whenever
the previous value of that cell was smaller. As $\ell=\mathcal{O}(t\log n)$,
this step takes $n^{\mathcal{O}(t\Delta^{2})}$ time. This completes the
description of the leaf step of the recursion.

If $|V(G^{\prime})|>4\Delta^{2}\ell$, the algorithm proceeds as follows. If
$|T|\leqslant 3\Delta^{2}\ell$, let $U:=V(G^{\prime})$, and otherwise, let
$U:=T$. The algorithm invokes Theorem 3 on $G^{\prime}$ and $U$. If an induced
$S_{t,t,t}$ is returned, then it can be returned by the main algorithm as it
is in particular an induced subgraph of $G$. Hence, we can assume that we
obtain a set $X\subseteq V(G)$ of size at most $\ell$ and an extended strip
decomposition $(H,\eta)$ of $G^{\ast}:=G^{\prime}-N_{G^{\prime}}[X]$ whose
every particle contains at most $|U|/2$ vertices of $U$.

Observe that as $|X|\leqslant\ell$ and the maximum degree of $G$ is $\Delta$,
we have $|N_{G^{\prime}}(N_{G^{\prime}}[X])|\leqslant\Delta^{2}\ell$. Let
$T^{\ast}:=(T\cap V(G^{\ast}))\cup N_{G^{\prime}}(N_{G^{\prime}}[X])$. Note
that we have $T^{\ast}\subseteq V(G^{\ast})$ and $|T^{\ast}|\leqslant
5\Delta^{4}\ell$. For every particle $A$ of $(H,\eta)$, invoke a recursive
call on $(G^{\ast}_{A}:=G^{\ast}[A],\mathbf{w},T^{\ast}_{A}:=T^{\ast}\cap A)$,
obtaining $f_{G^{\ast}_{A},\mathbf{w},T^{\ast}_{A}}$ (or an induced
$S_{t,t,t}$, which can be directly returned). Use Lemma 7 to obtain a solution
$f_{G^{\ast},\mathbf{w},T^{\ast}}$ to Border MWIS instance
$(G^{\ast},\mathbf{w},T^{\ast})$.

Finally, iterate over every $I_{T}\subseteq T^{\ast}\cup N_{G^{\prime}}[X]$
(note that $T\subseteq T^{\ast}\cup N_{G^{\prime}}[X]$) and, if $I_{T}$ is
independent, update the cell $f_{G^{\prime},\mathbf{w},T}(I_{T}\cap T)$ with
the value $\mathbf{w}(I_{T}\setminus
T^{\ast})+f_{G^{\ast},\mathbf{w},T^{\ast}}(I_{T}\cap T^{\ast})$, if this value
is larger than the previous value of this cell. This completes the description
of the algorithm.

The correctness of the algorithm is immediate thanks to Lemma 7 and the fact
that $N_{G^{\prime}}[X]$ is adjacent in $G^{\prime}$ only to
$N_{G^{\prime}}(N_{G^{\prime}}[X])$ which is a subset of $T^{\ast}$.

For the complexity analysis, consider a recursive call to
$(G^{\ast}_{A},\mathbf{w},T^{\ast}_{A})$ for a particle $A$. If $|T|\leqslant
3\Delta^{2}\ell$, then $|T^{\ast}_{A}|\leqslant|T^{\ast}|\leqslant
4\Delta^{2}\ell$. Otherwise, $U=T$ and $|T\cap A|\leqslant|T|/2\leqslant
2\Delta^{2}\ell$. As
$|N_{G^{\prime}}(N_{G^{\prime}}[X])|\leqslant\Delta^{2}\ell$, we have
$|T^{\ast}_{A}|\leqslant 3\Delta^{2}\ell$. Hence, in the recursive call the
invariant of at most $4\Delta^{2}\ell$ terminals is maintained and, moreover:

  * •

if $|T|\leqslant 3\Delta^{2}\ell$, then $U=|V(G^{\prime})|$ and
$|V(G^{\ast}_{A})|=|A|\leqslant|V(G^{\prime})|/2$;

  * •

otherwise, $V(G^{\ast}_{A})\subseteq V(G^{\prime})$ and
$|T^{\ast}_{A}|\leqslant 3\Delta^{2}\ell$, hence the recursive call will fall
under the first bullet.

We infer that the depth of the recursion is at most $2\lceil\log n\rceil$.

At every non-leaf recursive call, we spend $n^{\mathcal{O}_{t}(1)}$ time on
invoking the algorithm from Theorem 3, $n^{\mathcal{O}(t\Delta^{2})}$ time to
compute $f_{G^{\ast},\mathbf{w},T^{\ast}}$ using Lemma 7, and
$n^{\mathcal{O}(t\Delta^{2})}$ time for the final iteration over all subsets
$I_{T}\subseteq T^{\ast}\cup N_{G^{\prime}}[X]$. Hence, the time spent at
every recursive call is bounded by
$n^{\mathcal{O}(t\Delta^{2})+\mathcal{O}_{t}(1)}$.

At every non-leaf recursive call, we make subcalls to
$(G^{\ast}_{A},\mathbf{w},T_{A}^{\ast})$ for every particle $A$ of $(H,\eta)$.
Lemmata 8 and 9 ensure that the sum of $|V(G^{\ast}_{A})|$ over all particles
$A$ is bounded by $(2\Delta+3)|V(G^{\prime})|$. Hence, the total size of all
graphs in the $i$-th level of the recursion is bounded by
$n\cdot(2\Delta+3)^{i}$. Since the depth of the recursion is bounded by
$2\lceil\log n\rceil$, the total size of all graphs in the recursion tree is
bounded by $n^{\mathcal{O}(\log\Delta)}$. Since this also bounds the size of
the recursion tree, we infer that the whole algorithm runs in time
$n^{\mathcal{O}(t\Delta^{2})+\mathcal{O}_{t}(1)}$.

This completes the proof of Theorem 1.

##  4 Graphs with no large bicliques: Proof of Theorem 2

This section is devoted to the proof of Theorem 2.

Let $t$ be a positive integer and let $k$ be the constant depending on $t$
from Corollary 6. Again, let $(G,\mathbf{w})$ be the input vertex-weighted
graph, let $n:=|V(G)|$, and let

$\ell:=\lceil 11\log n+6\rceil(t+2)=\mathcal{O}(t\log n)$

be an upper bound on the size of $\bigcup\mathcal{P}$ for any application of
Theorem 3 for any induced subgraph of $G$.

The general framework and the leaves of the recursion are almost exactly the
same as in the previous section, but with different thresholds. That is, we
describe a recursive algorithm that takes as input an induced subgraph
$G^{\prime}$ of $G$ with weights $\mathbf{w}$ and a set of terminals
$T\subseteq V(G^{\prime})$ of size at most $32k^{5}\ell$ and solves Border
MWIS on $(G^{\prime},\mathbf{w},T)$. The root call is for $G^{\prime}:=G$ and
$T:=\emptyset$ and the algorithm returns
$f_{G,\mathbf{w},\emptyset}(\emptyset)$ as the final answer.

Let $(G^{\prime},\mathbf{w},T)$ be an input to a recursive call. The algorithm
initiates first $f_{G^{\prime},\mathbf{w},T}(I_{T})=-\infty$ for every
$I_{T}\subseteq T$.

If $|V(G^{\prime})|\leqslant 32k^{5}\ell$, the algorithm proceeds by brute-
force: it enumerates independent sets $I\subseteq V(G^{\prime})$ and updates
$f_{G^{\prime},\mathbf{w},T}(I\cap T)$ with $\mathbf{w}(I)$ whenever the
previous value of that cell was smaller. As $\ell=\mathcal{O}(t\log n)$ and
$k$ is a constant depending on $t$, this step takes polynomial time. This
completes the description of the leaf step of the recursion.

Otherwise, if $|V(G^{\prime})|>32k^{5}\ell$, we invoke Corollary 6 on
$G^{\prime}$, obtaining a tree decomposition $(\mathcal{T},\beta)$ of
$G^{\prime}$. If $|T|\leqslant 24k^{5}\ell$, let $U:=V(G^{\prime})\setminus
T$, and otherwise, let $U:=T$.

For every $t_{1}t_{2}\in E(\mathcal{T})$, proceed as follows. For $i=1,2$, let
$\mathcal{T}_{i}$ be the connected component of $\mathcal{T}-\\{t_{1}t_{2}\\}$
that contains $t_{i}$ and let
$V_{i}=\bigcup_{x\in\mathcal{T}_{i}}\beta(x)\setminus\sigma(t_{1}t_{2})$.
Clearly, $\sigma(t_{1}t_{2})$ separates $V_{1}$ from $V_{2}$. Orient the edge
$t_{1}t_{2}$ towards $t_{i}$ with larger $|U\cap V_{i}|$, breaking ties
arbitrarily.

There exists $t\in V(\mathcal{T})$ of outdegree $0$. Then, for every connected
component $C$ of $G^{\prime}-\beta(t)$ we have $|C\cap U|\leqslant|U|/2$. Fix
one such node $t$ and let $B:=\beta(t)$ and let $\mathcal{C}$ be the set of
connected components of $G^{\prime}-B$. Let $G^{B}$ be a supergraph of
$G^{\prime}[B]$ obtained from $G^{\prime}[B]$ by turning, for every
$C\in\mathcal{C}$, the neighborhood $N_{G^{\prime}}(C)$ into a clique. Note
that $G^{B}$ is a subgraph of the torso of $\beta(t)$. Hence, by the
properties promised by Corollary 6, for every $C\in\mathcal{C}$ we have
$|N_{G^{\prime}}(C)|<k$ (as this set is contained in a single adhesion of an
edge incident with $t$ in $\mathcal{T}$) and $G^{B}$ contains at most $k$
vertices of degree larger than $2k(k-1)$. Let $Q$ be the set of vertices of
$G^{B}$ of degree larger than $2k(k-1)$.

We perform exhaustive branching on $Q$. That is, we iterate over all
independent sets $J\subseteq Q$ and denote
$G^{J}:=G^{\prime}-Q-N_{G^{\prime}}(J)$, $T^{J}:=T\cap V(G^{J})$,
$U^{J}:=U\cap V(G^{J})$. For one $J$, we proceed as follows.

We invoke Theorem 3 to $G^{J}$ with set $U^{J}$, obtaining a set $X^{J}$ of
size at most $\ell$ and an extended strip decomposition $(H^{J},\eta^{J})$ of
$G^{J}-N_{G^{J}}[X^{J}]$ whose every particle has at most
$|U^{J}|/2\leqslant|U|/2$ vertices of $U$. Note that $G^{J}$ is an induced
subgraph of $G^{\prime}$, which is an induced subgraph of $G$, so there is no
induced $S_{t,t,t}$ in $G^{J}$.

A component $C\in\mathcal{C}$ is _dirty_ if $N_{G^{J}}[X^{J}]\cap
N_{G^{\prime}}[C]\neq\emptyset$ and _clean_ otherwise. Let

$Y^{J}:=(N_{G^{J}}[X^{J}]\cap B)\cup\bigcup_{C\in\mathcal{C}:C\mathrm{\ is\
dirty}}(N_{G^{\prime}}(C)\cap V(G^{J})).$

The following bounds will be important for further steps.

$|N_{G^{J}}[X^{J}]\cap B|\leqslant(2k(k-1)+1)|X^{J}|.$ (1)

To see (1) observe that a vertex $v\in X^{J}\cap B$ has at most $2k(k-1)$
neighbors in $B$ (as every vertex of $B\setminus Q$ has degree at most
$2k(k-1)$ in $G_{B}$) while every vertex $v\in X^{J}\setminus B$ has at most
$k$ neighbors in $B$, as every component of $G^{\prime}-B$ has at most $k$
neighbors in $B$. This proves (1).

$|Y^{J}|\leqslant(k+(2k(k-1)+1)^{2})|X^{J}|\leqslant 4k^{4}|X^{J}|\leqslant
4k^{4}\ell=\mathcal{O}(k^{4}t\log n).$ (2)

To see (2), consider a dirty component $C\in\mathcal{C}$. Observe that either
$C$ contains a vertex of $X^{J}$ or $N_{G^{\prime}}(C)\cap V(G^{J})$ contains
a vertex of $N_{G^{J}}[X^{J}]\cap B$. There are at most $|X^{J}|$ dirty
components of the first type, contributing in total at most $k|X^{J}|$
vertices to $Y^{J}$. For the dirty components of the second type, although
there can be many of them, we observe that if $v\in N_{G^{\prime}}(C)\cap
N_{G^{J}}[X^{J}]\cap B$, then $N_{G^{\prime}}(C)\cap V(G^{J})\subseteq
N_{G_{B}}[v]$. Hence, for every dirty component of the second type, it holds
that $N_{G^{\prime}}(C)\cap V(G^{J})\subseteq N_{G_{B}}[N_{G^{J}}[X^{J}]\cap
B]$. Since the degree of each vertex of $G_{B}$ is at most $2k(k-1)$, by (1)
we have

$\left|N_{G_{B}}\left[N_{G^{J}}[X^{J}]\cap
B\right]\right|\leqslant(2k(k-1)+1)^{2}|X^{J}|.$

The bound (2) follows.

A component $C\in\mathcal{C}$ is _touched_ if it is dirty or
$N_{G^{\prime}}(C)$ contains a vertex of $Y^{J}$. Let

$Z^{J}:=(N_{G^{J}}[Y^{J}]\cap B)\cup\bigcup_{C\in\mathcal{C}:C\mathrm{\ is\
touched}}N_{G^{\prime}}(C)\cap V(G^{J}).$

Using similar arguments as before, we can prove

$|Z^{J}|\leqslant(2k(k-1)+1)|Y^{J}|\leqslant 8k^{5}|X^{J}|\leqslant
8k^{5}\ell=\mathcal{O}(k^{5}t\log n).$ (3)

Indeed, if $C$ is touched, then $N_{G^{\prime}}(C)$ contains a vertex $v\in
Y^{J}$ (if $C$ is dirty, $N_{G^{\prime}}(C)\cap V(G^{J})$ is contained in
$Y^{J}$), and then $N_{G^{\prime}}(C)$ is contained in $N_{G_{B}}[v]$. Also,
for $v\in Y^{J}$ we have $N_{G^{J}}[v]\cap B\subseteq N_{G_{B}}[v]$. Hence,
$Z^{J}\subseteq N_{G_{B}}[Y^{J}]$. Since the maximum degree of a vertex of
$B\setminus Q$ is $2k(k-1)$, this proves (3).

For every touched $C\in\mathcal{C}$, denote
$G_{C}:=G^{J}[N_{G^{\prime}}[C]\cap V(G^{J})]$ and $T_{C}:=((T\cap C)\cup
N_{G^{\prime}}(C))\cap V(G^{J})$. Recurse on $(G_{C},\mathbf{w},T_{C})$,
obtaining $f_{G_{C},\mathbf{w},T_{C}}$.

Let

$G^{Y}:=G^{J}-Y^{J}-\bigcup_{C\in\mathcal{C}:C\mathrm{\ is\ touched}}C.$

Note that, by the definition of dirty and touched, $G^{Y}$ is an induced
subgraph of $G^{J}-N_{G^{J}}[X^{J}]$. Hence, $(H^{J},\eta^{J})$ can be
restricted to a (not necessarily rigid) extended strip decomposition
$(H^{J},\eta^{J,Y})$ of $G^{Y}$.

Let $T^{Y}:=(T\cup Z^{J})\cap V(G^{Y})$. For every particle $A$ of
$(H^{J},\eta^{J,Y})$, recurse on $(G^{Y}[A],\mathbf{w},T^{Y}\cap A)$,
obtaining $f_{G^{Y}[A],\mathbf{w},T^{Y}\cap A}$. Then, use these values with
Lemma 7 to solve a Border MWIS instance $(G^{Y},\mathbf{w},T^{Y})$, obtaining
$f_{G^{Y},\mathbf{w},T^{Y}}$.

Iterate over every independent set $I_{T}\subseteq(T\cap V(G^{J}))\cup
T^{Y}\cup Y^{J}$. Observe that $G^{\prime}$ admits an independent set $I$ with
$I\cap(Q\cup T\cup T^{Y}\cup Y^{J})=J\cup I_{T}$ and weight:

$\mathbf{w}(J)+\mathbf{w}(I_{T}\setminus
T^{Y})+f_{G^{Y},\mathbf{w},T^{Y}}(I_{T}\cap
T^{Y})+\sum_{C\in\mathcal{C}:C\mathrm{\ is\
touched}}\left(f_{G_{C},\mathbf{w},T_{C}}(N_{G^{\prime}}[C]\cap
I_{T})-\mathbf{w}(I_{T}\cap N_{G^{\prime}}(C))\right).$

Update the cell $f_{G^{\prime},\mathbf{w},T}((I_{T}\cup J)\cap T)$ with this
value if it is larger than the previous value of this cell. This finishes the
description of the algorithm.

For correctness, it suffices to note that for every touched component $C$, the
whole $N_{G^{\prime}}(C)\cap V(G^{J})$ is in the terminal set for the
recursive call $(G_{C},\mathbf{w},T_{C})$ and the whole $N_{G^{\prime}}(C)\cap
V(G^{Y})$ is in $Z^{J}$ and thus in the terminal set for the Border MWIS
instance $(G^{Y},\mathbf{w},T^{Y})$.

For the sake of analysis, consider a recursive call on
$(G_{C},\mathbf{w},T_{C})$ for a touched component $C$. If $|T|\leqslant
24k^{5}\ell$ and $U=V(G^{\prime})\setminus T$, then
$|T_{C}|\leqslant|T|+k\leqslant 32k^{5}\ell$ and $|V(G_{C})\setminus
T_{C}|\leqslant|C\setminus T|\leqslant|V(G^{\prime})\setminus T|/2$.
Otherwise, if $|T|>24k^{5}\ell$ and $U=T$, then
$|T_{C}|\leqslant|T|/2+k\leqslant 16k^{5}\ell+k\leqslant 24k^{5}\ell$. Thus,
the recursive call on $(G_{C},\mathbf{w},T_{C})$ will fall under the first
case of at most $24k^{5}\ell$ terminals.

Analogously, consider a recursive call on $(G^{Y}[A],\mathbf{w},T^{Y}\cap A)$
for a particle $A$ of $(H^{J},\eta^{J,Y})$. If $|T|\leqslant 24k^{5}\ell$ and
$U=V(G^{\prime})\setminus T$, then $|T^{Y}\cap
A|\leqslant|T^{Y}|\leqslant|T|+|Z^{J}|\leqslant 32k^{5}\ell$ due to (3).
Furthermore, $|V(G^{Y}[A])\setminus T^{Y}|\leqslant|V(G^{\prime})\setminus
T|/2$. Otherwise, if $|T|>24k^{5}\ell$ and $U=T$, then $|T^{Y}\cap
A|\leqslant|T|/2+|Z^{J}|\leqslant 16k^{5}\ell+8k^{5}\ell\leqslant 24k^{5}\ell$
again due to (3). Thus, the recursive call on $(G^{Y}[A],\mathbf{w},T^{Y}\cap
A)$ will fall under the first case of at most $24k^{5}\ell$ terminals.

Finally, note that a recursive call $(G^{\prime},\mathbf{w},T)$ without
nonterminal vertices (i.e., with $T=V(G^{\prime})$) is a leaf call.

We infer that all recursive calls satisfy the invariant of at most
$32k^{5}\ell$ terminals and the depth of the recursion tree is bounded by
$2\lceil\log n\rceil$ (as every second level the number of nonterminal
vertices halves).

At each recursive call, we iterate over at most $2^{k}$ subsets $J\subseteq
Q$. Lemma 8 ensures that the maximum degree of $H^{J}$ is at most $2t-1$,
while Lemma 9 ensures that every vertex of $G^{Y}$ is used in at most $4t$
particles of $(H^{J},\eta^{J,Y})$. In a subcall $(G_{C},\mathbf{w},T_{C})$ for
a touched component $C$, vertices of $C$ are not used in any other call for
the current choice of $J$, while all vertices of $V(G_{C})\setminus C$ are
terminals. Consequently, every nonterminal vertex $v$ of $G^{\prime}$ is
passed as a nonterminal vertex to a recursive subcall at most $2^{k}\cdot 4t$
number of times (and a terminal is always passed to a subcall as a terminal).
Furthermore, a recursive call without nonterminal vertices is a leaf call. As
the depth of the recursion is $\mathcal{O}(\log n)$, we infer that, summing
over all recursive calls in the entire algorithm, the number of nonterminal
vertices is bounded by $n^{\mathcal{O}(\log t+k)}$ and the total size of the
recursion tree is $n^{\mathcal{O}(\log t+k)}$.

At each recursive call, we iterate over all $2^{k}$ subsets $J\subseteq Q$ and
then we invoke Theorem 3 and iterate over all independent sets $I_{T}$ in
$(T\cap V(G^{J}))\cup T^{Y}\cup Y^{J}$. Thanks to the invariant $|T|\leqslant
32k^{5}\ell$ and bounds (2), and (3), this set is of size
$\mathcal{O}(k^{5}\ell)$. Hence, every recursive call runs in time
$n^{\mathcal{O}(k^{5}t)+k\mathcal{O}_{t}(1)}$. As $k$ is a constant depending
on $t$ only, the final running time bound is polynomial.

This completes the proof of Theorem 2.

##  5 Conclusion

Let us remark that it is very easy to lift theorem 1 to the class of bounded-
degree $H$-free graphs, where every component of $H$ is a subdivided claw, see
[1, 34]. However, it is far from clear how to do it in the setting of theorem
2.

While it is generally believed that MWIS is polynomial-time-solvable in
$S_{t,t,t}$-free graphs (with no further assumptions), such a result seems
currently out of reach. Thus is is interesting to investigate how further can
we relax the assumptions on instances, as we did when going from theorem 1 to
theorem 2. In particular, we used the assumption of $K_{t}$-freeness twice:
once in lemma 5 and then to argue that $H$ (the pattern of an extended strip
decomposition we obtain) is of bounded degree. On the other hand, the
assumption of $K_{t,t}$-freeness was used just once: in lemma 5. Thus it seems
natural to try to prove the following conjecture.

######  Conjecture 10.

For every integer $t$ there exists a polynomial-time algorithm that, given an
$S_{t,t,t}$-free and $K_{t}$-free vertex-weighted graph $(G,\mathbf{w})$
computes the maximum possible weight of an independent set in
$(G,\mathbf{w})$.

### Acknowledgements

We acknowledge the welcoming and productive atmosphere at Dagstuhl Seminar
22481 “Vertex Partitioning in Graphs: From Structure to Algorithms,” where a
crucial part of the work leading to the results in this paper was done.

## References

  * [1] Tara Abrishami, Maria Chudnovsky, Cemil Dibek, and Paweł Rzążewski.  Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws.  In Niv Buchbinder Joseph (Seffi) Naor, editor, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference, January 9-12, 2022, pages 1448–1470. SIAM, 2022.  doi:10.1137/1.9781611977073.61.
  * [2] Vladimir E. Alekseev.  The effect of local constraints on the complexity of determination of the graph independence number.  Combinatorial-algebraic methods in applied mathematics, pages 3–13, 1982.
  * [3] Vladimir E. Alekseev.  On easy and hard hereditary classes of graphs with respect to the independent set problem.  Discret. Appl. Math., 132(1-3):17–26, 2003.  doi:10.1016/S0166-218X(03)00387-1.
  * [4] Vladimir E. Alekseev.  Polynomial algorithm for finding the largest independent sets in graphs without forks.  Discrete Applied Mathematics, 135(1):3 – 16, 2004.  Russian Translations II.  URL: http://www.sciencedirect.com/science/article/pii/S0166218X02002901, doi:https://doi.org/10.1016/S0166-218X(02)00290-1.
  * [5] Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan van Leeuwen.  Subexponential-time algorithms for Maximum Independent Set in $P_{t}$-free and broom-free graphs.  Algorithmica, 81(2):421–438, 2019.  doi:10.1007/s00453-018-0479-5.
  * [6] Andreas Brandstädt and Raffaele Mosca.  Maximum weight independent sets for ($P_{7}$, triangle)-free graphs in polynomial time.  Discret. Appl. Math., 236:57–65, 2018.  doi:10.1016/j.dam.2017.10.003.
  * [7] Andreas Brandstädt and Raffaele Mosca.  Maximum weight independent sets for (${P}_{7}$, triangle)-free graphs in polynomial time.  Discret. Appl. Math., 236:57–65, 2018.  doi:10.1016/j.dam.2017.10.003.
  * [8] Andreas Brandstädt and Raffaele Mosca.  Maximum weight independent sets for ($S_{1,2,4}$,triangle)-free graphs in polynomial time.  Theor. Comput. Sci., 878-879:11–25, 2021.  doi:10.1016/j.tcs.2021.05.027.
  * [9] Christoph Brause.  A subexponential-time algorithm for the Maximum Independent Set Problem in $P_{t}$-free graphs.  Discret. Appl. Math., 231:113–118, 2017.  doi:10.1016/j.dam.2016.06.016.
  * [10] Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk.  Designing FPT algorithms for cut problems using randomized contractions.  SIAM J. Comput., 45(4):1171–1229, 2016.  doi:10.1137/15M1032077.
  * [11] Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé.  Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in $H$-free graphs.  CoRR, abs/1907.04585, 2019.  arXiv:1907.04585.
  * [12] Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé.  Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in $H$-free graphs.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2260–2278. SIAM, 2020.  doi:10.1137/1.9781611975994.139.
  * [13] Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, and Kristina Vuskovic.  Maximum independent sets in (pyramid, even hole)-free graphs.  CoRR, abs/1912.11246, 2019.  URL: http://arxiv.org/abs/1912.11246, arXiv:1912.11246.
  * [14] M. Cygan, F. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized algorithms.  Springer, 2015.
  * [15] Peter Gartland and Daniel Lokshtanov.  Independent set on ${P}_{k}$-free graphs in quasi-polynomial time.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613–624. IEEE, 2020.  doi:10.1109/FOCS46700.2020.00063.
  * [16] Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski.  Maximum weight independent set in graphs with no long claws in quasi-polynomial time.  CoRR, abs/2305.15738, 2023.  arXiv:2305.15738, doi:10.48550/arXiv.2305.15738.
  * [17] Michael U. Gerber, Alain Hertz, and Vadim V. Lozin.  Stable sets in two subclasses of banner-free graphs.  Discrete Applied Mathematics, 132(1-3):121–136, 2003.  doi:10.1016/S0166-218X(03)00395-0.
  * [18] Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk.  Polynomial-time algorithm for Maximum Weight Independent Set on $P_{6}$-free graphs.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1257–1271. SIAM, 2019.  doi:10.1137/1.9781611975482.77.
  * [19] M. Grötschel, L. Lovász, and A. Schrijver.  Polynomial algorithms for perfect graphs.  In C. Berge and V. Chvátal, editors, Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325–356. North-Holland, 1984.  URL: https://www.sciencedirect.com/science/article/pii/S0304020808729438, doi:https://doi.org/10.1016/S0304-0208(08)72943-8.
  * [20] Ararat Harutyunyan, Michael Lampis, Vadim V. Lozin, and Jérôme Monnot.  Maximum independent sets in subcubic graphs: New results.  Theor. Comput. Sci., 846:14–26, 2020.  doi:10.1016/j.tcs.2020.09.010.
  * [21] Johan Håstad.  Clique is hard to approximate within $n^{{(1-\varepsilon)}}$.  In Acta Mathematica, pages 627–636, 1996.
  * [22] Richard M. Karp.  Reducibility among combinatorial problems.  In Complexity of Computer Computations, pages 85–103. Springer US, 1972.  doi:10.1007/978-1-4684-2001-2_9.
  * [23] Ken-ichi Kawarabayashi and Mikkel Thorup.  The minimum $k$-way cut of bounded size is fixed-parameter tractable.  In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 160–169. IEEE Computer Society, 2011.  doi:10.1109/FOCS.2011.53.
  * [24] T. Kövari, V. Sós, and P. Turán.  On a problem of k. zarankiewicz.  Colloquium Mathematicae, 3(1):50–57, 1954.  URL: http://eudml.org/doc/210011.
  * [25] Ngoc Chi Lê, Christoph Brause, and Ingo Schiermeyer.  The Maximum Independent Set Problem in subclasses of $S_{i,j,k}$-free graphs.  Electron. Notes Discret. Math., 49:43–49, 2015.  doi:10.1016/j.endm.2015.06.008.
  * [26] Daniel Lokshantov, Martin Vatshelle, and Yngve Villanger.  Independent set in $P_{5}$-free graphs in polynomial time.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 570–581. SIAM, 2014.  doi:10.1137/1.9781611973402.43.
  * [27] Vadim V. Lozin and Martin Milanic.  A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.  J. Discrete Algorithms, 6(4):595–604, 2008.  doi:10.1016/j.jda.2008.04.001.
  * [28] Vadim V. Lozin, Martin Milanic, and Christopher Purcell.  Graphs without large apples and the Maximum Weight Independent Set problem.  Graphs Comb., 30(2):395–410, 2014.  doi:10.1007/s00373-012-1263-y.
  * [29] Vadim V. Lozin, Jérôme Monnot, and Bernard Ries.  On the maximum independent set problem in subclasses of subcubic graphs.  J. Discrete Algorithms, 31:104–112, 2015.  doi:10.1016/j.jda.2014.08.005.
  * [30] Vadim V. Lozin and Raffaele Mosca.  Independent sets in extensions of $2{K}_{2}$-free graphs.  Discret. Appl. Math., 146(1):74–80, 2005.  doi:10.1016/j.dam.2004.07.006.
  * [31] Vadim V. Lozin and Dieter Rautenbach.  Some results on graphs without long induced paths.  Inf. Process. Lett., 88(4):167–171, 2003.  doi:10.1016/j.ipl.2003.07.004.
  * [32] Vadim V. Lozin and Igor Razgon.  Tree-width dichotomy.  Eur. J. Comb., 103:103517, 2022.  doi:10.1016/j.ejc.2022.103517.
  * [33] Frédéric Maffray and Lucas Pastor.  Maximum weight stable set in (${P}_{7}$, bull)-free graphs.  CoRR, abs/1611.09663, 2016.  URL: http://arxiv.org/abs/1611.09663.
  * [34] Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski.  Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás’ Path Argument.  In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 93:1–93:19, Dagstuhl, Germany, 2022\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ICALP.2022.93.
  * [35] George J. Minty.  On maximal independent sets of vertices in claw-free graphs.  Journal of Combinatorial Theory, Series B, 28(3):284–304, 1980\.  doi:https://doi.org/10.1016/0095-8956(80)90074-X.
  * [36] Raffaele Mosca.  Stable sets in certain ${P}_{6}$-free graphs.  Discret. Appl. Math., 92(2-3):177–191, 1999.  doi:10.1016/S0166-218X(99)00046-3.
  * [37] Raffaele Mosca.  Stable sets of maximum weight in (${P}_{7}$, banner)-free graphs.  Discrete Mathematics, 308(1):20–33, 2008.  doi:10.1016/j.disc.2007.03.044.
  * [38] Raffaele Mosca.  Independent sets in (${P}_{6}$, diamond)-free graphs.  Discret. Math. Theor. Comput. Sci., 11(1):125–140, 2009.  doi:10.46298/dmtcs.473.
  * [39] Raffaele Mosca.  Maximum weight independent sets in (${P}_{6}$, co-banner)-free graphs.  Inf. Process. Lett., 113(3):89–93, 2013.  doi:10.1016/j.ipl.2012.10.004.
  * [40] Raffaele Mosca.  Independent sets in (${P}_{4+4}$, triangle)-free graphs.  Graphs Comb., 37(6):2173–2189, 2021.  doi:10.1007/s00373-021-02340-7.
  * [41] Marcin Pilipczuk, Michał Pilipczuk, and Pawel Rzążewski.  Quasi-polynomial-time algorithm for independent set in $P_{t}$-free graphs via shrinking the space of induced paths.  In Hung Viet Le and Valerie King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 204–209. SIAM, 2021.  doi:10.1137/1.9781611976496.23.
  * [42] Najiba Sbihi.  Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile.  Discrete Mathematics, 29(1):53–76, 1980.  doi:https://doi.org/10.1016/0012-365X(90)90287-R.
  * [43] Daniel Weißauer.  On the block number of graphs.  SIAM J. Discret. Math., 33(1):346–357, 2019.  doi:10.1137/17M1145306.
  * [44] Nikola Yolov.  Minor-matching hypertree width.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 219–233. SIAM, 2018.  doi:10.1137/1.9781611975031.16.

##  Appendix A Appendix: Proof of Lemma 7

Iterate over every $I_{T}\subseteq T$. For fixed $I_{T}$, we aim at computing
$f_{G,\mathbf{w},T}(I_{T})$. If $I_{T}$ is not independent, we set
$f_{G,\mathbf{w},T}(I_{T})=-\infty$. In the remainder of the proof, we show
how to compute in polynomial time the value $f_{G,\mathbf{w},T}(I_{T})$ for
fixed independent $I_{T}\subseteq T$.

For a particle $A$ of $(H,\eta)$, let $a(A):=f_{G[A],\mathbf{w},T\cap
A}(I_{T}\cap A)$ and let $I(A)$ be an independent set witnessing this value,
that is, an independent set in $G[A]$ of weight $\mathbf{w}(a(A))$ with
$I(A)\cap T\cap A=I_{T}\cap A$. Note that as $I_{T}$ is independent, the value
$a(A)$ is not equal to $-\infty$ and such an independent set exists.

We say that $x\in V(H)$ is _forced_ if $I_{T}\cap\bigcup_{y\in
N_{H}(x)}\eta(xy,x)\neq\emptyset$. Note that since $I_{T}$ is independent, if
$x$ is forced, then $\eta(xy,x)\cap I_{T}\neq\emptyset$ for exactly one edge
$xy$ incident with $x$. We call such an edge $xy$ the _enforcer_ of $x$. Note
that an edge $xy$ may be the enforcer of both $x$ and $y$.

The arguments now follow very closely the outline of Section 3.3 of [11].

We construct a set $\mathcal{P}$ of particles and an edge-weighted graph
$(H^{\prime},\mathbf{w}^{\prime})$ as follows. We start with
$\mathcal{P}=\emptyset$, $V(H^{\prime})=V(H)$, and $E(H^{\prime})=\emptyset$.

For every $x\in V(H)$ that is not forced, add $A_{x}$ to $\mathcal{P}$. For
every $xyz\in T(H)$ such that neither of the edges $xy$, $yz$, or $xz$ is the
enforcer of _both_ its endpoints, add $A_{xyz}$ to $\mathcal{P}$. For every
$e=xy\in E(H)$, proceed as follows.

  1. 1.

If neither $x$ nor $y$ is forced, we add to $H^{\prime}$ a new vertex $t_{e}$
and edges $t_{e}x$, $t_{e}y$, $xy$, and set the edge weights
$\mathbf{w}^{\prime}$ as follows:

$\displaystyle\mathbf{w}^{\prime}(t_{e}x)$
$\displaystyle:=a(A_{xy}^{x})-a(A_{xy}^{\bot})-a(A_{x}),$
$\displaystyle\mathbf{w}^{\prime}(t_{e}y)$
$\displaystyle:=a(A_{xy}^{y})-a(A_{xy}^{\bot})-a(A_{y}),$
$\displaystyle\mathbf{w}^{\prime}(xy)$
$\displaystyle:=a(A_{xy}^{xy})-a(A_{xy}^{\bot})-a(A_{x})-a(A_{y})-\sum_{z,\text{
s.t. }xyz\in T(H)}a(A_{xyz}).$

Furthermore, add $A_{xy}^{\bot}$ to $\mathcal{P}$.

  2. 2.

If exactly one of $x$ and $y$ is forced, say w.l.o.g. $x$ is forced and $y$ is
not forced, proceed as follows.

    1. (a)

If $xy$ is the enforcer of $x$, then add to $H^{\prime}$ an edge $xy$ with
weight

$\mathbf{w}^{\prime}(xy):=a(A_{xy}^{xy})-a(A_{xy}^{x})-a(A_{y})-\sum_{z,\text{
s.t. }xyz\in T(H)}a(A_{xyz}).$

Furthermore, add $A_{xy}^{x}$ to $\mathcal{P}$.

    2. (b)

If $xy$ is not the enforcer of $x$, then add to $H^{\prime}$ a new vertex
$t_{e}$ and an edge $t_{e}y$ with weight

$\mathbf{w}^{\prime}(t_{e}y):=a(A_{xy}^{y})-a(A_{xy}^{\bot})-a(A_{y}).$

Furthermore, add $A_{xy}^{\bot}$ to $\mathcal{P}$.

  3. 3.

If both $x$ and $y$ are forced, proceed as follows.

    1. (a)

If $xy$ is neither the enforcer of $x$ nor of $y$, add $A_{xy}^{\bot}$ to
$\mathcal{P}$.

    2. (b)

If $xy$ is the enforcer of $x$ but not of $y$ add $A_{xy}^{x}$ to
$\mathcal{P}$.

    3. (c)

If $xy$ is the enforcer of $y$ but not of $x$ add $A_{xy}^{y}$ to
$\mathcal{P}$.

    4. (d)

If $xy$ is the enforcer of both $x$ and $y$, add $A_{xy}^{xy}$ to
$\mathcal{P}$.

This finishes the description of the construction of $\mathcal{P}$ and
$(H^{\prime},\mathbf{w}^{\prime})$. In the next two paragraphs we make two
observations that follow by a direct check from the definitions.

Observe that $I_{0}:=\bigcup_{A\in\mathcal{P}}I(A)$ is independent in $G$ and
has weight $a_{0}:=\sum_{A\in\mathcal{P}}a(A)$. Furthermore, for every
$A\in\mathcal{P}$, we have $I_{0}\cap A\cap T=I_{T}\cap A$ and $I_{0}\cap
T=I_{T}$. We think of $I_{0}$ as the “base” solution for
$f_{G,\mathbf{w},T}(I_{T})$.

Observe also that all weights $\mathbf{w}^{\prime}$ of $H^{\prime}$ are
nonnegative, as $A_{xy}^{x}$ contains both $A_{xy}^{\bot}$ and $A_{x}$ while
$A_{xy}^{xy}$ contains $A_{xy}^{\bot}$, $A_{x}$, $A_{y}$, as well as all
$A_{xyz}$ for all triangles $xyz$ containing the edge $xy$.

We will be asking for a maximum weight matching in
$(H^{\prime},\mathbf{w}^{\prime})$. Intuitively, taking an edge $t_{e}x$ to
such a matching corresponds to replacing in $I_{0}$ the parts
$I(A_{xy}^{\bot})$ and $I(A_{x})$ with the part $I(A_{xy}^{x})$ while taking
an edge $xy$ to such a matching corresponds to replacing in $I_{0}$ the parts
$I(A_{xy}^{\bot})$, $I(A_{x})$, $I(A_{y})$ and all parts $I(A_{xyz})$ for
triangles $xyz$ containing the edge $xy$ with part $I(A_{xy}^{xy})$.

From another perspective, fix $x\in V(H)$ and recall that the sets
$\eta(xy,x)$ for $y\in N_{H}(x)$ are complete to each other. Hence, any
independent set in $G$ can contain vertices in at most one of such sets. For
an edge $e=xy\in E(H)$, taking an edge $xy$ or $t_{e}x$ in a matching in
$H^{\prime}$ corresponds to choosing that, among all neighbors of $x$ in $H$,
the neighbor $y$ is such that the set $\eta(xy,x)$ is allowed to contain
vertices of the sought independent set. (Choosing $xy\in E(H^{\prime})$ to the
matching corresponds to allowing both $\eta(xy,x)$ and $\eta(yx,y)$ to contain
vertices of the sought independent set.)

However, there is a delicacy if $I_{T}$ contains a vertex of some interface
$\eta(xy,x)$. Then, in some sense $I_{T}$ already forces some choices in the
corresponding matching in $H^{\prime}$. This is modeled above by having
alternate construction for vertices $x\in V(H)$ that are forced.

The following two claims prove that $f_{G,\mathbf{w},T}(I_{T})$ equals $a_{0}$
plus the maximum possible weight of a matching in
$(H^{\prime},\mathbf{w}^{\prime})$ and thus complete the proof of Lemma 7.
Their proofs follow exactly the lines of the proofs of Claims 3.7 and 3.8 of
Section 3.3 of [11] and are thus omitted.

######  Claim 1.

Let $I$ be an independent set in $G$ with $I\cap T=I_{T}$. Let $M$ be the set
of edges of $H^{\prime}$ defined as follows: for every $e=xy\in E(H)$, if
$\eta(xy,x)\cap I\neq\emptyset$ and $\eta(xy,y)\cap I\neq\emptyset$, then
$xy\in M$, if $\eta(xy,x)\cap I\neq\emptyset$ and $\eta(xy,y)\cap
I=\emptyset$, then $t_{e}x\in M$, and if $\eta(xy,x)\cap I=\emptyset$ and
$\eta(xy,y)\cap I\neq\emptyset$, then $t_{e}y\in M$. Then, all the above edges
indeed exist in $H^{\prime}$ and $M$ is a matching. Furthermore, the weight of
$I$ is at most $a_{0}+\sum_{e\in M}\mathbf{w}^{\prime}(e)$.

######  Claim 2.

Let $M$ be a matching in $H^{\prime}$. Let $\mathcal{P}_{M}$ be the set of
particles of $(H,\eta)$ defined as follows. Start with
$\mathcal{P}_{M}:=\mathcal{P}$ and then for every edge $e=xy\in E(H)$,

  * •

if $xy\in M$, insert $A_{xy}^{xy}$ into $\mathcal{P}_{M}$ and remove from
$\mathcal{P}_{M}$ the following particles if present: $A_{xy}^{x}$,
$A_{xy}^{y}$, $A_{xy}^{\bot}$, $A_{x}$, $A_{y}$, $A_{xyz}$ for any $z\in V(H)$
such that $xyz\in T(H)$.

  * •

if $t_{e}x\in M$ (resp. $t_{e}y\in M$), insert $A_{xy}^{x}$ (resp.
$A_{xy}^{y}$) into $\mathcal{P}_{M}$, and remove from $\mathcal{P}_{M}$ the
following particles if present: $A_{xy}^{\bot}$ and $A_{x}$ (resp. $A_{y}$).

Then $I_{M}:=\bigcup_{A\in\mathcal{P}_{M}}$ is an independent set in $G$ with
$I_{M}\cap T=I_{T}$ and of weight at least $a_{0}+\sum_{e\in
M}\mathbf{w}^{\prime}(e)$.


$c_{n^{\prime\prime}+1}(\alpha)=-\frac{1}{f(\alpha+n^{\prime\prime}+1)}\sum_{k=0}^{n^{\prime\prime}-1}[(\alpha+k)a_{n^{\prime\prime}-k-1}+b_{n^{\prime\prime}-k-2}]c_{k}(\alpha),$

and hence

$\operatorname{LT}(c_{n^{\prime\prime}+1}(\alpha))=-\frac{1}{f(\alpha+n^{\prime\prime}+1)}\operatorname{LT}((\alpha+n^{\prime\prime}-1)a_{0}+b_{-1})\operatorname{LT}(c_{n^{\prime\prime}-1}(\alpha)),$

which, by (5.17), is equal to

$-\frac{\operatorname{LT}((\alpha+n^{\prime\prime}-1)a_{0}+b_{-1})}{f(\alpha+n^{\prime\prime}+1)}\prod_{k=1}^{n^{\prime\prime}-1}\left(-\frac{(\alpha+k-3/2)d_{1}r_{z_{j}}^{(1)}+d_{2}s_{z_{j}}^{(2)}}{f(\alpha+k)}\right).$

Then using (5.13) we can inductively show that for $n$ with
$n^{\prime\prime}+1\leq n\leq n^{\prime}-1$,

$\displaystyle\operatorname{LT}(c_{n}(\alpha))$
$\displaystyle=\operatorname{LT}(c_{n^{\prime\prime}+1}(\alpha))\prod_{k=n^{\prime\prime}+2}^{n}\left(-\frac{\operatorname{LT}((\alpha+k-1)a_{-1}+b_{-2})}{f(\alpha+k)}\right)$
$\displaystyle=\operatorname{LT}(c_{n^{\prime\prime}+1}(\alpha))\prod_{k=n^{\prime\prime}+2}^{n}\left(-\frac{(\alpha+k-3/2)d_{1}r_{z_{j}}^{(1)}+d_{2}s_{z_{j}}^{(2)}}{f(\alpha+i)}\right).$

Thus, for $(k_{1},k_{2})=(1,3)$, we have

$\displaystyle\operatorname{LT}(P_{z_{j},1,3}(\mathbf{r},\mathbf{s}))=\operatorname{LT}(c_{n^{\prime\prime}+1}(\alpha))\prod_{k=n^{\prime\prime}+2}^{n^{\prime}}\left(-\frac{(\alpha+k-3/2)d_{1}r_{z_{j}}^{(1)}+d_{2}s_{z_{j}}^{(2)}}{f(\alpha+k)}\right)$
$\displaystyle\hphantom{\operatorname{LT}(P_{z_{j},1,3}(\mathbf{r},\mathbf{s}))}{}=-\frac{\operatorname{LT}((\alpha+n^{\prime\prime}-1)a_{0}+b_{-1})}{f(\alpha+n^{\prime\prime}+1)}$
$\displaystyle\hphantom{\operatorname{LT}(P_{z_{j},1,3}(\mathbf{r},\mathbf{s}))=}{}\times\prod_{k=1,\,k\neq
n^{\prime\prime},n^{\prime\prime}+1}^{n^{\prime}}\left(-\frac{(\alpha+k-3/2)d_{1}r_{z_{j}}^{(1)}+d_{2}s_{z_{j}}^{(2)}}{f(\alpha+k)}\right).$

Note that $\operatorname{LT}((\alpha+n^{\prime\prime}-1)a_{0}+b_{-1})$ is of
the form

$d_{3}s_{z_{j}}^{(1)}+d_{1}^{\prime}r_{z_{1}}^{(1)}+\cdots+d_{m}^{\prime}r_{z_{m}}^{(1)},$

where $d_{3}$, $d_{1}^{\prime},\dots,d_{m}^{\prime}$ are complex numbers with
$d_{3}\neq 0$.

We next consider the case where $z_{0}={\rm i}$ is the elliptic point of order
$2$. There exists a unique pair of $k_{1}$ and $k_{2}$ with $k_{1}<k_{2}$ such
that $\kappa_{{\rm i}}^{(k_{2})}-\kappa_{{\rm i}}^{(k_{1})}\equiv 0\
\mathrm{mod}\ 2$. We let $\alpha=\kappa_{{\rm i}}^{(k_{1})}$ and
$n^{\prime}=\kappa_{{\rm i}}^{(k_{2})}-\kappa_{z_{0}}^{(k_{1})}$. We have seen
earlier that $c_{n}(\alpha)\neq 0$ only when $2|n$. Also, from (5.15), we can
inductively show that

$\operatorname{LT}(c_{n}(\alpha))=\prod_{k=1}^{n/2}\left(-\frac{\operatorname{LT}((\alpha+2k-2)a_{0}+b_{-1})}{f(\alpha+2k)}\right)$

and

$\operatorname{LT}(P_{{\rm
i}}(\mathbf{r},\mathbf{s}))=\prod_{k=1}^{n^{\prime}/2}\left(-\frac{\operatorname{LT}((\alpha+2k-2)a_{0}+b_{-1})}{f(\alpha+2k)}\right).$

Noting that $\operatorname{LT}((\alpha+2k-2)a_{0}+b_{-1}))=ds_{{\rm
i}}^{(1)}+(\text{a linear sum in }\mathbf{r})$ for some nonzero complex number
$d$ (which is the leading coefficient of the expansion of $\Delta(z)/E_{6}(z)$
at ${\rm i}$ in $\widetilde{w}$), we conclude that $\operatorname{LT}(P_{{\rm
i}}(\mathbf{r},\mathbf{s})$ is a product of $\big{(}\kappa_{{\rm
i}}^{(k_{2})}-\kappa_{{\rm i}}^{(k_{1})}\big{)}/2$ linear sums in $s_{{\rm
i}}^{(1)}$ and $\mathbf{r}$ with all coefficients of $s_{{\rm i}}^{(1)}$
nonzero. This completes the proof. ∎

######  Remark 5.12.

The proposition suggests that when the local exponents $\kappa$’s are fixed,
for generic points $z_{j}$, the number of pairs $(Q,R)$ of modular forms such
that (5.2) satisfies the conditions (S1)–(S3) is

$\frac{\kappa_{\rm i}^{(k_{2})}-\kappa_{\rm
i}^{(k_{1})}}{2}\prod_{j=1}^{m}\big{(}\kappa_{z_{j}}^{(2)}-\kappa_{z_{j}}^{(1)}\big{)}\big{(}\kappa_{z_{j}}^{(3)}-\kappa_{z_{j}}^{(2)}\big{)}\big{(}\kappa_{z_{j}}^{(3)}-\kappa_{z_{j}}^{(1)}-1\big{)},$

where $k_{1}$ and $k_{2}$ are the integers such that $\kappa_{\rm
i}^{(k_{2})}-\kappa_{\rm i}^{(k_{1})}\in 2\mathbb{N}$. (Notice that if
$\big{(}\kappa_{z}^{(1)},\kappa_{z}^{(2)},\kappa_{z}^{(3)}\big{)}=(0,1,2)$ for
all $z\in\mathbb{H}$, this number is $1$, as expected.) However, because the
polynomials have intersection of positive dimension at infinity in general, we
are not able to use the Bézout theorem to obtain this conclusion. (Even the
existence of $(Q,R)$ with an arbitrary set of given data is not established
yet.) We leave this problem for future study.

##  6 Extremal quasimodular forms

We note that by using some results in Section 5, Theorem 2.2 can be improved
in some special case. More precisely, the main result of this section is
Theorem 6.2 below, which states that $Q_{2}(z)$, $Q_{3}(z)$ in Theorem 2.2 can
be explicitly written down in the case $f(z)$ is an extremal quasimodular form
on $\Gamma=\mathrm{SL}(2,\mathbb{Z})$.

######  Definition 6.1 ([18]).

A quasimodular form $f\in\widetilde{\mathfrak{M}}_{k}^{\leq
r}(\mathrm{SL}(2,\mathbb{Z}))$ is said to be extremal if its vanishing order
at $\infty$ is equal to $\dim\widetilde{\mathfrak{M}}_{k}^{\leq
r}(\mathrm{SL}(2,\mathbb{Z}))-1$. We say $f$ is normalized if its leading
Fourier coefficient is $1$.

Pellarin [28] proved that if $r\leq 4$, then a normalized extremal
quasimodular form in $\widetilde{\mathfrak{M}}_{k}^{\leq
r}(\mathrm{SL}(2,\mathbb{Z}))$ exists and is unique.

######  Theorem 6.2.

Let $f(z)$ be an extremal quasimodular form of weight $k$ and depth $2$ on
$\mathrm{SL}(2,\mathbb{Z})$ and

$D_{q}^{3}y(z)+Q(z)D_{q}y(z)+\left(\frac{1}{2}D_{q}Q(z)+R(z)\right)y(z)=0$
(6.1)

be the differential equation satisfied by $f(z)/\sqrt[3]{W_{f}(z)}$ as derived
in Section 2.

  1. $(i)$

If $k\equiv 0\ \mathrm{mod}\ 4$, then

$Q(z)=-\frac{k^{2}}{48}E_{4}(z),\qquad R(z)=-\frac{k^{3}}{864}E_{6}(z).$

  2. $(ii)$

If $k\equiv 2\ \mathrm{mod}\ 4$, then

$Q(z)=-\frac{(k-2)^{2}}{48}E_{4}(z)-\frac{1}{3}\frac{E_{4}(z)\big{(}E_{4}(z)^{3}-E_{6}(z)^{2}\big{)}}{E_{6}(z)^{2}},$

and

$\displaystyle
R(z)=-\frac{(k-2)^{3}}{864}E_{6}(z)+\frac{5}{54}\frac{\big{(}E_{4}(z)^{3}-E_{6}(z)^{2}\big{)}^{2}}{E_{6}(z)^{3}}$
$\displaystyle\hphantom{R(z)=}{}+\frac{12-(k-2)^{2}}{144}\frac{E_{4}(z)^{3}-E_{6}(z)^{2}}{E_{6}(z)}.$

######  Remark 6.3.

We note that the differential equation in the case $k\equiv 0\ \mathrm{mod}\
4$ is equivalent to the following equation studied by Kaneko and Koike [18,
Theorem 3.1]:

$D_{q}^{3}f-\frac{k}{4}E_{2}D_{q}^{2}f+\frac{k(k-1)}{4}D_{q}E_{2}D_{q}f-\frac{k(k-1)(k-2)}{24}D_{q}^{2}E_{2}f=0.$

Indeed, by letting $f(z)=\Delta(z)^{\frac{k}{12}}y(z)$, a direct computation
shows that $y(z)$ solves

$D_{q}^{3}y-\frac{k^{2}}{48}E_{4}(z)D_{q}y-\frac{2k^{2}}{12^{3}}\left(3E_{2}(z)E_{4}(z)+(k-3)E_{6}(z)\right)y=0.$

To prove Theorem 6.2, we need the following general lemma, in which the
quasimodular form $f(z)$ is not assumed to be extremal.

######  Lemma 6.4.

Assume that

$\displaystyle
f(z)=f_{0}(z)+f_{1}(z)E_{2}(z)+f_{2}(z)E_{2}(z)^{2}\in\widetilde{\mathfrak{M}}^{\leq
2}_{k}(\mathrm{SL}(2,\mathbb{Z})),$ $\displaystyle
f_{j}(z)\in\mathfrak{M}_{k-2j}(\mathrm{SL}(2,\mathbb{Z})).$

Let

$\displaystyle g(z)=f_{1}(z)+2f_{2}(z)E_{2}(z),\qquad h(z)=f_{2}(z),\qquad
m=\min(\operatorname{ord}_{\infty}f,\operatorname{ord}_{\infty}g,\operatorname{ord}_{\infty}h).$

Let $\kappa_{\infty}^{(1)}\leq\kappa_{\infty}^{(2)}\leq\kappa_{\infty}^{(3)}$
be the local exponents of (2.4) at $\infty$.

  1. $(i)$

If $\operatorname{ord}_{\infty}f=m$, then
$\operatorname{ord}_{\infty}W_{f}=3m$ and $\kappa_{\infty}^{(j)}=0$ for all
$j$.

  2. $(ii)$

If $\operatorname{ord}_{\infty}g=m$ and $\operatorname{ord}_{\infty}f\neq m$,
then
$\operatorname{ord}_{\infty}W_{f}=\operatorname{ord}_{\infty}f+2\operatorname{ord}_{\infty}g$
and
$\kappa_{\infty}^{(1)}=\kappa_{\infty}^{(2)}=(\operatorname{ord}_{\infty}g-\operatorname{ord}_{\infty}f)/3$
and
$\kappa_{\infty}^{(3)}=2(\operatorname{ord}_{\infty}f-\operatorname{ord}_{\infty}g)/3$.

  3. $(iii)$

If
$\operatorname{ord}_{\infty}h<\operatorname{ord}_{\infty}f\leq\operatorname{ord}_{\infty}g$,
then
$\operatorname{ord}_{\infty}W_{f}=2\operatorname{ord}_{\infty}f+\operatorname{ord}_{\infty}h$
and
$\kappa_{\infty}^{(1)}=2(\operatorname{ord}_{\infty}h-\operatorname{ord}_{\infty}f)/3$
and
$\kappa_{\infty}^{(2)}=\kappa_{\infty}^{(3)}=(\operatorname{ord}_{\infty}f-\operatorname{ord}_{\infty}h)/3$.

  4. (iv)

If
$\operatorname{ord}_{\infty}h<\operatorname{ord}_{\infty}g<\operatorname{ord}_{\infty}f$,
then
$\operatorname{ord}_{\infty}W_{f}=\operatorname{ord}_{\infty}f+\operatorname{ord}_{\infty}g+\operatorname{ord}_{\infty}h$
and
$\kappa_{\infty}^{(1)}=\operatorname{ord}_{\infty}h-\frac{1}{3}\operatorname{ord}_{\infty}W_{f}$,
$\kappa_{\infty}^{(2)}=\operatorname{ord}_{\infty}g-\frac{1}{3}\operatorname{ord}_{\infty}W_{f}$,
and
$\kappa_{\infty}^{(3)}=\operatorname{ord}_{\infty}f-\frac{1}{3}\operatorname{ord}_{\infty}W_{f}$.

###### Proof.

Let $r=\frac{1}{3}\operatorname{ord}_{\infty}W_{f}$. Since up to scalars,
$g_{3}(z)=f(z)/\sqrt[3]{W_{f}(z)}$ is the unique solution of (2.4) without
logarithmic singularity near $\infty$, according to Frobenius’ method for
complex ordinary differential equations (see, e.g., Appendix A), we must have
$\kappa_{\infty}^{(3)}=\operatorname{ord}_{\infty}f-r$. Likewise, because
$g_{2}(z)=(2zf(z)+\alpha g(z))/\sqrt[3]{W_{f}(z)}$ and
$g_{1}(z)=\big{(}z^{2}f(z)+\alpha
zg(z)+\alpha^{2}h(z)\big{)}/\sqrt[3]{W_{f}(z)}$ are the other two linearly
independent solutions of (2.4), we have

$\kappa_{\infty}^{(2)}=\min(\operatorname{ord}_{\infty}f,\operatorname{ord}_{\infty}g)-r,\qquad\kappa_{\infty}^{(1)}=\min(\operatorname{ord}_{\infty}f,\operatorname{ord}_{\infty}g,\operatorname{ord}_{\infty}h)-r.$

Analyzing case by case, we obtain the claimed conclusions. ∎

###### Proof of Theorem 6.2.

First of all, recall that

$\dim\widetilde{\mathfrak{M}}_{k}^{\leq
2}(\mathrm{SL}(2,\mathbb{Z}))=1+\left\lfloor\frac{k}{4}\right\rfloor.$ (6.2)

Let $f(z)=f_{0}(z)+f_{1}(z)E_{2}(z)+f_{2}(z)E_{2}(z)^{2}$,
$f_{j}\in\mathfrak{M}_{k-2j}(\mathrm{SL}(2,\mathbb{Z}))$, be an extremal
quasimodular form in $\widetilde{\mathfrak{M}}_{k}^{\leq
2}(\mathrm{SL}(2,\mathbb{Z}))$. Note that $f_{j}(z)$ cannot have a common zero
on $\mathbb{H}$. To see this, say, assume that $f_{j}(z)$ has a common zero at
$z_{0}$. Let $F(z)$ be a modular form of weight $k^{\prime}$ with a simple
zero at $z_{0}$ and nonvanishing elsewhere. Then
$f(z)/F(z)\in\widetilde{\mathfrak{M}}_{k-k^{\prime}}^{\leq
2}(\mathrm{SL}(2,\mathbb{Z}))$ has order $\left\lfloor k/4\right\rfloor$ at
$\infty$, which is impossible by (6.2) and the facts that $k^{\prime}\geq 4$
and that extremal quasimodular forms of depth $2$ exist for any weight and are
unique up to scalars. Therefore, $f_{j}(z)$ have no common zeros on
$\mathbb{H}$.

Now according to Pellarin’s argument [28], one has
$\operatorname{ord}_{\infty}W_{f}=\operatorname{ord}_{\infty}f=\left\lfloor
k/4\right\rfloor$. Hence, we have

$W_{f}(z)=\begin{cases}c\Delta(z)^{k/4},&\text{if }k\equiv 0\ \mathrm{mod}\
4,\\\ c\Delta(z)^{(k-2)/4}E_{6}(z),&\text{if }k\equiv 2\ \mathrm{mod}\
4,\end{cases}$

for some nonzero complex number $c$. Also, by Lemma 6.4, we must have
$\operatorname{ord}_{\infty}(f_{1}+2f_{2}E_{2})=0$ and the local exponents at
$\infty$ must be $-r/3$, $-r/3$, and $2r/3$, where $r=\left\lfloor
k/4\right\rfloor$. In other words, the indicial equation of (2.4) at $\infty$
is

$x^{3}-\frac{r^{2}}{3}x-\frac{2r^{3}}{27}=0.$ (6.3)

Consider first the case $k\equiv 0\ \mathrm{mod}\ 4$. In this case, since
$\Delta(z)$ has no zeros on $\mathbb{H}$, (2.4) has no singularities on
$\mathbb{H}$. Hence, $Q(z)$ is a multiple of $E_{4}(z)$, while $R(z)$ is a
multiple of $E_{6}(z)$. In view of (6.3) and Lemma 5.8, we see that

$Q(z)=-\frac{k^{2}}{48}E_{4}(z),\qquad R(z)=-\frac{k^{3}}{864}E_{6}(z).$

We now consider the case $k\equiv 2\ \mathrm{mod}\ 4$. In this case,
$W_{f}(z)=c\Delta(z)^{(k-2)/4}E_{6}(z)$ has a simple zero at ${\rm i}$. Thus,
the local exponents of (2.4) at ${\rm i}$ are $-1/3$, $2/3$, and $8/3$ since
the differences must be positive integers and the sum must be equal to $3$,
and the indicial equation at ${\rm i}$ is

$x^{3}-3x^{2}+\frac{2}{3}x+\frac{16}{27}=0.$ (6.4)

We will use this information, together with the apparentness property, to
determine $Q(z)$ and $R(z)$.

First of all, according to Lemma 5.7, $Q(z)$ is of the form

$Q(z)=r_{\infty}E_{4}(z)+r_{\rm
i}^{(2)}\frac{E_{4}(z)\big{(}E_{4}(z)^{3}-E_{6}(z)^{2}\big{)}}{E_{6}(z)^{2}},$

while $R(z)$ is of the form

$R(z)=s_{\infty}E_{6}(z)+s_{\rm
i}^{(3)}\frac{\big{(}E_{4}(z)^{3}-E_{6}(z)^{2}\big{)}^{2}}{E_{6}(z)^{3}}+s_{\rm
i}^{(1)}\frac{E_{4}(z)^{3}-E_{6}(z)^{2}}{E_{6}(z)}$

for some complex numbers $r_{\infty}$, $r_{\rm i}^{(2)}$, $s_{\infty}$,
$s_{\rm i}^{(3)}$, and $s_{\rm i}^{(1)}$. The parameters $r_{\infty}$ and
$s_{\infty}$ are determined by the local exponents at $\infty$. As in the case
$k\equiv 0\ \mathrm{mod}\ 4$, we find that $r_{\infty}=-\frac{(k-2)^{2}}{48}$
and $s_{\infty}=-\frac{(k-2)^{3}}{864}$. We now determine the other
parameters.

By (6.4) and Lemma 5.9, we have $r_{\rm i}^{(2)}=-\frac{1}{3}$ and $s_{\rm
i}^{(3)}=\frac{5}{54}$. To determine the remaining parameter $s_{\rm
i}^{(1)}$, we let $w=(z-{\rm i})/(z+{\rm i})$ and recall that, by (5.7),

$E_{4}(z)=(1-w)^{4}\left(B+\frac{5}{72}B^{2}u^{2}+\frac{5}{6912}B^{3}u^{4}+\cdots\right)$

and

$E_{6}(z)=(1-w)^{6}\left(-\frac{1}{2}B^{2}u-\frac{7}{432}B^{3}u^{3}-\frac{7}{17280}B^{4}u^{5}+\cdots\right),$

where $u=-4\pi w$ and $B=E_{4}({\rm i})$. (Note that $E_{6}(z_{0})$ and the
constant $A$ in Lemma 5.5 are both $0$ when $z_{0}={\rm i}$.) Then the power
series $\widetilde{Q}(x)$ and $\widetilde{R}(x)$ such that
$Q(z)=(1-w)^{4}\widetilde{Q}(-4\pi w)$ and $R(z)=(1-w)^{6}\widetilde{R}(-4\pi
w)$ are

$\widetilde{Q}(x)=\frac{4r_{\rm
i}^{(2)}}{x^{2}}+\left(r_{\infty}-\frac{4r_{\rm
i}^{(2)}}{27}\right)B+\cdots=-\frac{4}{3x^{2}}+\left(-\frac{(k-2)^{2}}{48}+\frac{4}{81}\right)B+\cdots$

and

$\widetilde{R}(x)=-\frac{8s_{\rm i}^{(3)}}{x^{3}}+\left(-2s_{\rm
i}^{(1)}+\frac{13}{9}s_{\rm
i}^{(3)}\right)\frac{B}{x}+\cdots=-\frac{20}{27x^{3}}+\left(-2s_{\rm
i}^{(1)}+\frac{65}{486}\right)\frac{B}{x}+\cdots,$

respectively. By Lemma 5.5, the series (5.5) with $c_{0}=1$ is a solution of
(6.1) if and only if the power series
$\widetilde{y}(x)=\sum_{n=0}^{\infty}c_{n}x^{n+\alpha}$ satisfies (5.6).
Consider $\widetilde{y}(x)$ with $\alpha=2/3$. The coefficients $c_{n}$ need
to satisfy

$\displaystyle\sum_{n=0}^{\infty}c_{n}(n+2/3)(n-1/3)(n-4/3)x^{n-7/3}$
$\displaystyle\qquad{}+\left(-\frac{4}{3x^{2}}+\left(\frac{4}{81}-\frac{(k-2)^{2}}{48}\right)B+\cdots\right)\sum_{n=0}^{\infty}c_{n}(n+2/3)x^{n-1/3}$
$\displaystyle\qquad{}+\left(\frac{16}{27x^{3}}+\left(\frac{65}{486}-2s_{\rm
i}^{(1)}\right)\frac{B}{x}+\cdots\right)\sum_{n=0}^{\infty}c_{n}x^{n+2/3}=0.$

Considering the coefficients of $x^{-1/3}$, we find that $s_{\rm
i}^{(1)}=\frac{12-(k-2)^{2}}{144}.$ This completes the proof of the theorem. ∎

##  Appendix A The solution structure of third order ODE

In this appendix, we apply Frobenius’ method to study the solution structure
for

$\mathcal{L}y:=\frac{{\rm d}^{3}}{{\rm d}x^{3}}y(x)+\mathcal{Q}(x)\frac{{\rm
d}}{{\rm d}x}y(x)+\mathcal{R}(x)y(x)=0.$ (A.1)

See, e.g., [15, 16] for detailed expositions of Frobenius’ method. The
following arguments are known to experts in this field. However, since we can
not find a suitable reference, we would like to provide all necessary details
for later usage.

Suppose $0$ is a regular singular point of (A.1) with three local exponents

$\kappa_{1},\qquad\kappa_{2}=\kappa_{1}+m_{1},\qquad\kappa_{3}=\kappa_{2}+m_{2},\qquad\text{where}\quad
m_{1},m_{2}\in\mathbb{Z}_{\geq 0},$

Since the exponent differences are all integers, there might be logarithmic
singularities for solutions of (A.1), or more precisely, the local expansion
of some solutions at $x=0$ might contains $\ln x$ terms or even $(\ln x)^{2}$
terms. This leads us to give the following definition.

######  Definition A.1.

  * (1)

We say (A.1) is apparent at $x=0$ if all solutions have no logarithmic
singularities at $x=0$. Otherwise (A.1) is called not apparent at $x=0$.

  * (2)

If (A.1) is not apparent at $x=0$ and the local expansion of some solutions
contains $(\ln x)^{2}$ terms, we say (A.1) is completely not apparent at
$x=0$.

Since $0$ is a regular singular point of (A.1), both $x^{2}\mathcal{Q}(x)$ and
$x^{3}\mathcal{R}(x)$ are holomorphic at $x=0$, so we may write

$\mathcal{Q}(x)=\sum_{n=-2}^{\infty}a_{n}x^{n},\qquad\mathcal{R}(x)=\sum_{n=-3}^{\infty}b_{n}x^{n}.$

Let

$y(x;\alpha)=x^{\alpha}\sum_{n=0}^{\infty}c_{n}(\alpha)x^{n},\qquad\text{where}\quad
c_{0}(\alpha)=1.$

Then

$\displaystyle\mathcal{L}y(x;\alpha)$
$\displaystyle=\sum_{n=0}^{\infty}\bigg{(}f(\alpha+n)c_{n}(\alpha)+\sum_{k=0}^{n-1}[(\alpha+k)a_{n-k-2}+b_{n-k-3}]c_{k}(\alpha)\bigg{)}x^{n+\alpha-3}$
$\displaystyle=:x^{\alpha-3}\sum_{n=0}^{\infty}R_{n}(\alpha)x^{n},$ (A.2)

where

$f(s):=s(s-1)(s-2)+sa_{-2}+b_{-3}=\prod_{j=1}^{3}(s-\kappa_{j}),$

i.e., $f(s)=0$ is the indicial equation of (A.1) at $x=0$. Note
$R_{0}(\alpha)=f(\alpha)$.

For any $\alpha$ satisfying $|\alpha-\kappa_{3}|<1/2$, we have

$f(\alpha+n)\neq 0\qquad\text{for any}\ n\geq 1,$

so by letting

$R_{n}(\alpha)=f(\alpha+n)c_{n}(\alpha)+\sum_{k=0}^{n-1}[(\alpha+k)a_{n-k-2}+b_{n-k-3}]c_{k}(\alpha)=0,\qquad
n\geq 1,$

we see that $c_{n}(\alpha)$ can be uniquely solved for any $n\geq 1$ such that

$\mathcal{L}y(x;\alpha)=x^{\alpha-3}f(\alpha),\qquad\text{for any}\
|\alpha-\kappa_{3}|<1/2.$ (A.3)

Note that $c_{n}(\alpha)\in\mathbb{C}(\alpha)$ is a rational function of
$\alpha$ for any $n\geq 1$.

In particular, letting $\alpha=\kappa_{3}$ in (A.3) leads to
$\mathcal{L}y(x;\kappa_{3})=0$, so

######  Lemma A.2.

$y(x;\kappa_{3})=x^{\kappa_{3}}\sum_{n=0}^{\infty}c_{n}(\kappa_{3})x^{n}$

is always a solution of (A.1) with the local exponent $\kappa_{3}$.

By (A.3), we have

$\mathcal{L}\frac{\partial
y(x;\alpha)}{\partial\alpha}=x^{\alpha-3}f(\alpha)\ln
x+x^{\alpha-3}f^{\prime}(\alpha),$

so

$\mathcal{L}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{3}}=x^{\kappa_{3}-3}f^{\prime}(\kappa_{3}).$
(A.4)

Similarly,

$\mathcal{L}\frac{\partial^{2}y(x;\alpha)}{\partial\alpha^{2}}\Big{|}_{\alpha=\kappa_{3}}=2x^{\kappa_{3}-3}f^{\prime}(\kappa_{3})\ln
x+x^{\kappa_{3}-3}f^{\prime\prime}(\kappa_{3}).$ (A.5)

Note that

$\displaystyle\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{3}}=(\ln
x)y(x;k_{3})+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n},$
(A.6)
$\displaystyle\frac{\partial^{2}y(x;\alpha)}{\partial\alpha^{2}}\Big{|}_{\alpha=\kappa_{3}}=(\ln
x)^{2}y(x;k_{3})+2(\ln
x)x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime\prime}(\kappa_{3})x^{n}.$
(A.7)

######  Theorem A.3.

If $\kappa_{1}=\kappa_{2}=\kappa_{3}$, then $\frac{\partial
y(x;\alpha)}{\partial\alpha}|_{\alpha=\kappa_{3}}$ and
$\frac{\partial^{2}y(x;\alpha)}{\partial\alpha^{2}}|_{\alpha=\kappa_{3}}$
given in (A.6) and (A.7) are the other two linearly independent solutions of
(A.1), namely (A.1) is completely not apparent at $x=0$.

###### Proof.

Since $f(s)=(s-\kappa_{3})^{3}$, we have
$f^{\prime}(\kappa_{3})=f^{\prime\prime}(\kappa_{3})=0$, so this theorem
follows from (A.4) and (A.5). ∎

Next we consider the case $\kappa_{1}<\kappa_{2}=\kappa_{3}$, i.e., $m_{1}>0$,
$m_{2}=0$ and $f(s)=(s-\kappa_{1})(s-\kappa_{3})^{2}$. Then
$f^{\prime}(\kappa_{3})=0$ and $f^{\prime\prime}(\kappa_{3})\neq 0$, so
$\frac{\partial y(x;\alpha)}{\partial\alpha}|_{\alpha=\kappa_{3}}$ given in
(A.6) is the second solution of (A.1), and (A.5) becomes

$\mathcal{L}\frac{\partial^{2}y(x;\alpha)}{\partial\alpha^{2}}\Big{|}_{\alpha=\kappa_{3}}=x^{\kappa_{3}-3}f^{\prime\prime}(\kappa_{3})\neq
0.$ (A.8)

On the other hand, $f(\kappa_{1}+n)\neq 0$ for
$n\in\mathbb{N}\setminus\\{m_{1}\\}$. Thus by letting
$c_{m_{1}}(\kappa_{1})=0$ and $R_{n}(\kappa_{1})=0$ for any
$n\in\mathbb{N}\setminus\\{m_{1}\\}$ in $\mathcal{L}y(x;\kappa_{1})$ (see
(A.2) with $\alpha=\kappa_{1}$), we see that $c_{n}(\kappa_{1})$ can be
uniquely solved for any $n\in\mathbb{N}\setminus\\{m_{1}\\}$ such that

$\mathcal{L}y(x;\kappa_{1})=x^{\kappa_{1}-3}R_{m_{1}}(\kappa_{1})x^{m_{1}}=R_{m_{1}}(\kappa_{1})x^{\kappa_{3}-3},$
(A.9)

where

$R_{m_{1}}(\kappa_{1})=\sum_{k=0}^{m_{1}-1}[(\kappa_{1}+k)a_{m_{1}-k-2}+b_{m_{1}-k-3}]c_{k}(\kappa_{1})$

is a constant. Thus we obtain

######  Theorem A.4.

Suppose $\kappa_{1}<\kappa_{2}=\kappa_{3}$. Then $\frac{\partial
y(x;\alpha)}{\partial\alpha}|_{\alpha=\kappa_{3}}$ given in (A.6) is the
second solution of (A.1). Furthermore,

  * $(1)$

If $R_{m_{1}}(\kappa_{1})=0$, then

$y(x;\kappa_{1})=x^{\kappa_{1}}\sum_{n=0}^{\infty}c_{n}(\kappa_{1})x^{n}$

is the third solution of (A.1) that has the local exponent $\kappa_{1}$.

  * $(2)$

If $R_{m_{1}}(\kappa_{1})\neq 0$, then (A.8) and (A.9) imply that

$\displaystyle y_{3}(x):={}$
$\displaystyle\frac{\partial^{2}y(x;\alpha)}{\partial\alpha^{2}}\Big{|}_{\alpha=\kappa_{3}}-\frac{f^{\prime\prime}(\kappa_{3})}{R_{m_{1}}(\kappa_{1})}y(x;\kappa_{1})$
$\displaystyle={}$ $\displaystyle(\ln x)^{2}y(x;k_{3})+2(\ln
x)x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}$
$\displaystyle{}+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime\prime}(\kappa_{3})x^{n}-\frac{f^{\prime\prime}(\kappa_{3})}{R_{m_{1}}(\kappa_{1})}y(x;\kappa_{1})$

is the third solution of (A.1) that corresponds to the local exponent
$\kappa_{1}$, namely (A.1) is completely not apparent at $x=0$.

The remaining case is $\kappa_{1}\leq\kappa_{2}<\kappa_{3}$, i.e.,
$m_{2}=\kappa_{3}-\kappa_{2}>0$. Then for any $\alpha$ satisfying
$|\alpha-\kappa_{2}|<1/2$, we have

$f(\alpha+n)\neq 0\qquad\text{for any}\ n\in\mathbb{N}\setminus\\{m_{2}\\},$

and

$f(\alpha+n)=0\qquad\text{for $n\geq 1$ if and only if $\alpha=\kappa_{2}$ and
$n=m_{2}$},$

so by letting $c_{m_{2}}(\alpha)=0$ and $R_{n}(\alpha)=0$ for any
$n\in\mathbb{N}\setminus\\{m_{2}\\}$ in $\mathcal{L}y(x;\alpha)$ (see (A.2)),
we see that $c_{n}(\alpha)$ can be uniquely solved for any
$n\in\mathbb{N}\setminus\\{m_{2}\\}$ such that

$\mathcal{L}y(x;\alpha)=x^{\alpha-3}f(\alpha)+x^{\alpha+m_{2}-3}R_{m_{2}}(\alpha),\qquad\text{for}\
|\alpha-\kappa_{2}|<1/2,$ (A.10)

where

$R_{m_{2}}(\alpha)=\sum_{k=0}^{m_{2}-1}[(\alpha+k)a_{m_{2}-k-2}+b_{m_{2}-k-3}]c_{k}(\alpha)\in\mathbb{C}(\alpha),$

because $c_{k}(\alpha)\in\mathbb{C}(\alpha)$ for any
$n\in\mathbb{N}\setminus\\{m_{2}\\}$.

Similarly as before, it follows from (A.10) that

$\displaystyle\mathcal{L}y(x;\kappa_{2})=x^{\kappa_{3}-3}R_{m_{2}}(\kappa_{2}),$
(A.11) $\displaystyle\mathcal{L}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}=x^{\kappa_{2}-3}f^{\prime}(\kappa_{2})+x^{\kappa_{3}-3}R_{m_{2}}^{\prime}(\kappa_{2})+(\ln
x)x^{\kappa_{3}-3}R_{m_{2}}(\kappa_{2}),$ (A.12)

where

$\frac{\partial y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}=(\ln
x)y(x;\kappa_{2})+x^{\kappa_{2}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{2})x^{n}.$

######  Theorem A.5.

Suppose $\kappa_{1}=\kappa_{2}<\kappa_{3}$.

  * $(1)$

If $R_{m_{2}}(\kappa_{2})=0$, then (A.11) implies that $y(x;\kappa_{2})$ is
the second solution of (A.1), and

$\displaystyle y_{3}(x):={}$ $\displaystyle\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}-\frac{R_{m_{2}}^{\prime}(\kappa_{2})}{f^{\prime}(\kappa_{3})}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{3}}$ $\displaystyle={}$
$\displaystyle(\ln
x)y(x;\kappa_{2})+x^{\kappa_{2}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{2})x^{n}$
$\displaystyle{}-\frac{R_{m_{2}}^{\prime}(\kappa_{2})}{f^{\prime}(\kappa_{3})}\bigg{(}(\ln
x)y(x;\kappa_{3})+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}\bigg{)}$

is the third solution of (A.1).

  * $(2)$

If $R_{m_{2}}(\kappa_{2})\neq 0$, then (A.4) and (A.11) imply that

$\displaystyle\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{3}}-\frac{f^{\prime}(\kappa_{3})}{R_{m_{2}}(\kappa_{2})}y(x;\kappa_{2})$
$\displaystyle\qquad{}=(\ln
x)y(x;\kappa_{3})+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}-\frac{f^{\prime}(\kappa_{3})}{R_{m_{2}}(\kappa_{2})}y(x;\kappa_{2})$

is the second solution of (A.1), and

$\displaystyle y_{3}(x):={}$
$\displaystyle\frac{\partial^{2}y(x;\alpha)}{\partial\alpha^{2}}\Big{|}_{\alpha=\kappa_{3}}-\frac{2f^{\prime}(\kappa_{3})}{R_{m_{2}}(k_{2})}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}$
$\displaystyle{}-\frac{f^{\prime\prime}(\kappa_{3})R_{m_{2}}(\kappa_{2})-2f^{\prime}(\kappa_{3})R_{m_{2}}^{\prime}(\kappa_{2})}{R_{m_{2}}(\kappa_{2})^{2}}y(x;\kappa_{2})$
$\displaystyle={}$ $\displaystyle(\ln x)^{2}y(x;k_{3})+2(\ln
x)x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime\prime}(\kappa_{3})x^{n}$
$\displaystyle{}-\frac{2f^{\prime}(\kappa_{3})}{R_{m_{2}}(k_{2})}\bigg{(}(\ln
x)y(x;\kappa_{2})+x^{\kappa_{2}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{2})x^{n}\bigg{)}$
$\displaystyle{}-\frac{f^{\prime\prime}(\kappa_{3})R_{m_{2}}(\kappa_{2})-2f^{\prime}(\kappa_{3})R_{m_{2}}^{\prime}(\kappa_{2})}{R_{m_{2}}(\kappa_{2})^{2}}y(x;\kappa_{2}).$

is the third solution of (A.1), namely (A.1) is completely not apparent at
$x=0$.

###### Proof.

Since $\kappa_{1}=\kappa_{2}<\kappa_{3}$, i.e., $m_{1}=0$, $m_{2}>0$ and
$f(s)=(s-\kappa_{2})^{2}(s-\kappa_{3})$, so $f^{\prime}(\kappa_{2})=0$ and
$f^{\prime}(\kappa_{3})\neq 0$.

(1) Note that (A.12) becomes

$\mathcal{L}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}=x^{\kappa_{3}-3}R_{m_{2}}^{\prime}(\kappa_{2}),$

we see from (A.4) that $\mathcal{L}y_{3}=0$.

(2) Note that (A.12) becomes

$\mathcal{L}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}=x^{\kappa_{3}-3}R_{m_{2}}^{\prime}(\kappa_{2})+(\ln
x)x^{\kappa_{3}-3}R_{m_{2}}(\kappa_{2}).$ (A.13)

Then (A.5), (A.11) and (A.13) together imply $\mathcal{L}y_{3}=0$. ∎

Finally, we consider the last case $\kappa_{1}<\kappa_{2}<\kappa_{3}$, i.e.,
$m_{1}>0$ and $m_{2}>0$. Then $f^{\prime}(\kappa_{j})\neq 0$ for all $j$.
Since $f(\kappa_{1}+n)=0$ for $n\geq 1$ if and only if
$n\in\\{m_{1},m_{1}+m_{2}\\}$, by letting
$c_{m_{1}}(\kappa_{1})=c_{m_{1}+m_{2}}=0$ and $R_{n}(\kappa_{1})=0$ for any
$n\in\mathbb{N}\setminus\\{m_{1},m_{1}+m_{2}\\}$ in
$\mathcal{L}y(x;\kappa_{1})$ (see (A.2) with $\alpha=\kappa_{1}$), we see that
$c_{n}(\kappa_{1})$ can be uniquely solved for any
$n\in\mathbb{N}\setminus\\{m_{1},m_{1}+m_{2}\\}$ such that

$\mathcal{L}y(x;\kappa_{1})=R_{m_{1}}(\kappa_{1})x^{\kappa_{2}-3}+R_{m_{1}+m_{2}}(\kappa_{1})x^{\kappa_{3}-3},$
(A.14)

where

$\displaystyle
R_{m_{1}}(\kappa_{1})=\sum_{k=0}^{m_{1}-1}[(\kappa_{1}+k)a_{m_{1}-k-2}+b_{m_{1}-k-3}]c_{k}(\kappa_{1}),$
$\displaystyle
R_{m_{1}+m_{2}}(\kappa_{1})=\sum_{k=0}^{m_{1}+m_{2}-1}[(\kappa_{1}+k)a_{m_{1}+m_{2}-k-2}+b_{m_{1}+m_{2}-k-3}]c_{k}(\kappa_{1}),$

are constants.

######  Theorem A.6.

Suppose $\kappa_{1}<\kappa_{2}<\kappa_{3}$ and $R_{m_{2}}(\kappa_{2})=0$. Then
(A.11) implies that $y(x;\kappa_{2})$ is the second solution of (A.1).
Furthermore,

  * $(1)$

If $R_{m_{1}}(\kappa_{1})=R_{m_{1}+m_{2}}(\kappa_{1})=0$, then (A.14) implies
that $y(x;\kappa_{3})$ is the third solution of (A.1), namely $0$ is an
apparent singularity of (A.1).

  * $(2)$

If $R_{m_{1}}(\kappa_{1})=0$ and $R_{m_{1}+m_{2}}(\kappa_{1})\neq 0$, then

$\displaystyle y_{3}(x):={}$ $\displaystyle\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{3}}-\frac{f^{\prime}(\kappa_{3})}{R_{m_{1}+m_{2}}(\kappa_{1})}y(x;\kappa_{1})$
$\displaystyle={}$ $\displaystyle(\ln
x)y(x;\kappa_{3})+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}-\frac{f^{\prime}(\kappa_{3})}{R_{m_{1}+m_{2}}(\kappa_{1})}y(x;\kappa_{1})$

is the third solution of (A.1).

  * $(3)$

If $R_{m_{1}}(\kappa_{1})\neq 0$, then

$\displaystyle y_{3}(x):={}$ $\displaystyle\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}-\frac{f^{\prime}(\kappa_{2})}{R_{m_{1}}(k_{1})}y(x;\kappa_{1})$
$\displaystyle{}-\frac{R_{m_{1}}(\kappa_{1})R_{m_{2}}^{\prime}(\kappa_{2})-f^{\prime}(\kappa_{2})R_{m_{1}+m_{2}}(\kappa_{1})}{f^{\prime}(\kappa_{3})R_{m_{1}}(\kappa_{1})}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{3}}$ $\displaystyle={}$
$\displaystyle(\ln
x)y(x;\kappa_{2})+x^{\kappa_{2}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{2})x^{n}-\frac{f^{\prime}(\kappa_{2})}{R_{m_{1}}(k_{1})}y(x;\kappa_{1})-$
$\displaystyle\frac{R_{m_{1}}(\kappa_{1})R_{m_{2}}^{\prime}(\kappa_{2})-f^{\prime}(\kappa_{2})R_{m_{1}+m_{2}}(\kappa_{1})}{f^{\prime}(\kappa_{3})R_{m_{1}}(\kappa_{1})}\bigg{(}(\ln
x)y(x;\kappa_{3})+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}\bigg{)}$

is the third solution of (A.1).

###### Proof.

Note that (A.12) becomes

$\mathcal{L}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}=x^{\kappa_{2}-3}f^{\prime}(\kappa_{2})+x^{\kappa_{3}-3}R_{m_{2}}^{\prime}(\kappa_{2}).$
(A.15)

(2) Note that (A.14) becomes

$\mathcal{L}y(x;\kappa_{1})=R_{m_{1}+m_{2}}(\kappa_{1})x^{\kappa_{3}-3}\neq
0.$ (A.16)

From here and (A.4), we easily obtain $\mathcal{L}y_{3}=0$.

(3) Similarly, it is easy see from (A.4), (A.14) and (A.15) that
$\mathcal{L}y_{3}=0$. ∎

Similarly, we can obtain

######  Theorem A.7.

Suppose $\kappa_{1}<\kappa_{2}<\kappa_{3}$ and $R_{m_{2}}(\kappa_{2})\neq 0$.
Then (A.4) and (A.11) imply that

$\displaystyle\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{3}}-\frac{f^{\prime}(\kappa_{3})}{R_{m_{2}}(\kappa_{2})}y(x;\kappa_{2})=(\ln
x)y(x;\kappa_{3})+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}-\frac{f^{\prime}(\kappa_{3})}{R_{m_{2}}(\kappa_{2})}y(x;\kappa_{2})$

is the second solution of (A.1). Furthermore,

  * $(1)$

If $R_{m_{1}}(\kappa_{1})=R_{m_{1}+m_{2}}(\kappa_{1})=0$, then (A.14) implies
that $y(x;\kappa_{3})$ is the third solution of (A.1).

  * $(2)$

If $R_{m_{1}}(\kappa_{1})=0$ and $R_{m_{1}+m_{2}}(\kappa_{1})\neq 0$, then
(A.11) and (A.16) imply that

$y(x;\kappa_{1})-\frac{R_{m_{1}+m_{2}}(\kappa_{1})}{R_{m_{2}}(\kappa_{2})}y(x;\kappa_{2})$

is the third solution of (A.1).

  * $(3)$

If $R_{m_{1}}(\kappa_{1})\neq 0$, then (A.5), (A.11), (A.12) and (A.14) imply
that

$\displaystyle y_{3}(x):={}$
$\displaystyle\frac{\partial^{2}y(x;\alpha)}{\partial\alpha^{2}}\Big{|}_{\alpha=\kappa_{3}}-\frac{2f^{\prime}(\kappa_{3})}{R_{m_{2}}(\kappa_{2})}\frac{\partial
y(x;\alpha)}{\partial\alpha}\Big{|}_{\alpha=\kappa_{2}}+C_{1}y(x;\kappa_{1})-C_{2}y(x;\kappa_{2})$
$\displaystyle={}$ $\displaystyle(\ln x)^{2}y(x;\kappa_{3})+2(\ln
x)x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{3})x^{n}+x^{\kappa_{3}}\sum_{n=1}^{\infty}c_{n}^{\prime\prime}(\kappa_{3})x^{n}$
$\displaystyle{}-\frac{2f^{\prime}(\kappa_{3})}{R_{m_{2}}(k_{2})}\bigg{(}(\ln
x)y(x;\kappa_{2})+x^{\kappa_{2}}\sum_{n=1}^{\infty}c_{n}^{\prime}(\kappa_{2})x^{n}\bigg{)}+C_{1}y(x;\kappa_{1})-C_{2}y(x;\kappa_{2})$

is the third solution of (A.1), where

$\displaystyle
C_{1}:=\frac{2f^{\prime}(\kappa_{3})f^{\prime}(\kappa_{2})}{R_{m_{2}}(\kappa_{2})R_{m_{1}}(\kappa_{1})},$
$\displaystyle
C_{2}:=\frac{1}{R_{m_{2}}(\kappa_{2})}\left[f^{\prime\prime}(\kappa_{3})-\frac{2f^{\prime}(\kappa_{3})R_{m_{2}}^{\prime}(\kappa_{2})}{R_{m_{2}}(\kappa_{2})}+\frac{2f^{\prime}(\kappa_{3})f^{\prime}(\kappa_{2})R_{m_{1}+m_{2}}(\kappa_{1})}{R_{m_{2}}(\kappa_{2})R_{m_{1}}(\kappa_{1})}\right].$

In particular, (A.1) is completely not apparent at $x=0$.

######  Remark A.8.

It follows from Theorem A.6(1) that $0$ can be apparent only for the case
$\kappa_{1}<\kappa_{2}<\kappa_{3}$.

######  Remark A.9.

Clearly all the above arguments work when we study whether the regular
singularity $\infty$ is apparent or not for

$y^{\prime\prime\prime}(z)+Q_{2}(z)y^{\prime}(z)+Q_{3}(z)y(z)=0,\qquad
z\in\mathbb{H},$ (A.17)

when the local exponents
$\kappa_{\infty}^{(1)}\leq\kappa_{\infty}^{(2)}\leq\kappa_{\infty}^{(3)}$
satisfy $\kappa_{\infty}^{(j)}-\kappa_{\infty}^{(j-1)}\in\mathbb{Z}$. Since
$Q_{j}(z)$’s have Fourier expansions in terms of $q_{N}={\rm
e}^{\frac{2\pi{\rm i}z}{N}}$ (where $N$ is the width of the cusp $\infty$ on
$\Gamma$ and $N=1$ for $\Gamma=\mathrm{SL}(2,\mathbb{Z})$), this is equivalent
to whether the regular singularity $q_{N}=0$ is apparent or not for

$\left(q_{N}\frac{{\rm d}}{{\rm d}q_{N}}\right)^{3}y+\frac{N^{2}}{(2\pi{\rm
i})^{2}}Q_{2}q_{N}\frac{{\rm d}}{{\rm d}q_{N}}y+\frac{N^{3}}{(2\pi{\rm
i})^{3}}Q_{3}y=0.$ (A.18)

All the above statements are true for (A.18) in terms of $q_{N}$. In
particular, (A.17) or equivalently (A.18) always has a solution of the form

$y_{+}(z):=q_{N}^{\kappa_{\infty}^{(3)}}\sum_{n=0}^{\infty}c_{n}(\kappa_{\infty}^{(3)})q_{N}^{n},\quad
c_{0}=1,$ (A.19)

and (A.17) is completely not apparent at $z=\infty$ or equivalently (A.18) is
completely not apparent at $q_{N}=0$ if and only if the local expansion of
some solutions in terms of $q_{N}$ contains the term $z^{2}y_{+}(z)$ because
of $\ln q_{N}=2\pi{\rm i}z/N$. More precisely, if (A.17) is completely not
apparent at $z=\infty$, then it follows from Theorems A.3, A.4(2), A.5(2) and
Theorem A.7(3) that (A.17) has two solutions of the following form

$\displaystyle y_{-}(z):=z^{2}y_{+}(z)+z\eta_{1}(z)+\eta_{2}(z),\qquad
y_{\perp}(z):=zy_{+}(z)+\eta_{3}(z),$ (A.20)

such that $(y_{-},y_{\perp},y_{+})^{t}$ is a basis of solutions, where

$\eta_{1}(z)=q_{N}^{\kappa_{\infty}^{(2)}}\sum_{n=0}^{\infty}c_{n,1}q_{N}^{n},\qquad\eta_{2}(z)=q_{N}^{\kappa_{\infty}^{(1)}}\sum_{n=0}^{\infty}c_{n,2}q_{N}^{n},\qquad\eta_{3}(z)=q_{N}^{\kappa_{\infty}^{(2)}}\sum_{n=0}^{\infty}c_{n,3}q_{N}^{n}.$

Note that $c_{0,j}=0$ may happen for any $j$; see Theorem A.3 for example.

### Acknowledgements

We would like to thank the referees for many valuable comments and pointing
out some references. The research of Z. Chen was supported by NSFC (No.
12071240).

## References

  * [1] Arike Y., Kaneko M., Nagatomo K., Sakai Y., Affine vertex operator algebras and modular linear differential equations, Lett. Math. Phys. 106 (2016), 693–718.
  * [2] Beukers F., Heckman G., Monodromy for the hypergeometric function ${}_{n}F_{n-1}$, Invent. Math. 95 (1989), 325–354.
  * [3] Bol G., Invarianten linearer differentialgleichungen, Abh. Math. Sem. Univ. Hamburg 16 (1949), 1–28.
  * [4] Chen Z., Kuo T.-J., Lin C.-S., The geometry of generalized Lamé equation, I, J. Math. Pures Appl. 127 (2019), 89–120, arXiv:1708.05306.
  * [5] Chen Z., Kuo T.-J., Lin C.-S., The geometry of generalized Lamé equation, II: Existence of pre-modular forms and application, J. Math. Pures Appl. 132 (2019), 251–272, arXiv:1807.07745.
  * [6] Chen Z., Kuo T.-J., Lin C.-S., The geometry of generalized Lamé equation, III: One to one of the Riemann–Hilbert correspondnece, Pure Appl. Math. Q. 17 (2021), 1619–1668, arXiv:2009.00840.
  * [7] Chen Z., Lin C.-S., On number and evenness of solutions of the ${\rm SU}(3)$ Toda system on flat tori with non-critical parameters, J. Differ. Geom., to appear, arXiv:2109.11721.
  * [8] Choie Y., Lee M.H., Jacobi-like forms, pseudodifferential operators, and quasimodular forms, Springer Monographs in Mathematics, Springer, Cham, 2019.
  * [9] Franc C., Mason G., Hypergeometric series, modular linear differential equations and vector-valued modular forms, Ramanujan J. 41 (2016), 233–267, arXiv:1503.05519.
  * [10] Franc C., Mason G., Classification of some vertex operator algebras of rank 3, Algebra Number Theory 14 (2020), 1613–1668, arXiv:1905.07500.
  * [11] Franc C., Mason G., Constructions of vector-valued modular forms of rank four and level one, Int. J. Number Theory 16 (2020), 1111–1152, arXiv:1810.09408.
  * [12] Gaberdiel M.R., Keller C.A., Modular differential equations and null vectors, J. High Energy Phys. 2008 (2008), no. 9, 079, 29 pages, arXiv:0804.0489.
  * [13] Grabner P.J., Quasimodular forms as solutions of modular differential equations, Int. J. Number Theory 16 (2020), 2233–2274, arXiv:2002.02736.
  * [14] Hampapura H.R., Mukhi S., Two-dimensional RCFT’s without Kac–Moody symmetry, J. High Energy Phys. 2016 (2016), no. 7, 138, 19 pages, arXiv:1605.03314.
  * [15] Henrici P., Applied and computational complex analysis. Vol. 2. Special functions – integral transforms – asymptotics – continued fractions, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1991.
  * [16] Hille E., Ordinary differential equations in the complex domain, Dover Publications, Inc., Mineola, NY, 1997.
  * [17] Kaneko M., Koike M., On modular forms arising from a differential equation of hypergeometric type, Ramanujan J. 7 (2003), 145–164, arXiv:math.NT/0206022.
  * [18] Kaneko M., Koike M., On extremal quasimodular forms, Kyushu J. Math. 60 (2006), 457–470.
  * [19] Kaneko M., Nagatomo K., Sakai Y., The third order modular linear differential equations, J. Algebra 485 (2017), 332–352.
  * [20] Kaneko M., Zagier D., A generalized Jacobi theta function and quasimodular forms, in The Moduli Space of Curves (Texel Island, 1994), Progr. Math., Vol. 129, Birkhäuser Boston, Boston, MA, 1995, 165–172.
  * [21] Kawasetsu K., Sakai Y., Modular linear differential equations of fourth order and minimal $\mathcal{W}$-algebras, J. Algebra 506 (2018), 445–488, arXiv:1803.02022.
  * [22] Le Bruyn L., Bulk irreducibles of the modular group, J. Algebra Appl. 15 (2016), 1650006, 14 pages.
  * [23] Lin C.-S., Nie Z., Wei J., Toda systems and hypergeometric equations, Trans. Amer. Math. Soc. 370 (2018), 7605–7626, arXiv:1610.03194.
  * [24] Lin C.-S., Wei J., Ye D., Classification and nondegeneracy of ${\rm SU}(n+1)$ Toda system with singular sources, Invent. Math. 190 (2012), 169–207, arXiv:1111.0390.
  * [25] Lin C.-S., Yang Y., Quasimodular forms and modular differential equations which are not apparent at cusps: I, arXiv:2103.04890.
  * [26] Mason G., Vector-valued modular forms and linear differential operators, Int. J. Number Theory 3 (2007), 377–390.
  * [27] Mathur S.D., Mukhi S., Sen A., On the classification of rational conformal field theories, Phys. Lett. B 213 (1988), 303–308.
  * [28] Pellarin F., On extremal quasi-modular forms after Kaneko and Koike (with an appendix by Gabriele Nebe), Kyushu J. Math. 74 (2020), 401–413, arXiv:1910.11668.
  * [29] Sebbar A., Saber H., Automorphic Schwarzian equations, Forum Math. 32 (2020), 1621–1636, arXiv:2002.00493.
  * [30] Serre J.-P., A course in arithmetic, Graduate Texts in Mathematics, Vol. 7, Springer-Verlag, New York – Heidelberg, 1973.
  * [31] Tuba I., Wenzl H., Representations of the braid group $B_{3}$ and of ${\rm SL}(2,{\bf Z})$, Pacific J. Math. 197 (2001), 491–510, arXiv:math.RT/9912013.
  * [32] Westbury B., On the character varieties of the modular group, Preprint, Nottingham University, 1995.
  * [33] Zagier D., Elliptic modular forms and their applications, in The 1-2-3 of Modular Forms, Universitext, Springer, Berlin, 2008, 1–103.
  * [34] Zhu Y., Modular invariance of characters of vertex operator algebras, J. Amer. Math. Soc. 9 (1996), 237–302, arXiv:math.RT/9912013.