Fix a parameter k ∈ ℕ. We give dynamic data structures that for a fully dynamic undirected graph G, updated over time by edge insertions and edge deletions, can answer the following queries: - Long (u,v)-path: Given u,v ∈ V(G), is there a path from u to v of length at least k? - Long (u,v)-detour: Given u,v ∈ V(G), is there a path from u to v of length at least dist_G(u,v)+k? - Even/odd (u,v)-path: Given u,v ∈ V(G), is there a path from u to v of even/odd length? The amortized time of executing an update or answering a query is 2^𝒪(k³) log n + 𝒪(log² n log² log n) in the first two cases, and 𝒪(log² n log² log n) in the last, where n is the number of vertices of G. The first result is in sharp contrast with known conditional lower bounds for reporting paths of length at most k. Specifically, there is no data structure supporting queries about (u,v)-paths of length at most two in time n^o(1) unless the Triangle Conjecture fails. Our main technical contribution is a mechanism of "delayed edge insertion" that works locally on the level of biconnected components.

We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining 0 on the empty set. For a connectivity function f on an n-element set V and an integer k ≥ 0, we show that the family of all sets X ⊆ V with f(X) = k admits a polynomial-size representation: it can be described by a list of at most O(n^{4k}) items, each consisting of a set to be included, another set to be excluded, and a partition of remaining elements, such that the union of some members of the partition and the set to be included are precisely all sets X with f(X) = k. We also give an algorithm that constructs this representation in time O(n^{2k+7}γ+n^{2k+8}+n^{4k+2}), where γ is the oracle time to evaluate f. This generalizes the low rank structure theorem of Bojańczyk, Pilipczuk, Przybyszewski, Sokołowski, and Stamoulis [Low rank MSO, LICS 2026] on cut-rank functions on graphs to general connectivity functions. As an application, for fixed k, we obtain a polynomial-time algorithm for finding a set A with f(A) = k and a prescribed cardinality constraint on A.

We study two fundamental decremental dynamic graph problems. In both problems, we need to maintain a vertex-weighted forest of size n under edge deletions, weight updates, and a certain information-retrieval query. Both problems can be solved in 𝒪(log n) time per update/query using standard dynamic forest data structures like top trees - even if additionally edge insertions are allowed. We investigate whether the deletion-only problem can be solved faster. First, we consider tree-sum queries, where we ask for the sum of vertex weights in one of the connected components (i.e., trees) in the forest. We give a data structure with 𝒪(n) preprocessing time and 𝒪(log^* n) time per operation, based on a micro-macro tree decomposition (Alstrup et al., 1997). If the forest is unweighted (i.e., all weights are 1 and cannot be changed), then the operation time can be improved to 𝒪(1). Additionally, we give an asymptotically universally optimal algorithm. More specifically, our algorithm works in the group model, and processes m operations on an initial forest F in running time 𝒪(OPT(F, m)). Here OPT(F, m) is the number of weight additions and subtractions that a best possible algorithm performs to handle a worst-case instance for a fixed initial forest F and a fixed number m of operations. We achieve this with a combination of the aforementioned decomposition technique, precomputation of optimal data structures for very small instances, and some insights into the behavior of OPT. Note that even the worst-case complexity of this algorithm remains unknown to us. Second, we consider subtree-sum queries. Here, the forest is rooted, and a query subtree-sum(v) returns the sum of weights in the subtree rooted at v. An easy reduction from the well-known prefix sum problem shows that the general, weighted version of the problem requires Θ(n log n) time for n operations. Interestingly, we prove that the Ω(n log n) complexity lower bound still holds even if weight updates are disallowed. On the other hand, we show that the unweighted version can be solved with 𝒪((log n)/(log log n)) time per operation, and this is tight.

