20(-1.9, 8.2)

20(-2.15, 8.6)

We design a randomized data structure that, for a fully dynamic graph $G$ updated by edge insertions and deletions and integers $k, d$ fixed upon initialization, maintains the answer to the Split Completion problem: whether one can add $k$ edges to $G$ to obtain a split graph. The data structure can be initialized on an edgeless $n$-vertex graph in time $n \cdot (k d \cdot \log n)^{\Oh(1)}$, and the amortized time complexity of an update is $5^k \cdot (k d \cdot \log n)^{\Oh(1)}$. The answer provided by the data structure is correct with probability $1-\Oh(n^{-d})$.

§ INTRODUCTION

In the field of parameterized algorithms, one measures resources used by an algorithm not only in terms of the total size of the considered instance, but also in terms of auxiliary quantitative measures associated with the instance, called parameters. Recently there is a growing interest in applying this principle to the area of dynamic data structures. In this context, we typically consider an instance $I$ of a fixed problem of interest, with an associated parameter $k$. The instance is dynamic, in the sense that it is updated over time by problem-specific update operations, while for simplicity we assume that the parameter stays intact. The goal is to design a data structure that would maintain whether $I$ is a yes-instance of the problem under the updates to $I$. Here we allow the update time to depend in any computable way on the parameter and sublinearly on the instance size; for instance, we are insterested in (possibly amortized) update times of the form $f(k)$, $f(k)\cdot (\log n)^{\Oh(1)}$, or $f(k)\cdot n^{o(1)}$, where $f$ is some computable function and $n$ is the size of $I$. Note that we allow $f$ to be superpolynomial, so this framework may be applied even to $\mathsf{NP}$-hard problems, as long as their static parameterized variants are fixed-parameter tractable.

Parameterized dynamic data structures were first systematically investigated by Iwata and Oka [23], followed by
Alman et al. [1]. These works provided data structures with update times $f(k)$ or $f(k)\cdot (\log n)^{\Oh(1)}$ for several classic problems such as Vertex Cover, Cluster Vertex Deletion, Hitting Set, Feedback Vertex Set, or Longest Path. Other recent advances include data structures for maintaining various graph decompositions together with runs of dynamic programming procedures [8, 13, 14, 26, 28], treatment of parameterized string problems from the dynamic perspective [32], and even an application of the framework in the context of timed automata [19].

A topic within parameterized algorithms that could be particularly productive from the point of view of dynamic data structures is that of graph modification problems. In this context, we fix a graph class $\Cc$ and a set of graph operations $\Pi$ (e.g. vertex deletion, edge deletion, edge insertion), and consider the following parameterized problem: given a graph $G$ and a parameter $k$, decide whether one can apply at most $k$ operations from $\Pi$ to $G$ in order to obtain a graph belonging to $\Cc$. By instantiating different graph classes $\Cc$ and sets of operations $\Pi$, we obtain a wealth of parameterized problems with vastly different complexities, highly dependent on the combinatorics of the class $\Cc$ in question. The most widely studied are vertex deletion problems (only vertex deletions are allowed), edge deletion and completion problems (only edge deletions, respectively insertions, are allowed), and editing problems (both edge deletions and edge insertions are allowed).

Note that Vertex Cover, Feedback Vertex Set, and Cluster Vertex Deletion can be understood as vertex deletion problems, for the classes of edgeless, acyclic, and cluster graphs, respectively. Thus, the results of Iwata and Oka [23] and of Alman et al. [1] already give parameterized dynamic data structures for some basic graph modification problems, but the impressive volume of work on static parameterized algorithms for such problems suggests that there is much more to be explored.

In this work we focus on the case of split graphs; recall that a graph $G$ is a split graph if the vertices of $G$ can be partitioned into sets $C$ and $I$ so that $C$ is a clique and $I$ is an independent set. As proved by Földes and Hammer [17], split graphs are exactly graphs that exclude $2K_2$, $C_4$, and $C_5$ as induced subgraphs. Hence, a standard branching strategy solves Split Vertex Deletion in time $5^k\cdot n^{\Oh(1)}$ and Split Completion in time $5^k\cdot n^{\Oh(1)}$ (note that Split Edge Deletion is equivalent to Split Completion in the complement of the given graph). In fact, faster algorithms are known: Split Vertex Deletion can be solved in time $1.2738^k\cdot k^{\Oh(\log k)}+n^{\Oh(1)}$ [10], while Split Completion can be solved in subexponential parameterized time, more precisely in time $k^{\Oh(\sqrt{k})}\cdot n^{\Oh(1)}$, and admits a kernel with $\Oh(k^2)$ vertices [18]. Somewhat surprisingly, Split Editing is polynomial-time solvable [20], while both Split Vertex Deletion and Split Completion remain $\mathsf{NP}$-hard [27, 31]. This makes graph modification problems related to split graphs very well understood in the static setting, and of remarkably low complexity, which suggests that they may serve as a suitable testbed for considerations from the point of view of dynamic data structures.

In fact, split graphs have already been considered in the dynamic setting. Ibarra [22] gave a dynamic data structure with constant update time for the membership problem: the data structure maintains whether the graph in question is a split graph. This can be understood as the treatment of (any) modification problem for parameter $k$ equal to $0$. Further aspects of dynamic maintenance of split graphs were investigated by Heggernes and Mancini [21].

Our contribution.
In this work we propose a randomized dynamic data structure for the Split Completion problem whose amortized update time depends polylogarithmically on the size of the graph. Formally, we prove the following result.

We note that by a tiny modification of the algorithm, we can also provide an analogous data structure for the dynamic Split Edge Deletion problem, with same complexity guarantees.

Let us now discuss the main ideas behind the proof of <ref>. The basic approach is to try to dynamize the standard $5^k\cdot n^{\Oh(1)}$-time branching algorithm, which works as follows: recursively find an obstruction — an induced subgraph belonging to $\{2K_2,C_4,C_5\}$ — and branch into at most $5$ different ways on how to destroy this obstruction by adding an edge. To implement this strategy in the dynamic setting, we need to have an efficient way of finding an obstruction in the current graph, or concluding that it is split. Indeed, if we get such a localization procedure, then the branching algorithm can be implemented using data structure's own methods for inserting and removing edges.
A detailed description is presented in <ref>.

The next observation is that if $(G,k)$ is a of the Split Completion problem, then in particular it is also a of the Split Editing problem: one can obtain a split graph from $G$ by adding or removing at most $k$ edges. This is equivalent to the following statement: there is a partition $(A,B)$ of the vertex set of $G$ such that the number of edges with both endpoints in $B$ plus the number of non-edges with both endpoints in $A$ is at most $k$. For a partition $(A,B)$, this number is called the splittance of $(A,B)$. As observed by Hammer and Simeone [20], a partition with optimal splittance can be computed in polynomial time using a simple greedy argument. Ibarra [22] dynamized this observation and showed that a partition $(A,B)$ with optimum splittance can be maintained with $\Ohtilde(1)$ worst-case update time. Moreover, upon every edge update, the data structure of Ibarra moves only $\Oh(1)$ vertices between the parts $A$ and $B$.

Therefore, thanks to the result of Ibarra we may assume that a partition $(A,B)$ with optimum splittance is available to us; this gives us a basic structural understanding of $G$. If the splittance of $(A,B)$ is larger than $k$, then we are certain that $(G,k)$ is a of Split Completion. Hence, from now on we will work in the promise model: We will assume that the maintained partition $(A,B)$ has splittance bounded by $k$ at all times. Lifting the result from the promise model to the general setting can be done by making a wrapper data structure that works as follows: while the splittance is larger than $k$, the new updates are put on a queue instead of directly implemented, and when the splittance becomes at most $k$ again, all the enqued updates are implemented in one large batch. We remark that this is the only source of amortization in our data structure: in the promise model, the claimed running time guarantees are worst-case.

The wrapper data structure is presented in <ref>. We note that together with the partition $(A,B)$, the wrapper data structure also maintains sets $\nonEdgesA$ and $\edgesB$ consisting of non-edges with both endpoints in $A$ and edges with both endpoints in $B$, with a guarantee that they are correct whenever the splittance of $(A,B)$ is at most $k$. Note that then $|\nonEdgesA|+|\edgesB|\leq k$.

The next step is to implement efficient access to edges and non-edges crossing the partition $(A,B)$. More precisely, we need $\Ohtilde(k^{\Oh(1)})$-time queries that given $\ell\in \Oh(k)$, are able to list:

* for a given $a\in A$, any set of $\ell$ neighbors of $a$ in $B$; and

* for a given $b\in B$, any set of $\ell$ non-neighbors of $b$ in $A$.

If $a$ has fewer than $\ell$ neighbors in $B$, then the query should list all of them; similarly for $b$. As the second query is symmetric to the first one, we focus on the latter.

First, consider the case when $a$ has exactly one neighbor in $B$. Then to quickly recover this neighbor, we can maintain in the data structure the following information:

