\section{Postponing insertions and the main results}\label{sec:kpath}

In this section we combine the results from the previous section, in particular Lemmas~\ref{lem:kpath-bnd-td} and~\ref{lem:kcycle-restricted}, with the technique of postponing insertions in order to prove our main results: data structure for the
dynamic \LPath and \LCycle problems. 


\paragraph*{Postponing insertions.}
We now present a generic technique for turning data structures working under structural restrictions into general ones, at the cost of introducing amortization and using a dictionary.
As we mentioned, the idea is not new: it was used by Eppstein et al.~\cite{EppsteinGIS96} for planarity testing.
We formulate the technique in an abstract way, because apart from being useful in our setting, it also applies to some other problems discussed by Alman et al.~\cite{AlmanMW17}.

Suppose $\Univ$ is some universe. A family of subsets $\Ff\subseteq 2^{\Univ}$ is {\em{downward closed}} if for all $E \subseteq F\subseteq \Univ$, $F\in \Ff$ entails $E\in \Ff$.
A  data structure $\Dt$  
{\em{strongly supports $\Ff$ membership}} if $\Dt$ maintains a subset $X$ of $\Univ$ under $\ins(x)$ and $\rem(x)$ operations (just as in the dictionary, but without the associated records), 
and in addition to this it offers a boolean query $\member()$ that checks whether $X\in \Ff$.
We also consider the following weaker notion: a  data structure $\Dt$ {\em{weakly supports $\Ff$ membership}} if, again, it implements $\ins(x)$ and $\rem(x)$ operations on a dynamic subset $X\subseteq \Univ$, 
but works under the restriction that we always have $X\in \Ff$. Whenever performing an $\ins(\cdot)$ operation would violate the invariant $X\in \Ff$,
the data structure should detect this and refuse to carry out the operation.

The following lemma shows that data structures supporting weak $\Ff$ membership can be turned into ones supporting strong $\Ff$ membership at the cost of introducing amortization and allowing access to a dictionary $\Lt$ on $\Univ$.
The proof essentially repeats the same argument as~\cite[Corollary~1]{EppsteinGIS96}.