We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restricted to vertex sets of bounded cutrank. We prove the following statements about the expressive power of low rank MSO. - Over any class of graphs that is weakly sparse, low rank MSO has the same expressive power as separator logic. This equivalence does not hold over all graphs. - Over any class of graphs that has bounded VC dimension, low rank MSO has the same expressive power as flip-connectivity logic. This equivalence does not hold over all graphs. - Over all graphs, low rank MSO has the same expressive power as flip-reachability logic. Here, separator logic is an extension of first-order logic by basic predicates for checking connectivity, which was proposed by Bojańczyk [ArXiv 2107.13953] and by Schirrmacher, Siebertz, and Vigny [ACM ToCL 2023]. Flip-connectivity logic and flip-reachability logic are analogues of separator logic suited for non-sparse graphs, which we propose in this work. In particular, the last statement above implies that every property of undirected graphs expressible in low rank MSO can be decided in polynomial time.

In this paper, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP can be solved within \(\tilde O(m+n^{2-\epsilon})\) work and \(\tilde O(n^{1-\epsilon})\) depth for some positive \(\epsilon \lt 0\). In particular, for dense graphs with non-negative real weights, we provide the first nearly work-efficient strongly polynomial algorithm with sublinear depth.

Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a 2^{O(k²)} n-time exact algorithm and a polynomial-time O(OPT log^{3/2} OPT)-approximation algorithm, where the former algorithm returns an elimination forest of height k (witnessing that treedepth is at most k) for the n-vertex input graph G, or correctly reports that G has treedepth larger than k, and OPT is the actual value of the treedepth. On the complexity side, exactly computing treedepth is NP-complete, but the known reductions do not rule out a polynomial-time approximation scheme (PTAS), and under the Exponential Time Hypothesis (ETH) only exclude a running time of 2^o(√n) for exact algorithms. We show that 1.0003-approximating Treedepth is NP-hard, and that exactly computing the treedepth of an n-vertex graph requires time 2^Ω(n), unless the ETH fails. We further derive that there exist absolute constants δ, c > 0 such that any (1+δ)-approximation algorithm requires time 2^Ω(n/log^c n). We do so via a simple direct reduction from Satisfiability to Treedepth, inspired by a reduction recently designed for Treewidth [STOC '25].

We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph; i.e. the vertices whose removal would disconnect the graph. Our data structure supports insertion and deletion of edges, as well as queries to whether a pair of connected vertices are either biconnected, or can be separated by a cutvertex, and in the latter case we support access to separating cutvertices. All update operations are supported in amortized O(log2 n log2 log n) time, and queries take worst-case O(log n log2 log n) time. Note that these time bounds match the current best for deterministic dynamic connectivity up to log log n factors. The previous best algorithm for biconnectivity had an update time of O(logλ n log log n) by Thorup [STOC'00], based on the O(logλ μ n) data structure by Holm, de Lichtenberg, and Thorup [STOC'98]. We obtain our improved running time by a series of reductions from the original problem into well-defined data structure problems. While we do indeed apply the well-known techniques for improving running time of two-edge connectivity [STOC'00, SODA'18], surprisingly, these techniques alone do not lead to an update time of Õ(log³ n), let alone the Õ(log2 n) we give as a final result. Our contributions include a formally defined transient expose operation, which can be thought of as a cheaper read-only expose operation on a top tree. For each vertex in the graph, we maintain a data structure over its neighbors, and in this data structure we apply biasing (twice) to save an Õ(log n) factor (twice, so two Õ(log n) factors). One of these biasing techniques is a new, simple biased disjoint sets data structure, which may be of independent interest. Moreover, in this neighborhood data structure, we facilitate that the vertex can select two VIP neighbors that get special treatment, corresponding to its potentially two neighbors on an exposed path, improving an otherwise log n-time operation down to constant time. It is this combination of VIP neighbors with the transient expose operation that saves an Õ(log n)-factor from another bottleneck. Combining these technical contributions with the well-known techniques for two-edge connectivity [STOC'00, SODA'18], we obtain the desired update times of O(log2 n log2 log n). The near-linear query time follows directly from the usage of transient expose.

It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, Siebertz, STOC 2014]. However, the dependency on the formula size is non-elementary, and in fact, this is unavoidable even for the class of all trees [Frick and Grohe, LICS 2002]. On the other hand, it is known that the dependency is elementary for classes of bounded degree [Frick and Grohe, LICS 2002] as well as for classes of bounded pathwidth [Lampis, ICALP 2023]. In this paper we generalise these results and almost completely characterise subgraph-closed graph classes for which the model checking problem is fixed-parameter tractable with an elementary dependency on the formula size. Those are the graph classes for which there exists a number d such that for every r, some tree of depth d and size bounded by an elementary function of r is avoided as an (≤r)-subdivision in all graphs in the class. In particular, this implies that if the class in question excludes a fixed tree as a topological minor, then first-order model checking for graphs in the class is fixed-parameter tractable with an elementary dependency on the formula size.

Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all the performed operations on reals (typically comparisons and additions) take constant time. Classical Dijkstra's and Bellman-Ford algorithms have been described in this setting.

