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)^{\mathcal{O}(1)}$, and the amortized time complexity of an update is $5^k \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$. The answer provided by the data structure is correct with probability $1-\mathcal{O}(n^{-d})$.

We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most $6 k+5$ under the promise that the treewidth of G never grows above k. The amortized update time is $\mathcal{O}_{k}\left(2^{\sqrt{\log n} \log \log n}\right)$, where n is the vertex count of G and the $\mathcal{O}_{k}(\cdot)$ notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle’s Theorem: for any fixed property $\varphi$ expressible in the CMSO2logic, the data structure can maintain whether G satisfies $\varphi$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].

Let 𝜑 be a sentence of CMSO₂ (monadic second-order logic with quantification over edge subsets and counting modular predicates) over the signature of graphs. We present a dynamic data structure that for a given graph G that is updated by edge insertions and edge deletions, maintains whether 𝜑 is satisfied in G. The data structure is required to correctly report the outcome only when the feedback vertex number of G does not exceed a fixed constant k, otherwise it reports that the feedback vertex number is too large. With this assumption, we guarantee amortized update time O_{𝜑,k}(log n). By combining this result with a classic theorem of Erdős and Pósa, we give a fully dynamic data structure that maintains whether a graph contains a packing of k vertex-disjoint cycles with amortized update time O_k(log n). Our data structure also works in a larger generality of relational structures over binary signatures.

We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw $S_{t,t,t}$ as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time $2^{\mathcal{O}(\sqrt{n}\log n)}$ and a quasipolynomial-time approximation scheme with improved running time $2^{\mathcal{O}(\varepsilon^{-1} \log^{5} n)}$. The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in $P_t$-free graphs, ensures that given an $n$-vertex $P_t$-free graph, in polynomial time we can find a set $P$ of at most $t-1$ vertices, such that every connected component of $G-N[P]$ has at most $n/2$ vertices. Our main technical contribution is an analog of this result for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, in polynomial time we can find a set $P$ of $\mathcal{O}(t \log n)$ vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of $G-N[P]$ such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most $n/2$ vertices.

Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algorithm running in time 𝒪^*(2ⁿ) developed almost 60 years ago by Bellman, Held and Karp, is still the state of the art for both of these problems. In this work we focus on sparse digraphs. First, we recall known approaches for Undirected Hamiltonicity and TSP in sparse graphs and we analyse their consequences for Directed Hamiltonicity and ATSP in sparse digraphs, either by adapting the algorithm, or by using reductions. In this way, we get a number of running time upper bounds for a few classes of sparse digraphs, including 𝒪^*(2^(n/3)) for digraphs with both out- and indegree bounded by 2, and 𝒪^*(3^(n/2)) for digraphs with outdegree bounded by 3. Our main results are focused on digraphs of bounded average outdegree d. The baseline for ATSP here is a simple enumeration of cycle covers which can be done in time bounded by 𝒪^*(μ(d)ⁿ) for a function μ(d) ≤ (⌈d⌉!)^(1/⌈d⌉). One can also observe that Directed Hamiltonicity can be solved in randomized time 𝒪^*((2-2^(-d))ⁿ) and polynomial space, by adapting a recent result of Björklund [ISAAC 2018] stated originally for Undirected Hamiltonicity in sparse bipartite graphs. We present two new deterministic algorithms for ATSP: the first running in time 𝒪(2^(0.441(d-1)n)) and polynomial space, and the second in exponential space with running time of 𝒪^*(τ(d)^(n/2)) for a function τ(d) ≤ d.