\begin{lemma}\label{lem:queue}
Suppose $\Univ$ is a universe and we have access to a dictionary $\Lt$ on $\Univ$.
Let $\Ff\subseteq 2^{\Univ}$ be downward closed and
suppose there is a  data structure $\Dt$ that weakly supports $\Ff$ membership.
Then there is a data structure $\Dt'$ that strongly supports $\Ff$ membership, where each $\member(\cdot)$ query takes $\Oh(1)$ time 
and each update uses amortized $\Oh(1)$ time and amortized $\Oh(1)$ calls to operations on $\Lt$ and~$\Dt$.
\end{lemma}
\begin{proof}
  $\Dt'$ maintains (a copy of) $\Dt$ and an additional queue $Q$, in which $\Dt'$ stores elements whose insertion is {\em{postponed}}.
 We will denote the set stored in $\Dt'$ by $X$, while the sets stored in (the copy of) $\Dt$ and in $Q$ are $X_{\Dt}$ and $X_{Q}$, respectively.
 We maintain the invariant that $X$ is the disjoint union of $X_{\Dt}$ and $X_Q$.
 
 The queue $Q$ is implemented as a doubly linked list. 
 In addition to the above, we maintain a dictionary $\Lt$ that stores $X$.
 In $\Lt$, the record associated with each $x\in X$ is either a pointer that points to the list element representing $x$ in $Q$, in case $x\in X_Q$, or a marker $\bot$ in case $x\in X_{\Dt}$. 
 Thus, given $x\in \Univ$, we may use the $\lookup(x)$ operation in $\Lt$ to check whether $x$ belongs to $X_{\Dt}$ or $X_Q$ and, if the latter holds, access the corresponding list element on $Q$.
 In the following, whenever we insert an element to $\Dt$ or $Q$, we insert it to $\Lt$ as well (possibly together with a pointer to list element). Same for removals.
 
 We maintain the following invariant:
 \begin{quote}
  $(\star)$\quad If $Q$ is non-empty and $x$ is the front element of $Q$, then $X_{\Dt}\cup \{ x \}\notin \Ff$.
 \end{quote}
 Note that since $\Dt$ stores $X_{\Dt}$, we obviously have $X_{\Dt}\in \Ff$. Hence if $Q$ is empty, then $X_{\Dt}=X\in \Ff$.
 On the other hand, if $Q$ is non-empty, then invariant~$(\star)$ together with upward-closedness of $\Ff$ implies $X\notin \Ff$.
 Thus, the $\member()$ query amounts to checking whether $Q$ is empty, which can be done in constant time.
 
 We now explain how updating $\Dt'$ works, starting with the $\ins(x)$ operation on $\Dt'$.
 By applying $\lookup(x)$ in $\Lt$, we may further assume that $x\notin X$.
 If $Q$ is not empty, then we push $x$ to the back of $Q$.
 Otherwise, we try to add $x$ to $X_{\Dt}$ by applying $\ins(x)$ on $\Dt$. 
 If this operation succeeds (i.e. $X_{\Dt}\cup \{x\}\in \Ff$), then there is nothing more to do. 
 Otherwise, if $\Dt$ refuses to insert the element $x$, then we have a situation where $X_Q=\emptyset$, $X_{\Dt} \in \Ff$, but $X_{\Dt} \cup \{x\} \notin \Ff$.
 Hence, we push $x$ to the back of $Q$; note that invariant~$(\star)$ is thus satisfied, as $x$ becomes the only element in $Q$.
 This concludes the implementation of $\ins(x)$ in $\Dt'$.
  
 We now move to the $\rem(x)$ operation in $\Dt'$.
 First, we apply $\lookup(x)$ operation offered by $\Lt$. If $x \notin X$, then there is nothing to do.
 Otherwise, we have two cases: either $x\in X_{\Dt}$ or $x\in X_Q$.
 
 If $x\in X_Q$, then we remove $x$ from $Q$; recall here that $\lookup(x)$ provided us with the pointer to the corresponding list element, so this can be done in constant time.
 However, at this point invariant~$(\star)$ might have ceased to hold.
 Hence, we apply the $\flush()$ operation, defined as follows. 
 We iteratively take the front element $x$ from $Q$ and try to insert it to $\Dt$ by applying $\ins(x)$ on $\Dt$.
 If $x$ gets successfully inserted into $\Dt$, we remove $x$ from $Q$ and proceed with the iteration.
 Otherwise, if $\Dt$ refuses to insert $x$, we break the iteration.
 Thus, the iteration stops when either~$Q$ becomes empty, or the first element $x$ of $Q$ satisfies $X_{\Dt}\cup \{x\}\notin \Ff$. So invariant~$(\star)$ is restored.
 
 We are left with the case when $x\in X_{\Dt}$. In this case we remove $x$ from $X_{\Dt}$ by calling $\rem(x)$ on~$\Dt$.
 Again, as this might have broken invariant~$(\star)$; we restore it by calling the $\flush()$ operation.
 This concludes the implementation of $\rem(x)$ in $\Dt'$.
 
 We are left with discussing the complexity.
 Observe that each operation $\ins(\cdot)$ uses $\Oh(1)$ operations on $\Dt$ and $\Oh(1)$ operations on $\Lt$.
 Similarly for $\rem(\cdot)$, except that the application of $\flush()$ may perform an unbounded number of moves of elements from $X_Q$ to $X_{\Dt}$, each involving $\Oh(1)$ operations on $\Dt$ and $\Lt$.
 However, each element inserted to $\Dt'$ is moved from $X_Q$ to $X_{\Dt}$ by $\flush()$ at most once, so the operations used for successful moves from $X_Q$ to $X_{\Dt}$ can be charged to $\ins(\cdot)$ previously applied on $\Dt'$.
 It follows that in the amortized sense, each operation in $\Dt'$ uses $\Oh(1)$ time and $\Oh(1)$ operations on $\Dt$ and $\Lt$.
\end{proof}

We remark that Lemma~\ref{lem:queue} can be applied to two problems considered by Alman et al.~\cite{AlmanMW17}: {\sc{Edge Clique Cover}} and {\sc{Point Line Cover}}.
In the first problem, given a graph $G$ and parameter $k$, we ask whether the edges of the $G$ can be covered by at most $k$ cliques in $G$.
In the second problem, given a set $S$ of points in the plane and parameter $k$, we ask whether all these points can be covered using at most $k$ lines.
Alman et al.~\cite{AlmanMW17} gave data structures for the dynamic variants of these problems, however working under the promise that there is always a solution of size at most $g(k)$.
They achieved: update time $\Oh(4^{g(k)})$ and query time $2^{2^{\Oh(k)}}+\Oh(16^{g(k)})$ for {\sc{Edge Clique Cover}}; and
update time $\Oh(g(k)^3)$ and query time $\Oh(g(k)^{g(k)+2})$ for {\sc{Point Line Cover}}.
It was left open whether the assumption about the promise can be lifted.
By combining the data structures of Alman et al.~\cite{AlmanMW17} for $g(k)=k+1$ with Lemma~\ref{lem:queue}, we obtain data structures that achieve:
amortized update time $\Oh(4^k)$ and query time $2^{2^{\Oh(k)}}$ for {\sc{Edge Clique Cover}}; and amortized update time $\Oh(k^3)$ and query time $2^{\Oh(k\log k)}$ for {\sc{Point Line Cover}}.
This assumes access to a dictionary on the edges of the graph in the case of {\sc{Edge Clique Cover}}, and on the point set in the case of {\sc{Point Line Cover}}.