The classic technique of Baker [J. ACM ‘94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and it has been applied in a myriad of different variants and settings throughout the last 30 years. In this work we propose a dynamic variant of Baker's technique, where instead of finding an approximate solution in a given static graph, the task is to design a data structure for maintaining an approximate solution in a fully dynamic graph, that is, a graph that is changing over time by edge deletions and edge insertions. Specifically, we address the two most basic problems — Maximum Weight Independent Set and Minimum Weight Dominating Set — and we prove the following: for a fully dynamic n-vertex planar graph G, one can

We give an algorithm that given a graph G with n vertices and m edges and an integer k, in time Ok(n1+o(1)) + O(m) either outputs a rank decomposition of G of width at most k or determines that the rankwidth of G is larger than k; the Ok(·)-notation hides factors depending on k. Our algorithm returns also a (2k+1−1)-expression for cliquewidth, yielding a (2k+1−1)-approximation algorithm for cliquewidth with the same running time. This improves upon the Ok(n2) time algorithm of Fomin and Korhonen [STOC 2022].

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].

A class of graphs $\mathscr{C}$ is monadically stable if for any unary expansion $\widehat{\mathscr{C}}$ of $\mathscr{C}$, one cannot interpret, in first-order logic, arbitrarily long linear orders in graphs from $\widehat{\mathscr{C}}$. It is known that nowhere dense graph classes are monadically stable; these encompass most of the studied concepts of sparsity in graphs, including graph classes that exclude a fixed topological minor. On the other hand, monadic stability is a property expressed in purely model-theoretic terms and hence it is also suited for capturing structure in dense graphs. For several years, it has been suspected that one can create a structure theory for monadically stable graph classes that mirrors the theory of nowhere dense graph classes in the dense setting. In this work we provide a step in this direction by giving a characterization of monadic stability through the Flipper game: a game on a graph played by Flipper, who in each round can complement the edge relation between any pair of vertex subsets, and Connector, who in each round localizes the game to a ball of bounded radius. This is an analog of the Splitter game, which characterizes nowhere dense classes of graphs (Grohe, Kreutzer, and Siebertz, J.ACM'17). We give two different proofs of our main result. The first proof uses tools from model theory, and it exposes an additional property of monadically stable graph classes that is close in spirit to definability of types. Also, as a byproduct, we give an alternative proof of the recent result of Braunfeld and Laskowski (arXiv 2209.05120) that monadic stability for graph classes coincides with existential monadic stability. The second proof relies on the recently introduced notion of flip-wideness (Dreier, Mählmann, Siebertz, and Toruńczyk, ICALP 2023) and provides an efficient algorithm to compute Flipper's moves in a winning strategy.

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.

For every fixed $d \in \mathbb{N}$, we design a data structure that represents a binary $n \times n$ matrix that is $d$-twin-ordered. The data structure occupies $O_d(n)$ bits, which is the least one could hope for, and can be queried for entries of the matrix in time $O_d(\log \log n)$ per query.

In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-edge-cuts in a given 3-edge-connected graph, and then we use the output of this algorithm in order to determine the 4-edge-connected components of the graph.