* the sum $s_A$ of the identifiers of all the vertices in $A$; and

* for every vertex $u$, the sum $s_u$ of the identifiers of all the neighbors of $u$.

Then given $a$, the identifier of the sole neighbor of $a$ in $B$ can be obtained by taking $s_a-s_A$ and adding the identifiers of all non-neighbors of $a$ in $A$, which can be listed in time $\Ohtilde(k)$ using the set $\nonEdgesA$. This trick can be lifted to listing all neighbors of $a$ in $B$ assuming that that their number is $\Oh(k)$ using the technique of color coding of Alon, Yuster, and Zwick [2]. Finally, to allow listing $\ell=\Oh(k)$ neighbors from possibly much larger neighborhoods, we sample in advance a polylogarithmically-sized family $\Ss$ of vertex subsets of varying sizes so that for any possible neighborhood $N$, with high probability among the sampled sets there will be some $S\in \Ss$ such that $\ell\leq |N\cap S|\leq \Oh(\ell)$. Then we apply the ideas presented above to list the members of $N\cap S$, whose number is already suitably bounded. We remark that this final trick is the only element of the reasoning that we do not know how to derandomize.
Implementation of this part of the proof is in <ref>.

The last step is to implement the procedure for finding of an obstruction. Here, the main idea is that every obstruction present in $G$ must contain a non-edge with both endpoints in $A$ or an edge with both endpoints in $B$; for otherwise it would be a split graph. For these (non-)edges, we have at most $k$ candidates contained in the lists $\nonEdgesA$ and $\edgesB$. Therefore, while searching for an obstruction, we can immediately “anchor” two of its vertices by guessing a member of $\nonEdgesA\cup \edgesB$ that is contained in the obstruction. Localizing the other two or three vertices of the obstruction requires a skillful juggle of the functionality specified above, in particular the methods for enumeration of (non-)neighbors across the partition $(A,B)$. This part of the argument can be found in <ref>.

§ PRELIMINARIES

For a positive integer $n$, we define $[n] \coloneqq \{1, 2, \ldots, n\}$.
If $x$ is a positive real number, we write $[x]$ as a shorthand for $[\ceil{x}] = \{ 1, 2, \ldots, \ceil{x} \}$.
For two sets $A$ and $B$, we denote their symmetric difference by
$A \symd B= (A \setminus B) \cup (B \setminus A)$.
Given any sets $A, B, C$ we write $C = A \uplus B$ if $C = A \cup B$, and $A \cap B = \emptyset$, that is, if $(A, B)$ is a partition of $C$.
For a boolean condition $b$, we denote by $\indic_b$ the indicator function of $b$, that is, $\indic_b = 1$ if $b$ is true, and $\indic_b = 0$ otherwise.

We use the $\Ohtilde(\cdot)$ notation to hide polylogarithmic factors; that is, $\Ohtilde(f(n))$ is the class of all functions $g(n)$ that are upper-bounded by $c\cdot f(n) \cdot (\log n)^c$ for some constant $c$.

All graphs considered in this paper are undirected and simple, that is, contain no loops or parallel edges. We often assume that the vertex set of a graph on $n$ vertices is $[n]$.

Let $G$ be a graph.
We denote the sets of vertices and of edges of $G$ by $V(G)$ and $E(G)$, respectively.
We refer to an edge $\{u, v \} \in E(G)$ as $uv$, for every pair of vertices $u$ and $v$.
For a vertex $v \in V(G)$, we denote the degree of $v$ by $d_G(v)$
and the set of all neighbors of $v$ by $N_G(v)$
(we may skip index $G$ if it is clear from the context).
Additionally, we define $\Non_G(v)$ as the set of non-neighbors of $v$, that is, $\Non_G(v) = V(G) \setminus (N_G(v) \cup \{ v \})$.

For a subset $A \subseteq V(G)$, we denote by $G[A]$ the subgraph of $G$ induced by $A$.
For a graph $F$, we say that $G$ is $F$-free if it does not contain an induced subgraph isomorphic to $F$.
Similarly, for a family of graphs $\Fc$, a graph $G$ is $\Fc$-free if it is $F$-free for every $F \in \Fc$.

Split graphs.

Let $G$ be a graph.
We say that $G$ is split if its vertices can be partitioned into two sets $A$ and $B$ such that $G[A]$ is a clique, and $G[B]$ is an independent set.
For any partition $(A, B)$ of $V(G)$, we denote

\[
\splittance_G(A, B) \coloneqq \binom{|A|}{2} - |E(G[A])| + |E(G[B])|,
\]

that is, $\splittance_G(A, B)$ counts the number of non-edges of $G$ within $A$ and edges of $G$ within $B$.

For the whole graph $G$, we write

\[
\splittance(G) \coloneqq \min_{(A, B) \colon V(G) = A \uplus B} \splittance_G(A, B).
\]

One can observe that $\splittance(G)$ counts the minimal number of edge updates (insertions or deletions) that need to be done on $G$ in order to make the graph $G$ split.
In particular, $G$ is split if and only if $\splittance(G) = 0$. It turns out that a partition with optimum splittance can be computed greedily by taking a prefix of the vertex set ordered by decreasing degrees, as stated formally in the following observation of Hammer and Simeone [20].

Let $G$ be a graph on $n$ vertices, and let $d_1 \geq d_2 \geq \ldots \geq d_n$ be a sorted sequence of the vertex degrees of $G$.
Define $m \coloneqq \max \{ i \in [n] \mid d_i \geq i - 1 \}$.

\[
\splittance(G) = m (m - 1) - \sum_{i = 1}^m d_i + \sum_{i = m + 1}^n d_i = 0,
\]

and a certifying partition $(A, B)$ of $V(G)$ can be obtained by taking the vertices of $G$ corresponding to the degrees $(d_1, \ldots, d_m)$ and $(d_{m+1}, \ldots, d_n)$, respectively.

We will also make use of another characterization of split graphs, namely via a finite family of forbidden induced subgraphs.

A graph $G$ is split if and only if $G$ is $\Fc$-free, where $\Fc = \{2K_2, C_4, C_5\}$.

Computation model and basic data structures.
We assume the standard word RAM model of computation with machine words of length $\Oh(\log n)$. As the most basic data structures, we use sets (representing a set of objects that can be updated by insertions and deletions, and queried for membership) and dictionaries (representing a set of key-value pairs that can be updated by insertions and deletions, and queried for the value associated with a given key). For both these data structures, we use standard implementations using any kind of self-balancing binary search trees, which offer all operations in worst-case time $\Oh(\log n)\subseteq \Ohtilde(1)$. In particular, graphs are represented as dictionaries mapping vertices to the sets of their neighbors. We refer to this representation as adjacency list representation. It allows verifying the adjacency of a pair of vertices in time $\Ohtilde(1)$.

Most of our data structures are randomized. We would like to stress that the random choices happen only during the initialization, and therefore the events of incorrectness of further queries are not independent — they all depend on the initial randomness.

§ DYNAMIC SPLITTANCE

In this section, we discuss how to maintain the value of $\splittance(G)$ with a witnessing partition $(A, B)$ of $V(G)$ for a dynamic graph $G$.
The data structure is a simple adaptation of the data structure of Ibarra [22] who showed how to maintain whether a dynamic graph $G$ is split.
For the sake of self-containedness, the proof is presented in <ref>.
We include the proof for the sake of self-containedness.

*lemsplitLemma <ref>

§ LISTING (NON-)EDGES ACROSS THE PARTITION

Let $G = (A \uplus B, E)$ be a dynamic graph whose vertices are partitioned into two sets $A$ and $B$ which might change over time.
In this section, we devise two auxiliary data structures that are responsible for listing all neighbors of a given $a \in A$ in the set $B$, provided this neighborhood is small, or sampling a sufficient number of neighbors of $a$ in $B$.
Symmetric queries can be also given for non-neighborhoods in $A$ of vertices $b \in B$.

Both data structures work under the promise that $\splittance_G(A, B) \leq k$. This promise will be lifted in the next section, where we design a wrapper data structure that works also when $\splittance_G(A, B) > k$. To facilitate the design of this wrapper data structure, both data structures presented in this section need to be able to process updates in batches: instead of being given only single edge updates, they will be given sets of edge modifications such that after applying all of them the condition $\splittance_G(A, B) \leq k$ is preserved.

Also, both data structures are assumed to have access to sets $\nonEdgesA, \edgesB$ consisting of non-edges with both endpoints in $A$ and edges with both endpoints in $B$, respectively. This access will be provided by the wrapper data structure.

We now give the first data structure, called $\promisenl$ (standing for neighbors listing).

There is a data structure $\promisenl[n, k, \ell, d, S]$,
parametrized by integers $k, \ell, d \in \N$ and a subset
$S \subseteq V(G)$,
that runs on a dynamic graph $G = (V, E)$ with $V=[n]$,
and maintains a partition $(A, B)$ of vertices of $G$