\newcommand{\Qq}{\mathcal{Q}}


\paragraph*{Deriving the results.} We now gather all our tools to prove the main results of this work.

\begin{theorem}[Main result for \LPath]\label{thm:main-formal}
 Let $k$ be a fixed parameter. Suppose we are given a dynamic graph $G$ on $n$ vertices, updated by edge insertions and removals, and we have access to a dictionary on the edges of $G$ where the dictionary operations have amortized running time bounded by $\tdict$. 
 Then there is a data structure that, under such updates,
 maintains whether $G$ contains a simple path on $k$ vertices with amortized update time $2^{\Oh(k^2)}+\Oh(\tdict)$. The data structure uses $(n \cdot 2^{\Oh(k \log k)} + \mdict)$ memory.
 The initialization of the data structure for an edgeless graph on $n$ vertices takes $\Oh(n)$ time.
\end{theorem}
\begin{proof}
 Let $V$ be the invariant vertex set of $G$ and let $\Univ\coloneqq \binom{V}{2}$.
 We note that a dynamic graph with vertex set $V$ can be equivalently treated as a dynamic subset of $\Univ$.
 Let then $\Qq_k\subseteq 2^{\Univ}$ comprise all sets $F\subseteq \Univ$ such that the graph $(V,F)$ does {\em{not}} contain a simple path on $k$ vertices.
 Similarly, let $\Tt_k\subseteq 2^{\Univ}$ comprise all sets $F\subseteq \Univ$ such that the graph $(V,F)$ has treedepth smaller than $k$.
 Note that both $\Qq_k$ and $\Tt_k$ are downward closed and, by Lemma~\ref{lem:path-td}, we have $\Qq_k\subseteq \Tt_k$.
  
 By Lemma~\ref{lem:kpath-bnd-td},
 there is a data structure $\Dt$ that weakly supports $\Tt_k$ membership with update time $2^{\Oh(k^2)}$, and moreover offers $\Qq_k$ membership queries in constant time.
 By Lemma~\ref{lem:queue}, we can now turn $\Dt$ into a data structure $\Dt'$ that strongly supports $\Tt_k$ membership, where each update takes amortized time $2^{\Oh(k^2)}$ and uses amortized $\Oh(1)$ operations on the dictionary over $\Univ$; the latter ones take amortized $\Oh(\tdict)$ time.
 Now, we can easily implement $\Qq_k$ membership queries in $\Dt'$ as follows:
 if the currently maintained set $X\subseteq \Univ$ does not belong to $\Tt_k$, then it also does not belong to $\Qq_k$, 
 and otherwise we may simply query the data structure $\Dt$ that is maintained within $\Dt'$ (see the proof of Lemma~\ref{lem:queue}).
 Finally, observe that strongly supporting $\Qq_k$ membership is equivalent to the requirement requested in the theorem statement.
\end{proof}

The same reasoning as presented in the proof of Theorem~\ref{thm:main-formal}, but with Lemma~\ref{lem:kpath-bnd-td} replaced with Lemma~\ref{lem:kcycle-restricted}, yields the following. We note here that as mentioned in Section~\ref{sec:prelims}, if in Lemma~\ref{lem:kcycle-restricted} we assume {\em{amortized}} time $\tdict$ per dictionary operation instead of worst-case, then we obtain the same running time guarantees, but for amortized complexity.

\begin{theorem}[Main result for \LCycle]\label{thm:main-formal-cycle}
 Let $k$ be a fixed parameter. Suppose we are given a dynamic graph $G$ on $n$ vertices, updated by edge insertions and removals, and we have access to a dictionary on the edges of $G$, which uses $\mdict$ memory and where dictionary operations have amortized bounded by $\tdict$. 
 Then there is a data structure that, under such updates,
 maintains whether $G$ contains a simple cycle on at least $k$ vertices with amortized update time $2^{\Oh(k^4)}+k^{\Oh(k^2)}\tdict+\Oh(k\log n)$. The data structure takes $(n \cdot 2^{\Oh(k^2 \log k)}+ \mdict)$ memory.
 The initialization of the data structure for an edgeless graph on $n$ vertices takes $\Oh(n)$ time.
\end{theorem}

Theorems~\ref{thm:main-formal} and~\ref{thm:main-formal-cycle} add up to a proof of Theorem~\ref{thm:main-intro}.
{"config": "arxiv", "file": "2006.00571/kpath.tex"}