by supporting
the following operations:

* $\oper{initialize}(n, k, \ell, d, S)$: sets
$V \coloneqq [n]$, fixes the values of $k$, $\ell$, $d$
and $S$ for the entire run, initializes
$G \coloneqq (V, \emptyset)$ and
$(A, B) \coloneqq (\emptyset, V)$.
Runs in time $\Ohtilde(\ell d \cdot n)$.

* $\oper{update}(\Vmoved, \Emod, \nonEdgesA, \edgesB)$:
modifies the edge set of the underlying graph to
$E' \coloneqq E \symd \Emod$ and modifes the partition to
$(A',B') \coloneqq (A \symd \Vmoved,B \symd \Vmoved)$, provided that
after the update $\splittance_{G'}(A', B') \leq k$ for the
modified graph $G'=(V,E')$.
Requires two lists of edges
$\nonEdgesA, \edgesB \subseteq \binom{V}{2}$ storing the sets of
all non-edges of $G'[A']$ and all edges of $G'[B']$, respectively.
Note that both sets are of size at most $k$ since
$\splittance_{G'}(A', B') \leq k$.
The running time is
$\Ohtilde(k + \ell d \cdot (|\Vmoved| + |\Emod|))$.

Moreover, the data structure can answer the following queries:

* $\oper{listNeighborsBS}(a)$: given a vertex $a \in A$, either returns the set

\[
N \coloneqq  N_G(a) \cap B \cap S
\]

provided $|N| \leq \ell$, or reports TooMany if $|N| > \ell$.

* $\oper{listNonNeighborsAS}(b)$: given a vertex $b \in B$, either returns the set

\[
N \coloneqq  \Non_G(b) \cap A \cap S
\]

provided $|N| \leq \ell$, or reports TooMany if $|N| > \ell$.

Both queries run in time $\Ohtilde(k \ell d)$ and return correct answers with probability $1 - \Oh(n^{-d})$.

Let $\gamma$ be some large enough constant whose value will be set later.
We assume that $\ell \leq n$, for otherwise we might set $\ell \coloneqq  n$, and this would not affect answers to the queries.
We also denote the sum of the vertex indices in a set
$X \subseteq V$ as $\sumset(X)=\sum_{v \in X} v$.
The data structure $\promisenl[n, k, \ell, d, S]$ stores:

* the adjacency list representation of $G$ and
representation of $A$ and $B$ as sets;

* the integer values of $k, \ell, d$ and $S \subseteq V(G)$ represented as a set;

* the sets of edges
$\nonEdgesA, \edgesB \subseteq \binom{V(G)}{2}$
provided in the updates, as lists;

* for every $i \in [\gamma d \log n]$, a vertex $\ell$-coloring $\chi_i \colon V(G) \to [\ell]$.
Define $S_{i, c} \coloneqq  S \cap \chi_i^{-1}(c)$, for every $i \in [\gamma d \log n]$ and $c \in [\ell]$; these sets are also stored in the data structure;

* the following integer values:

\begin{align*}
\oper{countS}(v) & = |N_G(v) \cap S|\quad \text{for every } v \in V(G);\\
\oper{countAS} & = |A \cap S|; \qquad \oper{countBS} = |B \cap S|; \\
\oper{idSumS}_{i, c}(v) & = \sumset( N_G(v) \cap S_{i, c} )\quad \text{for every } i \in [\gamma d \log n], c \in [\ell] \text{ and } v \in V(G); \\
\oper{idSumAS}_{i,c} & = \sumset( A \cap S_{i, c} )\quad \text{for every } i \in [\gamma d \log n] \text{ and } c \in [\ell];\\
\oper{idSumBS}_{i,c} & = \sumset( B \cap S_{i, c} ) \quad \text{for every } i \in [\gamma d \log n] \text{ and } c \in [\ell].
\end{align*}

Before proceeding with the description of operations, let us give a brief idea how these variables are going to be used.
Consider a vertex $a \in A$.
Using the variables $\oper{count}$- and the set $\nonEdgesA$, one can obtain the number of neighbors of $a$ in the set $B \cap S$ by applying a simple inclusion-exclusion formula.
If this neighborhood $N$ is  of size at most $\ell$, we would like to list all the vertices of $N$.
To this end, we use the vertex colorings $\chi_i$ and the corresponding variables $\oper{idSum}$-.
Each coloring $\chi_i$ will be initialized randomly.
Therefore, with high probability, for every vertex $v \in N$, there will be a coloring $\chi_i$ such that under $\chi_i$, $v$ has a different color than all the other vertices of $N \setminus \{v\}$.
By applying a similar inclusion-exclusion principle on the variables $\oper{idSum}$- we will be able to retrieve an identifier of $v$.

* We initialize the adjacency representation of $G$
to store an edgless graph on vertices $[n]$.
We initialize $A=\emptyset$ and $B=V$.
Also, we set the lists
$\nonEdgesA,\edgesB$ to be empty.

* We store the values of $k, \ell, d$ and $S$ as a set.

* All colorings $\chi_i$ are initialized randomly, that is, for every $i \in [\gamma d \log n]$ and $v \in V(G)$, we choose a color for $\chi_i(v)$ uniformly at random from the set $[\ell]$.
The colorings are fixed for the entire run as well, and so are sets $S_{i,c}$.

* Since the initial graph is empty, all the values $\oper{count}$- and $\oper{idSum}$- can be computed according to their definitions in total time $\Ohtilde(\ell d \cdot n)$.

Consider an update $\oper{update}(\Vmoved, \Emod, \nonEdgesA, \edgesB)$.
First, we save the new values of $\nonEdgesA$ and $\edgesB$.
Observe that the functions $\oper{countS}(\cdot)$ and $\oper{idSumS}_{i, c}(\cdot)$ need to be changed only for the endpoints of the edges of $\Emod$, and the remaining $\Ohtilde(\ell  d)$ stored variables are affected only by vertices moved between $A$ and $B$.
Therefore, the entire update takes $\Ohtilde(k + \ell d \cdot (|\Vmoved| + |\Emod|))$ time.

We show how to answer the query $\oper{listNeighborsBS}(a,\ \nonEdgesA)$
for a vertex $a \in A$.
Recall that since $\splittance_G(A, B) \leq k$, there are at most $k$ non-edges within $A$, i.e., $|\nonEdgesA| \leq k$.
Let $N \coloneqq  N_G(a) \cap B \cap S$.
We start with the following observation.

Now, as a first step to answer
$\oper{listNeighborsBS}(a,\ \nonEdgesA)$ query, we compute $|N|$.
If $|N| > \ell$, we report TooMany.
So assume that $|N| \leq \ell$.
For a vertex $b \in N$ and a coloring $\chi_i$,
let us say that $b$ is exposed by the coloring $\chi_i$
if $\chi_i(b) \neq \chi_i(b')$ for every $b' \in N \setminus \{b\}$. First, we note that every member of $N$ is exposed with high probability.

Next, we note that once a vertex of $N$ is exposed, its identifier can be easily computed using a similar inclusion-exclusion principle as in the proof of <ref>.

We already have all the tools to finish the implementation of the query $\oper{listNeighborsBS}(a)$.
To list all the elements of $N$,
it is enough to iterate over all indices
$i \in [\gamma d \log n]$ and colors $c \in [\ell]$,
and for each pair $(i, c)$ retrieve the
value that is described in <ref>
and check whether the returned value is a vertex that belongs to
By <ref>, this procedure will retrieve the entire
set $N$ with probability at least $1 - n^{-d}$ and the total
running time is bounded by $\Ohtilde(k \ell d)$.

To answer the queries $\oper{listNonNeighborsAS}(b,\ \edgesB)$ for $b \in B$ we proceed analogously.
To this end, we need additionally the values of:

* $|\Non_G(b) \cap S|$ which can be obtained from the values of $|N_G(b) \cap S|$ and $|S|$; and

* $\sumset( \Non_G(b) \cap S_{i, c} ) $ which we can
obtain from $\sumset( N_G(b) \cap S_{i, c} )$ and
$\sumset( S_{i, c} ) $, where the latter sums can be precomputed during the initialization.

We note that the application of color coding presented in <ref> and <ref> can be derandomized in a standard way, by replacing sampling the sets $S_{i,c}$ with drawing them from a suitable universal hash family; see e.g. <cit.>. However, as we will use randomization again in our second data structure (<ref> below), we prefer to present color coding here in a randomized, and therefore simpler manner.

So far, we can list $\ell$ neighbors of a vertex $a \in A$ in the set $B \cap S$ only under an assumption that this neighborhood $N$ is small.
However, this condition does not need to hold in general, and in
the next sections we will also need to find several neighbors of $a$ in $B$ (more precisely, a subset of $N$ of size $\Theta(k)$) in the case when the set $N$ is large.
This is the responsibility of our next data structure, named $\promisens$ (standing for neighbors sampling).
Roughly speaking, this data structure will store a set of layers
of the vertex set, where the $i$th layer contains
roughly $n / 2^i$ random vertices of $G$.
Then, provided $|N| > \ell$,
with high probability one of the layers will contain $\Theta(\ell)$ vertices of $N$. By running an instance of $\promisenl$ on each layer, we will be able to retrieve those vertices.

There exists a data structure $\promisens[n, k, \ell, d]$,
parametrized by integers $k, \ell, d \in \N$,
that runs on a dynamic graph $G = (V, E)$ with $V=[n]$,
and maintains a dynamic partition $(A, B)$ of vertices of $G$

by supporting
the following operations:

* $\oper{initialize}(n, k, \ell, d)$: sets
$V \coloneqq [n]$, fixes the values of $k$, $\ell$ and $d$
for the entire run, initializes
$G \coloneqq (V, \emptyset)$ and
$(A, B) \coloneqq (\emptyset, V)$.
Runs in time $\Ohtilde(\ell d^2 \cdot n)$.

* $\oper{update}(\Vmoved, \Emod, \nonEdgesA, \edgesB)$:
modifies the edge set of the underlying graph to
$E' \coloneqq E \symd \Emod$ and modifes the partition to
$(A',B') \coloneqq (A \symd \Vmoved,B \symd \Vmoved)$, provided that
after the update $\splittance_{G'}(A', B') \leq k$ for the
modified graph $G'=(V,E')$.
Requires two lists of edges
$\nonEdgesA, \edgesB \subseteq \binom{V}{2}$ storing the sets of
all non-edges of $G'[A']$ and all edges of $G'[B']$, respectively.
Note that both sets are of size at most $k$ since
$\splittance_{G'}(A', B') \leq k$.
The running time is
$\Ohtilde(kd + \ell d^2 \cdot (|\Vmoved| + |\Emod|))$.

Moreover, the data structure can answer the following queries:

* $\oper{sampleEdges}(a)$: given a vertex $a \in A$, returns a subset

\[
\NBsample(a) \subseteq N_G(a) \cap B
\]

of size $\min(\ell, |N_G(a) \cap B|)$;

* $\oper{sampleNonEdges}(b)$: given a vertex $b \in B$, returns a subset

\[
\NAsample(b) \subseteq \Non_G(b) \cap A
\]

of size $\min(\ell, |\Non_G(b) \cap A|)$.

Both queries run in time $\Ohtilde(k\ell d^2)$ and
return correct answers with probability
$1 - \Oh(n^{-d})$.

The data structure $\promisens[n, k, \ell, d]$ stores:

* the adjacency lists representation of $G$
and representation of $A$ and $B$ as sets;

* the values of the parameters $k$, $\ell$, and $d$;

* the sets
$\nonEdgesA, \edgesB \subseteq \binom{V(G)}{2}$
given in the updates, as lists;

* a single instance $\promisenl[n, k, \ell', d, S]$ of the data structure from <ref> running on the same dynamic graph $G$, where $\ell' \coloneqq 72\ell$ and $S \coloneqq V(G)$;

* for every $i \in [\log n]$ and $j \in [d \log n]$, a subset of vertices $V_{i, j} \subseteq V(G)$, fixed upon initialization and not modified later on; and

* for every $i \in [\log n]$ and $j \in [d \log n]$, an instance $\promisenl_{i,j}[n, k, \ell', d, S_{i, j}]$ of the data structure from <ref> running on the same dynamic graph $G$, where $S_{i,j} \coloneqq V_{i, j}$.

Intuitively, we want the set $V_{i, j}$ to be a random subset containing roughly $n/2^i$ vertices of $G$.
To achieve this, for every $i \in [\log n]$ and $j \in [d \log n]$, and every vertex $v \in V(G)$, we put $v$ into the set $V_{i, j}$ with probability $2^{-i}$, independently.
Then, we initialize all the data structures $\promisenl$ and $\promisenl_{i,j}$.
The total running time of this phase is bounded by

\[ \log n \cdot d \log n \cdot \Ohtilde(\ell' d \cdot n) \subseteq \Ohtilde(\ell d^2 \cdot n).\]

Given an update with arguments $(\Vmoved, \Emod, \nonEdgesA, \edgesB)$, we simply pass it to all the stored data structures.
The running time is thus bounded by

\[
\log n \cdot d \log n \cdot \Ohtilde(k + \ell' d \cdot (|\Vmoved| + |\Emod|)) \subseteq \Ohtilde(kd + \ell d^2 \cdot (|\Vmoved| + |\Emod|)).
\]

Fix a vertex $a \in A$.
We show how to answer the query $\oper{sampleEdges}(a)$.
The implementation of queries $\oper{sampleNonEdges}(b)$, for $b \in B$, is symmetric.
Let $N \coloneqq N_G(a) \cap B$.
Our goal is to sample a subset of the set $N$ of size $\min(\ell, |N|)$.

First, consider the case when $|N| \leq \ell'$.
Then, by querying the structure $\promisenl$ about the list of
neighbors of $a$ in the set $B \cap V(G) = B$
(i.e., we run $\oper{listNeighborsBS}(a)$), we obtain all the
vertices of $N$ with probability at least $1 - \Oh(n^{-d})$.
Otherwise, the call returns $\textsc{TooMany}$, and we can proceed as follows.

From now on, assume that $|N| > \ell'=72\ell$.
Then, we query all the data structures $\promisenl_{i, j}$ about the list of neighbors of $a$ in the corresponding sets $B \cap V_{i, j}$ (i.e., we run $\oper{listNeighborsBS}(a)$ on each $\promisenl_{i, j}$).
We prove that with probability
at least $1 - \Oh(n^{-d})$ one of such queries will correctly return at least $\ell$ elements of $N$.
Define $N_{i, j} \coloneqq N \cap V_{i, j}$, for every $i \in [\log n]$, $j \in [d \log n]$.

Take an index $i \in [\log n]$ satisfying <ref>.
We know that with probability at least
$1 - n^{-d\ell}$ there exists $j \in [d \log n]$ such that the
set $N_{i, j}$ contains more than $12\ell > \ell$ but less than $72\ell = \ell'$ vertices.
The corresponding query to the data structure $\promisenl_{i, j}$ will return at least $\ell$ elements of $N_{i, j} \subseteq N$ with probability at least $1 - \Oh(n^{-d})$.
Hence, by the union bound, the probability of incorrectly answering the query $\oper{sampleEdges}(a)$ is upper bounded by $n^{-d\ell} + \Oh(n^{-d}) \subseteq \Oh(n^{-d})$.
The running time is dominated by the total running time of queries on all structures $\promisenl_{i, j}$ which is bounded by
$\log n \cdot d \log n \cdot \Ohtilde(k\ell' \cdot d) \subseteq \Ohtilde(k\ell \cdot d^2)$.

§ LIFTING THE PROMISE

In the previous section we presented data structures that work under the promise that $\splittance_G(A, B) \leq k$.
Now, we focus on the general case when no such condition is guaranteed to hold.
The main responsibility of our next data structure, $\nsample[n, k, d]$, is to implement the same functionality as data structures $\promisenl$ and $\promisens$, but to work without the assumption that $\splittance_G(A, B) \leq k$ and, additionally, to offer methods for listing non-edges with both endpoints in $A$ and edges with both endpoints in $B$ (these were needed for queries in the data structures $\promisenl$ and $\promisens$).

All those methods are required to give correct outputs only when the inequality $\splittance_G(A,B) \leq k$ holds, but the data structure should persist also when $\splittance_G(A,B)>k$, and return to giving correct answers again once the splittance decreases to at most $k$.

There exists a data structure $\nsample[n, k, d]$ parametrized by integers
$k, d \in \N$ that runs on a
dynamic graph $G = (V, E)$ with $V=[n]$ and
maintains a partition $(A, B)$ of $V$ satisfying
$\splittance_G(A, B) = \splittance(G)$ by supporting the
following operations:

* $\oper{initialize}(n, k, d)$: sets $V \coloneqq [n]$,
fixes the values of
$k$ and $d$ for the entire run, initalizes
$G \coloneqq (V, \emptyset)$ and
$(A, B) \coloneqq (\emptyset, V)$.
Runs in time $\Ohtilde(kd^2 \cdot n)$.

* $\oper{update}(uv)$:
inserts edge $uv$ if $uv \not\in E(G)$
or removes edge $uv$ if $uv \in E(G)$. Runs
in $\Ohtilde(kd(k + d))$ amortized time.

* $\oper{splittance}()$:
returns $\splittance(G)$ in time $\Oh(1)$.

Moreover, if  $\splittance(G) \leq k$,
the data structure answers the following queries:

* $\oper{listNonEdgesA}()$: returns the list of all non-edges of $G$ with both endpoints in $A$;

* $\oper{listEdgesB}()$: returns the list of all edges of $G$ with both endpoints in $B$;

* $\oper{sampleEdges}(a)$: given a vertex $a \in A$, returns a subset
\NBsample(a) \subseteq N_G(a) \cap B
of size $\min(10k, |N_G(a) \cap B|)$;

* $\oper{sampleNonEdges}(b)$: given a vertex $b \in B$, returns a subset
\NAsample(b) \subseteq \Non_G(b) \cap A
of size $\min(10k, |\Non_G(b) \cap A|)$.

The queries $\oper{listNonEdgesA}$ and $\oper{listEdgesB}$ run in time $\Ohtilde(k)$, and the queries $\oper{sampleEdges}$ and $\oper{sampleNonEdges}$ run in time $\Ohtilde(k^2d^2)$.
The data structure is randomized and returns correct answers
with probability $1 - \Oh(n^{-d})$.

The data structure $\nsample[n, k, d]$ stores:

* the adjacency list representation of $G$ and
representation of $A$ and $B$ as sets;

* the values of $k$ and $d$;

* an instance $\dsplit[n]$ of the data structure from <ref> running on $G$;

* an instance $\promisenl[n, k, \ell, d', S]$ of the data structure from <ref>, where $\ell = k$, $d' = d+3$ and $S = V(G)$;

* an instance $\promisens[n, k, \ell', d]$ of the data structure from <ref>, where $\ell' = 10k$;

* a set $\oper{verticesUpd} \subseteq V(G)$ and
$\oper{edgesUpd}, \oper{edgesB},
\oper{nonEdgesA} \subseteq \binom{V(G)}{2}$
described in the next paragraph.

Let $G_0, G_1, \ldots, G_t$ be a sequence of consecutive graphs
maintained by our data structure, that is,
for every $i = 0, 1, \ldots, t-1$, $G_{i+1}$ is obtained from $G_i$
by adding or removing a single edge.
Moreover, let $(A_i, B_i)$ be the corresponding partition
of  $V(G_i)$ maintained by the data structure,
and let $E_i$ be the set of edges of $G_i$, for $i = 0, \ldots, t-1$.
Define $s \coloneqq \max\ \{ 0 \leq i \leq t \mid \splittance(G_i) \leq k \}$.
Note that $s$ is well-defined as the initial graph $G_0$ is a
split graph.
Then, sets $\oper{verticesUpd},
\oper{edgesUpd}, \oper{edgesB},
\oper{nonEdgesA}$
are defined by the following invariants that must be satisfied at all times:

* $\oper{edgesB}$ is the set of all edges of the graph $G_s[B_s]$, and $\oper{nonEdgesA}$ is the set of all non-edges of the graph $G_s[A_s]$, both with probability $1 - \Oh(n^{-d})$;

* $\oper{verticesUpd} = A_s \symd A_t = B_s \symd B_t$, and $\oper{edgesUpd} = E_s \symd E_t$;

* the data structures $\promisenl$ and $\promisens$ store the graph $G_s$ with the partition $(A_s, B_s)$ of its vertices.

In other words, sets $\oper{edgesB}$ and $\oper{nonEdgesA}$ store the answers to the queries $\oper{listEdgesB}()$ and $\oper{listNonEdgesA}()$ that were correct at the last time step when the splittance was bounded by $k$. Sets $\oper{verticesUpd}$ and $\oper{edgesUpd}$ store all the updates that got accumulated since this time step.
Also, note that the data structures $\promisenl$ and
$\promisens$ run on the graph $G_s = (A_s \uplus B_s, E_s)$,
not $G_t$, as they require that the stored graph $G$ and its
partition $(A,B)$ satisfy
$\splittance_G(A,B) \leq k$.

Let us observe at this point that one can assume that the inequality $s \leq n^2$ holds.
This comes from the fact that after  $n^2$ updates, we can recompute the correct values of $\oper{edgesB}$ and $\oper{nonEdgesA}$ for $G_s$ (and renumber $G_0 \coloneqq  G_s$) which amortizes to $\Ohtilde(1)$ cost per update.

Since the initialization of is straightforward, we moved the detailed description to <ref>.

Consider an operation $\oper{update}(uv)$, where $uv$ is an edge to
be inserted or deleted.
First, we pass the same update to the inner structure $\dsplit$ which returns a subset of vertices $\Vmoved$ of size $\Oh(1)$ which need to be moved between $A$ and $B$.
Then, we can update the sets $A$ and $B$, accordingly.
Next, we update sets $\oper{verticesUpd}$ and
$\oper{edgesUpd}$ as follows:

\oper{verticesUpd}' = \oper{verticesUpd} \symd \Vmoved \quad \text{ and } \quad \oper{edgesUpd}' = \oper{edgesUpd} \symd \{ e \}.

Let $G_s, G_{s+1}, \ldots, G_t = G$ be the suffix of the sequence of consecutive graphs given to the data structure, where $s$ is the previous moment our dynamic graph $G$ was of splittance at most $k$.
If $\splittance(G_t) > k$, we can finish the update as all the invariants , and hold.
The running time is $\Ohtilde(1)$.

Now, assume that $\splittance(G_t) \leq k$.
Then $\max\ \{ 0 \leq i \leq t \mid \splittance(G_i) \leq k \} = t$, and we need to perform additional modifications so that the invariants , and hold.
Let $r \coloneqq t - s$ be the number of updates that were applied since the last time our graph was of splittance at most $k$.
Our goal now is to recompute the sets $\edgesB$ and $\nonEdgesA$, so that the invariant holds, in time proportional to $r$.
First, let us make a useful observation.

Now, let us focus on updating the set $\edgesB$, so that after the update it reflects time step $t$ instead of $s$ (the set $\nonEdgesA$ is handled analogously).
In other words, we need to locate all the edges of $G_t$ with both endpoints in $B_t$.
Denote this new set by $\edgesB'$.
All such edges can be classified into the following three
categories (see <ref> for illustration). In the following, we use variables $\edgesB$
and $\nonEdgesA$ as they are in the data structure before
updating, i.e., their content refers to the time step $s$.

(1) Edges $b_1 b_2$, where $b_1, b_2 \in B_s \cap B_t$.

Observe that every edge in $G_t$ of this form is either

* an edge of $G_s[B_s]$, but there were at most $k$ such ones as $\splittance(G_s) \leq k$; or

* an edge inserted during an update after time step $s$, but there are at most $r$ such ones.

So using the sets $\edgesB$ and $\oper{edgesUpd}$ we can enumerate all such edges in time $\Ohtilde(k + r)$.

(2) Edges $a_1 a_2$, where $a_1, a_2 \in A_s \cap B_t$.

We can list the set $A_s \cap B_t \subseteq \oper{verticesUpd}$ in time $\Ohtilde(r)$, and by <ref> we can check all the pairs of vertices of $A_s \cap B_t$ in time $\Ohtilde(r + k)$.

(3) Edges $a_1 b_1$, where $a_1 \in A_s \cap B_t$ and $b_1 \in B_s \cap B_t$.

To list all such edges we start with applying on $\promisenl$ a temporary modification by calling

\[
\oper{update}(\emptyset,\ \Emod,\ \nonEdgesA,\ \edgesB),
\]
where $\Emod=\Emod_1 \cup \Emod_2$ consists of:

* $\Emod_1$: all edges of $\oper{edgesUpd}$ of the form $ab$, where $a \in A_s \cap B_t$ and $b \in B_s \cap B_t$; there are at most $r$ such edges.

* $\Emod_2$: all edges of the graph $G_s$ of the form $ab$, where $a \in A_s \cap B_t$ and $b \in B_s \cap A_t$; we can list these edges brutally in time $\Ohtilde(r+k)$ by <ref>.

That is, structure $\promisenl$ works now on the graph $\Gtmp = (A_s \uplus B_s, \Etmp)$ such that

* the graphs $\Gtmp[A_s]$ and $\Gtmp[B_s]$ are isomorphic $G_s[A_s]$ and $G_s[B_s]$, respectively,

* there are no edges between $A_s \cap B_t$ and $A_t \cap B_s$, and

* the edges between $A_s \cap B_t$ and $B_s \cap B_t$ coincide in the graphs $\Gtmp$ and $G_t$.

The cost of this temporary update is $\Ohtilde(k + \ell d'(k + r)) = \Ohtilde(kd(k + r))$.
Observe that $\edgesB$ and $\nonEdgesA$ store currently
respectively the edges within $B_s$ and non-edges within
$A_s$ in $\Gtmp$, and thus $\splittance_{\Gtmp}(A_s,B_s) \leq k$,
as required by the $\promisenl$ data structure.

Now, we iterate over all vertices $a \in A_s \cap B_t$;
recall that their number is bounded by $r$ as they are all
contained in $\oper{verticesUpd}$.
Recall that $\splittance_{G_t}(A_t, B_t) \leq k$, hence
$a$ has at most $k$ neighbors in $B_s \cap B_t$, and we
would like to list them all.
However, this can be done precisely by calling
$\oper{listNeighborsBS}(a)$ on $\promisenl$.
The total cost of such queries for
all $a_1 \in A_s \cap B_t$ is

\[
\Ohtilde(|A_s \cap B_t| \cdot k \ell d') \leq \Ohtilde(r k^2 d).
\]

Finally, we revert $\promisenl$ to the state before the temporary update, by calling

\[
\oper{update}(\emptyset,\ \Emod,\ \nonEdgesA,\ \edgesB).
\]

Summing up, the amortized cost of computing the set $\edgesB'$ (and $\nonEdgesA'$) is upper-bounded by

\[
\frac{\Ohtilde(k + r) + \Ohtilde(r + k) + \Ohtilde(k d (k + r)) + \Ohtilde(r k^2d)}{r} \subseteq \Ohtilde(k^2 d).
\]

Now, we need to bound the probability of incorrectly computing the sets $\edgesB'$ and $\nonEdgesA'$.
In the process of recomputation we do at most $\Oh(n)$ queries to $\promisenl$, each having an error probability $\Oh(n^{-d'}) = \Oh(n^{-(d+3)})$.
Hence, with probabilty $1 - \Oh(n^{d+2})$ all these queries return correct answers.
Furthermore, we rely on the fact that the sets $\edgesB$ and $\nonEdgesA$ were computed correctly for the graph $G_s$.
Recall that we can assume $s \leq n^2$, and thus by the union bound these sets were computed correctly for all the graphs $G_0, \ldots, G_t$ with probability at least

\[
1 - n^2 \cdot \Oh(n^{-(d+2)}) = 1 - \Oh(n^{-d}).
\]

Next, we should update the structures $\promisenl$ and $\promisens$ so that their inner states correspond to the graph $G_t$.
To this end, we run on both structures the update

\[
\oper{update}(\oper{verticesUpd},\ \oper{edgesUpd},\ \nonEdgesA',\ \edgesB').
\]

Then, the invariant holds, and the amortized cost of these updates is

\[
\frac{\Ohtilde(k + r \ell d') + \Ohtilde(k d + r\ell' d^2 )}{r} \subseteq \Ohtilde(k d^2).
\]

Finally, we set $\oper{verticesUpd}' \coloneqq \emptyset$ and $\oper{edgesUpd}' \coloneqq \emptyset$, so that invariant holds.

Each query can be answered by doing a single call to one of the structures $\dsplit$ or $\promisens$.
The details are given in <ref>.

§ LOCALIZING THE OBSTRUCTIONS

Let us recall that the graph is split if and only if it is
$\Fc$-free, where $\Fc = \{2K_2, C_4, C_5\}$.
We call the members of ${\Fc}$ simply obstructions.
In this section, using the interface of the data structure $\nsample[n, k, d]$ from <ref>, we show how to extend this data structure with a method that is able to either conclude that $G$ is split, or report an obstruction in $G$ witnessing that it is not split.
The following statement encapsulates this result.

The data structure $\nsample[n, k, d]$
of <ref> can be extended by a method

* $\oper{findObstruction}()$ which returns if $\splittance(G) = 0$; or a subset of vertices $U \subseteq V(G)$ such that the induced subgraph $G[U]$ is isomorphic to one of the graphs of $\Fc = \{ 2K_2, C_4, C_5 \}$ if $0 < \splittance(G) \leq k$.

The query runs in time $\Ohtilde(k^{\Oh(1)} \cdot d^2)$ and is correct with probability $1-\Oh(n^{c-d})$ for some constant $c$ whenever $\splittance(G) \leq k$; without this assumption, there are no guarantees on the correctness.

We assume that $\splittance(G) = \splittance_G(A, B) \leq k$, otherwise we can provide any answer.

In what follows, we use extensively the following two

The second observation is symmetric to the first one.
We include the statement for clarity.

Let $b_1, b_2 \in B$ be vertices such that $b_1b_2 \in E(G)$. Then, at least one of the following holds:

* there is a subset $U \subseteq V(G)$ such that $\{b_1, b_2\} \subseteq U$ and $G[U]$ is isomorphic to $2K_2$ or $C_4$;

* at least one of the vertices $b_1, b_2$ has at most $3\sqrt{k}$ non-neighbors in $A$.

Moreover, in time $\Ohtilde(k^2 d^2)$ we can return a
case that holds, together with a witnessing set $U$ for the
first case, or the non-neighborhood of $b_1$ or $b_2$ in
$A$ for the second case. The answer is correct with probability
at least $1 - \Oh(n^{-d})$.

We are ready to proceed with the description of the
$\oper{findObstruction}(\cdot)$ query.
Suppose now that there is a set $U \subseteq V(G)$ such that
$G[U]$ is an obstruction.
We examine all three cases for $G[U] \in \{2K_2, C_4, C_5\}$, and
in each case we provide a procedure that, assuming the existence of
$U$ as above, detects some set $U'$ (possibly different from $U$)
that induces an obstruction. If no case yields an obstruction,
we conclude that $G$ is split.
It will be always clear that the procedure for locating $U'$ runs
in time $\Ohtilde(k^{\Oh(1)})$.

Recall that by running $\oper{listNonEdgesA}()$ and $\oper{listEdgesB}()$, we have access to the sets $\oper{nonEdgesA}$ containing all non-edges within $A$ and $\oper{edgesB}$ containing all edges within $B$, and each of these sets has cardinality at most $k$. For brevity, a set is small if its size is at most $3\sqrt{k}$.

Localizing $2K_2$.
Suppose first that $G[U]=G[\{x,y,z,t\}]$ is isomorphic to $2K_2$, where $xy, zt \in E(G)$.
We consider all possible alignments of vertices $x, y, z, t$ with
respect to the partition $(A, B)$. We divide the analysis
into five cases depening on
the intersection $U \cap A$. See <ref> in <ref> for an illustration.

(a) $|U \cap A| = 4$.

Then, in particular, $xt$ and $yz$ are two non-edges within $A$.
Hence, $U$ can be detected by exhaustive search through all the pairs of non-edges in the set $\nonEdgesA$.

(b) $|U \cap A| = 3$.

Without loss of generality assume that $U \cap A = \{x, y, z\}$.
Since $xz$ and $yz$ are two non-edges with both endpoints in $A$ we can list all $\Oh(k^2)$ candidates for $(x, y, z)$ by inspecting all the pairs of non-edges in $\nonEdgesA$.
Having $(x, y, z)$ fixed, it remains to locate (any) vertex $t' \in B$ that is a neighbor of $z$ and a non-neighbor of $x$ and $y$ (the original vertex $t\in U$ witnesses that such $t'$ exists).
We call $\oper{sampleEdges}(z)$ on $\nsample$ to obtain a set $\NBsample(z)$ consisting of up to $10k$ neighbors of $z$ in $B$.
If $|\NBsample(z)| < 10k$, then $\NBsample(z)$ contains all neighbors of $z$ in $B$, and we can test all of them for a vertex $t'$.
So assume now that $|\NBsample(z)| = 10k$.
Then, we run the subroutine from <ref> for pairs $(x, z)$ and $(y, z)$.
If any of these calls detects and returns an obstruction, we are done.
Otherwise, since $z$ has more than $3\sqrt{k}$ neighbors in $B$, both $x$ and $y$ must have at most $3\sqrt{k}$ neighbors in $B$ and the subroutine returns the corresponding sets.
Denote them by $N_B(x)$ and $N_B(y)$.

\[
|\NBsample(z)| = 10k > 3\sqrt{k} + 3\sqrt{k} \geq |N_B(x)| + |N_B(y)|,
\]

there exists a vertex $t' \in \NBsample(z) \setminus (N_B(x) \cup N_B(y))$. Then $x,y,z,t'$ induce a $2K_2$.

(c) $|U \cap A| = 2$ and the vertices of $U \cap A$ are adjacent in $G$.

Without loss of generality assume that $U \cap A = \{ x, y \}$ and $U \cap B = \{z, t\}$.
Then $zt$ is an edge with both endpoints in $B$, hence using the set $\edgesB$ we can list $\Oh(k)$ candidates for $(z, t)$ and thus fix $(z,t)$.
Next, we run the subroutine from <ref> for $(z, t)$, and assume that it did not detect an obstruction (for otherwise we are done).
Then, the subroutine discovers that one of $z$ or $t$ (say $z$) has small non-neighborhood $\Non_A(z)$ in $A$. Since $x, y \in \Non_A(z)$, it is enough to check at most $\binom{3\sqrt{k}}{2}=\Oh(k)$ candidates for $(x, y)$.

Due to the space constraints, we present the remaining cases in <ref>.

Localizing $C_4$.

Again, suppose that $G[U]=G[\{x,y,z,t\}]$ is isomorphic to $C_4$, where $xy, zt \not\in E(G)$.
Note that $C_4$ is the complement of $2K_2$, and all our data structures are symmetric under taking the complement and swapping the sides $(A, B)$.
So the analysis of possible arrangements of $C_4$ is fully symmetric to the analysis of $2K_2$, and hence we omit it.

Localizing $C_5$.

Since the analysis of possible arrangements of $C_5$ is done similarly to the case of $2K_2$, we present it in <ref>.

This finishes the case study.
Let us summarize the implementation of the query
Every such query makes single calls $\oper{listNonEdgesA}()$
and $\oper{listEdgesB}()$, $k^{\Oh(1)}$ calls $\oper{sampleEdges}(\cdot)$ and $\oper{sampleNonEdges}(\cdot)$ (either directly, or via the calls to the subroutines from <ref> and <ref>), and spends $\Ohtilde(k^{\Oh(1)})$ time on internal computation.
Therefore, the total running time of $\oper{findObstruction}()$ is bounded by

\[
k^{\Oh(1)} \cdot \Ohtilde(k^2 d^2) + \Ohtilde(k^{\Oh(1)}) \subseteq \Ohtilde(k^{\Oh(1)} \cdot d^2).
\]

Further, as we may assume that $k\leq n^2$, the probability of
incorrectly answering the query is:

\[
\Oh\left(n^{-d} \right) + \Oh(k^{\Oh(1)}) \cdot \Oh \left( n^{-d}\right) = \Oh\left(n^{\Oh(1)} \cdot n^{-d}\right) \subseteq \Oh\left(n^{c-d}\right).
\]

for some fixed constant $c$.

With <ref> established, the proof of <ref> follows easily: Assuming we maintain the data structure $\nsample$ extended as in <ref>, upon each query one simply executes the standard branching algorithm for Split Completion, using method $\oper{findObstruction}()$ for finding consecutive obstructions and $\oper{update}(\cdot)$ for modifying the graph on the fly during backtracking. Details can be found in <ref>.

§ BRANCHING

We are ready to prove our main result, <ref>, which we recall for convenience.

Our main data structure stores:

* the values of $k$ and $d$;

* an instance $\nsample[n, k, d']$ of the data structure
from <ref>, extended with a method
from <ref>, for $d' \coloneqq d+k+c$, where $c$ is
the constant from <ref>.

We set the values of $k$ and $d$ for the entire run, and initialize the inner data structure $\nsample$ with corresponding values.
The total running time of this phase is

\[
\Ohtilde(k \cdot d'^2 \cdot n) = \Ohtilde(k^{\Oh(1)} \cdot d^2 \cdot n).
\]

Consider an edge update $e = uv$ (that is, we either insert $e$ to the graph $G$, or remove it).
First, we pass this to the structure $\nsample$.
Let $G'$ denote the newly obtained graph.
Now, we should update the answer to our query: we need to determine whether one can insert at most $k$ edges to $G'$ so that the resulting graph is split.

If $\splittance(G') > k$, then we know that $(G',k)$ is a of the Split Completion problem.
Assume then that $\splittance(G') \leq k$.
Now we make a query $\oper{findObstruction}()$ on $\nsample$.
If $\oper{findObstruction}()$ reports the answer , then $G'$ is a split graph, and in particular, $(G', k)$ is a of the Split Completion problem.
Otherwise, $\oper{findObstruction}()$ returns a subset $U \subseteq V(G')$ such that $G'[U]$ is an obstruction.

Since in the Split Completion problem we are only allowed to insert new edges, we know that in order to make the graph $G'$ split, we need to insert to it at least one non-edge of $G'[U]$. Note that $G'[U]$ has at most $5$ non-edges (in the case of $C_5$).
We branch into all these possibilities, and when considering an insertion of a non-edge $e \in \overline{E}(G'[U])$, we temporarily insert it to the graph $G'$ (by doing appropriate call to the structure $\nsample$), and proceed recursively, where at each step either we obtain that the current graph is split, or $\nsample$ localizes an obstruction which needs to be eliminated from the graph by subsequent insertions.
Since we are allowed to insert at most $k$ edges to $G'$, we can exit branches of depth larger than $k$, and thus the total number of nodes in the search tree (and also the number of calls to $\nsample$) is bounded by $\Oh(5^k)$.

The correctness of this recursive procedure is straightforward under an assumption that all the calls to $\nsample$ return correct answers.
The amortized running time of the entire update is bounded by

\[
\Oh(5^k) \cdot \Ohtilde(k^{\Oh(1)} \cdot d'^2) = \Ohtilde(5^k \cdot k^{\Oh(1)} \cdot d^2)
\]

By the union bound, the probability of reporting an incorrect answer is at most

\[
\Oh\left(\frac{5^k}{n^{d'-c}}\right) = \Oh\left(\frac{5^k}{n^{k + d+c-c}}\right) \subseteq \Oh\left(\frac{1}{n^d}\right).
\]

Finally, let us remark that this is in fact a Monte Carlo algorithm: once our procedure finds a set of edges $F \subseteq \binom{V(G)}{2}$ to be inserted, we can verify deterministically whether $G'' = (V(G'), E(G') \cup F)$ is a split graph by temporarily inserting edges of $F$ to $\nsample$, checking whether $\splittance(G'') = 0$, and removing edges of $F$ from $\nsample$ afterwards.

We remark that the proof of <ref> can be trivially adjusted to handle the Split Edge Deletion problem instead: once an obstruction is located we branch into at most five ways of breaking it by an edge deletion instead of an edge insertion. The running time guarantees remain the same.

§ CONCLUSIONS

In this work we gave a dynamic data structure for the Split Completion problem with amortized update time $2^{\Oh(k)}\cdot (d\log n)^{\Oh(1)}$, where the error probability is bounded by $1-\Oh(n^{-d})$. Two natural questions that one may ask are the following:

* Can the data structure be derandomized? The usage of color coding in <ref> can be derandomized in a standard way using universal hash families. However, we also apply randomization in a non-trivial way in the proof of <ref>, and this application we do not know how to derandomize.

* A careful analysis of our arguments reveals that the polylogarithmic factor in the obtained update time is $(\log n)^4$.
Can this be improved? Could one expect update time independent of $n$, that is, of the form $f(k)$ for some computable function $f$?

As for amortization, the only place where amortization comes into play is the proof of <ref>: the updates are queued during the time when the splittance is above $k$, and then they get executed all at once only when the splittance becomes bounded by $k$. Consequently, our data structure actually executes updates in worst-case time $2^{\Oh(k)}\cdot (d\log n)^{\Oh(1)}$ under the assumption that the splittance is never larger than $k$. We believe that relying on amortization to handle the general setting without any promises is a rather small hindrance. Consequently, while the question about removing amortization is definitely relevant, we consider it less interesting than the two questions stated above.

In a wider context, our result together with the previous work of Iwata and Oka [23] and of Alman et al. [1] suggest that investigating parameterized dynamic data structures for graph modification problems might turn out to be a particularly fruitful direction. Concrete problems that we suspect to be amenable to dynamization are Planarization [30, 24] and various graph modification problems connected to chordal graphs and their subclasses such as interval, proper interval, trivially perfect, or threshold graphs; these were studied extensively, see e.g. [3, 4, 5, 6, 7, 11, 12, 15, 16, 25, 29, 33, 34].

[1]
Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams.
Dynamic parameterized problems and algorithms.
ACM Trans. Algorithms, 16(4):45:1–45:46, 2020.

[2]
Noga Alon, Raphael Yuster, and Uri Zwick.
J. ACM, 42(4):844–856, 1995.

[3]
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michał Pilipczuk.
A subexponential parameterized algorithm for Proper Interval
SIAM J. Discret. Math., 29(4):1961–1987, 2015.

[4]
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michał Pilipczuk.
Subexponential parameterized algorithm for Interval Completion.
ACM Trans. Algorithms, 14(3):35:1–35:62, 2018.

[5]
Yixin Cao.
Linear recognition of almost interval graphs.
In 27th Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA 2016, pages 1096–1115. SIAM, 2016.

[6]
Yixin Cao.
Unit interval editing is fixed-parameter tractable.
Inf. Comput., 253:109–126, 2017.

[7]
Yixin Cao and Dániel Marx.
Chordal editing is fixed-parameter tractable.
Algorithmica, 75(1):118–137, 2016.

[8]
Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny
Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk, Manuel
Sorge, Bartłomiej Wróblewski, and Anna Zych-Pawlewicz.
Efficient fully dynamic elimination forests with applications to
detecting long paths and cycles.
In 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA
2021, pages 796–809. SIAM, 2021.

[9]
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel
Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.
Parameterized Algorithms.
Springer, 2015.

[10]
Marek Cygan and Marcin Pilipczuk.
Split Vertex Deletion meets Vertex Cover: New fixed-parameter
and exact exponential-time algorithms.
Inf. Process. Lett., 113(5-6):179–182, 2013.

[11]
Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, and Yngve
Exploring the subexponential complexity of completion problems.
ACM Trans. Comput. Theory, 7(4):14:1–14:38, 2015.

[12]
Pål Grønås Drange and Michal Pilipczuk.
A polynomial kernel for Trivially Perfect Editing.
Algorithmica, 80(12):3481–3524, 2018.

[13]
Zdenek Dvořák, Martin Kupec, and Vojtech Tůma.
A dynamic data structure for MSO properties in graphs with bounded
In 22th Annual European Symposium on Algorithms, ESA 2014,
volume 8737 of Lecture Notes in Computer Science, pages 334–345.
Springer, 2014.

[14]
Zdenek Dvořák and Vojtech Tůma.
A dynamic data structure for counting subgraphs in sparse graphs.
In 13th International Symposium on Algorithms and Data
Structures, WADS 2013, volume 8037 of Lecture Notes in Computer
Science, pages 304–315. Springer, 2013.

[15]
Fedor V. Fomin, Saket Saurabh, and Yngve Villanger.
A polynomial kernel for Proper Interval Vertex Deletion.
SIAM J. Discret. Math., 27(4):1964–1976, 2013.

[16]
Fedor V. Fomin and Yngve Villanger.
Subexponential parameterized algorithm for Minimum Fill-in.
SIAM J. Comput., 42(6):2197–2216, 2013.

[17]
Stéphane Földes and Peter L. Hammer.
Split graphs.
In Eighth Southeastern Conference on Combinatorics, Graph Theory
and Computing, volume XIX of Congressus Numerantium, pages 311–315,

[18]
Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan,
Ashutosh Rai, and M. S. Ramanujan.
Faster parameterized algorithms for deletion to split graphs.
Algorithmica, 71(4):989–1006, 2015.

[19]
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk, Gabriele Puppis, and
Cristian Riveros.
Dynamic data structures for timed automata acceptance.
Algorithmica, 84(11):3223–3245, 2022.

[20]
Peter L. Hammer and Bruno Simeone.
The splittance of a graph.
Combinatorica, 1:275–284, 1981.

[21]
Pinar Heggernes and Federico Mancini.
Dynamically maintaining split graphs.
Discret. Appl. Math., 157(9):2057–2069, 2009.

[22]
Louis Ibarra.
Fully dynamic algorithms for chordal graphs and split graphs.
ACM Trans. Algorithms, 4(4):40:1–40:20, 2008.

[23]
Yoichi Iwata and Keigo Oka.
Fast dynamic graph algorithms for parameterized problems.
In 14th Scandinavian Symposium and Workshops on Algorithm
Theory, SWAT 2014, volume 8503 of Lecture Notes in Computer Science,
pages 241–252. Springer, 2014.

[24]
Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh.
A near-optimal planarization algorithm.
In 25th Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA 2014, pages 1802–1811. SIAM, 2014.

[25]
Yuping Ke, Yixin Cao, Xiating Ouyang, Wenjun Li, and Jianxin Wang.
Unit interval vertex deletion: Fewer vertices are relevant.
J. Comput. Syst. Sci., 95:109–121, 2018.

[26]
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, and
Marek Sokołowski.
Dynamic treewidth.
CoRR, abs/2304.01744, 2023.
To appear in the proceedings of FOCS 2023.

[27]
John M. Lewis and Mihalis Yannakakis.
The node-deletion problem for hereditary properties is NP-complete.
J. Comput. Syst. Sci., 20(2):219–230, 1980.

[28]
Konrad Majewski, Michał Pilipczuk, and Marek Sokołowski.
Maintaining CMSO$_2$ properties on dynamic structures with bounded
feedback vertex number.
In 40th International Symposium on Theoretical Aspects of
Computer Science, STACS 2023, volume 254 of LIPIcs, pages
46:1–46:13. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2023.

[29]
Dániel Marx.
Chordal deletion is fixed-parameter tractable.
Algorithmica, 57(4):747–768, 2010.

[30]
Dániel Marx and Ildikó Schlotter.
Obtaining a planar graph by vertex deletion.
Algorithmica, 62(3-4):807–822, 2012.

[31]
Assaf Natanzon, Ron Shamir, and Roded Sharan.
Complexity classification of some edge modification problems.
Discret. Appl. Math., 113(1):109–128, 2001.

[32]
Jędrzęj Olkowski, Michał Pilipczuk, Mateusz Rychlicki, Karol
Węgrzycki, and Anna Zych-Pawlewicz.
Dynamic data structures for parameterized string problems.
In 40th International Symposium on Theoretical Aspects of
Computer Science, STACS 2023, volume 254 of LIPIcs, pages
50:1–50:22. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2023.

[33]
Pim van 't Hof and Yngve Villanger.
Proper interval vertex deletion.
Algorithmica, 65(4):845–867, 2013.

[34]
Yngve Villanger, Pinar Heggernes, Christophe Paul, and Jan Arne Telle.
Interval Completion is fixed parameter tractable.
SIAM J. Comput., 38(5):2007–2020, 2009.

§ PROOF OF <REF>

§ MISSING PROOFS FROM <REF>

§ MISSING PROOFS FROM <REF>

Here, we fill in the missing details from the proof of <ref>.

§ MISSING PROOFS FROM <REF>

Here, we fill in the missing parts from the proof of <ref>.

Localizing $2K_2$.

We continue the case analysis started in the proof of <ref>.

Localizing $C_5$.

§ BRANCHING

We are ready to prove our main result, <ref>, which we recall for convenience.

Our main data structure stores:

* the values of $k$ and $d$;

* an instance $\nsample[n, k, d']$ of the data structure
from <ref>, extended with a method
from <ref>, for $d' \coloneqq d+k+c$, where $c$ is
the constant from <ref>.

We set the values of $k$ and $d$ for the entire run, and initialize the inner data structure $\nsample$ with corresponding values.
The total running time of this phase is

\[
\Ohtilde(k \cdot d'^2 \cdot n) = \Ohtilde(k^{\Oh(1)} \cdot d^2 \cdot n).
\]

Consider an edge update $e = uv$ (that is, we either insert $e$ to the graph $G$, or remove it).
First, we pass this to the structure $\nsample$.
Let $G'$ denote the newly obtained graph.
Now, we should update the answer to our query: we need to determine whether one can insert at most $k$ edges to $G'$ so that the resulting graph is split.

If $\splittance(G') > k$, then we know that $(G',k)$ is a of the Split Completion problem.
Assume then that $\splittance(G') \leq k$.
Now we make a query $\oper{findObstruction}()$ on $\nsample$.
If $\oper{findObstruction}()$ reports the answer , then $G'$ is a split graph, and in particular, $(G', k)$ is a of the Split Completion problem.
Otherwise, $\oper{findObstruction}()$ returns a subset $U \subseteq V(G')$ such that $G'[U]$ is an obstruction.

Since in the Split Completion problem we are only allowed to insert new edges, we know that in order to make the graph $G'$ split, we need to insert to it at least one non-edge of $G'[U]$. Note that $G'[U]$ has at most $5$ non-edges (in the case of $C_5$).
We branch into all these possibilities, and when considering an insertion of a non-edge $e \in \overline{E}(G'[U])$, we temporarily insert it to the graph $G'$ (by doing appropriate call to the structure $\nsample$), and proceed recursively, where at each step either we obtain that the current graph is split, or $\nsample$ localizes an obstruction which needs to be eliminated from the graph by subsequent insertions.
Since we are allowed to insert at most $k$ edges to $G'$, we can exit branches of depth larger than $k$, and thus the total number of nodes in the search tree (and also the number of calls to $\nsample$) is bounded by $\Oh(5^k)$.

The correctness of this recursive procedure is straightforward under an assumption that all the calls to $\nsample$ return correct answers.
The amortized running time of the entire update is bounded by

\[
\Oh(5^k) \cdot \Ohtilde(k^{\Oh(1)} \cdot d'^2) = \Ohtilde(5^k \cdot k^{\Oh(1)} \cdot d^2)
\]

By the union bound, the probability of reporting an incorrect answer is at most

\[
\Oh\left(\frac{5^k}{n^{d'-c}}\right) = \Oh\left(\frac{5^k}{n^{k + d+c-c}}\right) \subseteq \Oh\left(\frac{1}{n^d}\right).
\]

Finally, let us remark that this is in fact a Monte Carlo algorithm: once our procedure finds a set of edges $F \subseteq \binom{V(G)}{2}$ to be inserted, we can verify deterministically whether $G'' = (V(G'), E(G') \cup F)$ is a split graph by temporarily inserting edges of $F$ to $\nsample$, checking whether $\splittance(G'') = 0$, and removing edges of $F$ from $\nsample$ afterwards.

We remark that the proof of <ref> can be trivially adjusted to handle the Split Edge Deletion problem instead: once an obstruction is located we branch into at most five ways of breaking it by an edge deletion instead of an edge insertion. The running time guarantees remain the same.