Search

For a group $\Gamma$, a $\Gamma$-labelled graph is an undirected graph $G$ where every orientation of an edge is assigned an element of $\Gamma$ so that opposite orientations of the same edge are assigned inverse elements. A path in $G$ is non-null if the product of the labels along the path is not the neutral element of $\Gamma$. We prove that for every finite group $\Gamma$, non-null $S$-$T$ paths in $\Gamma$-labelled graphs exhibit the half-integral Erd\H{o}s-P\'osa property. More precisely, there is a function $f$, depending on $\Gamma$, such that for every $\Gamma$-labelled graph $G$, subsets of vertices $S$ and $T$, and integer $k$, one of the following objects exists: a family $\cal F$ consisting of $k$ non-null $S$-$T$ paths in $G$ such that every vertex of $G$ participates in at most two paths of $\cal F$; or a set $X$ consisting of at most $f(k)$ vertices that meets every non-null $S$-$T$ path in $G$. This in particular proves that in undirected graphs $S$-$T$ paths of odd length have the half-integral Erd\H{o}s-P\'osa property., Comment: 12 pages, 1 figure

Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$. A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix. We prove that tripods in directed graphs exhibit the Erd\H{o}s-P\'osa property. More precisely, there is a function $f\colon \mathbb{N}\to \mathbb{N}$ such that for every digraph $D$ with sources $S$ and sinks $T$, if $D$ does not contain $k$ vertex-disjoint tripods, then there is a set of at most $f(k)$ vertices that meets all the tripods in $D$., Comment: 12 pages, 4 figures

We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time ${\cal O}_H(n^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the ${\cal O}_H(\cdot)$-notation hides factors that depend on $H$ and are computable. By the Graph Minor Theorem, this implies the existence of an $n^{1+o(1)}$-time membership test for every minor-closed class of graphs. More generally, we give an ${\cal O}_{H,|X|}(m^{1+o(1)})$-time algorithm for the rooted version of the problem, in which $G$ comes with a set of roots $X\subseteq V(G)$ and some of the branch sets of the sought minor model of $H$ are required to contain prescribed subsets of $X$; here, $m$ is the total number of vertices and edges of $G$. This captures the Disjoint Paths problem, for which we obtain an ${\cal O}_{k}(m^{1+o(1)})$-time algorithm, where $k$ is the number of terminal pairs. For all the mentioned problems, the fastest algorithms known before are due to Kawarabayashi, Kobayashi, and Reed [JCTB 2012], and have a time complexity that is quadratic in the number of vertices of $G$. Our algorithm has two main ingredients: First, we show that by using the dynamic treewidth data structure of Korhonen, Majewski, Nadara, Pilipczuk, and Soko{\l}owski [FOCS 2023], the irrelevant vertex technique of Robertson and Seymour can be implemented in almost-linear time on apex-minor-free graphs. Then, we apply the recent advances in almost-linear time flow/cut algorithms to give an almost-linear time implementation of the recursive understanding technique, which effectively reduces the problem to apex-minor-free graphs., Comment: 81 pages

We study parameterized and approximation algorithms for a variant of Set Cover, where the universe of elements to be covered consists of points in the plane and the sets with which the points should be covered are segments. We call this problem Segment Set Cover. We also consider a relaxation of the problem called $\delta$-extension, where we need to cover the points by segments that are extended by a tiny fraction, but we compare the solution's quality to the optimum without extension. For the unparameterized variant, we prove that Segment Set Cover does not admit a PTAS unless $\mathsf{P}=\mathsf{NP}$, even if we restrict segments to be axis-parallel and allow $\frac{1}{2}$-extension. On the other hand, we show that parameterization helps for the tractability of Segment Set Cover: we give an FPT algorithm for unweighted Segment Set Cover parameterized by the solution size $k$, a parameterized approximation scheme for Weighted Segment Set Cover with $k$ being the parameter, and an FPT algorithm for Weighted Segment Set Cover with $\delta$-extension parameterized by $k$ and $\delta$. In the last two results, relaxing the problem is probably necessary: we prove that Weighted Segment Set Cover without any relaxation is $\mathsf{W}[1]$-hard and, assuming ETH, there does not exist an algorithm running in time $f(k)\cdot n^{o(k / \log k)}$. This holds even if one restricts attention to axis-parallel segments., Comment: 25 pages, 7 figures. The extended abstract will appear in the proceedings of STACS 2024

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})$., Comment: 25 pages, 2 figures

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 $({\leq} 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., Comment: 44 pages

We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form $\{A_i \mathbf{x} + D_i \mathbf{y}_i = \mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where $A_i$ and $D_i$ are bounded-size matrices. On the other hand, $n$-fold programs are integer programs of the form $\{{\sum_{i=1}^n C_i\mathbf{y}_i=\mathbf{a}} \textrm{ and } D_i\mathbf{y}_i=\mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where again $C_i$ and $D_i$ are bounded-size matrices. It is known that solving these kind of programs is fixed-parameter tractable when parameterized by the maximum dimension among the relevant matrices $A_i,C_i,D_i$ and the maximum absolute value of any entry appearing in the constraint matrix. We show that the parameterized tractability results for two-stage stochastic and $n$-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove that: - The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices $A_i,D_i$ and by the maximum absolute value of the entries of matrices $D_i$. That is, we allow matrices $A_i$ to have arbitrarily large entries. - The linear optimization problem for $n$-fold integer programs that are uniform -- all matrices $C_i$ are equal -- is fixed-parameter tractable when parameterized by the dimensions of matrices $C_i$ and $D_i$ and by the maximum absolute value of the entries of matrices $D_i$. That is, we require that $C_i=C$ for all $i=1,\ldots,n$, but we allow $C$ to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is $\mathsf{NP}$-hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input., Comment: 40 pages. Extended abstract to appear in the proceedings of SODA 2024

We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time $2^{o(k \log k)} \cdot n^{O(1)}$, where $k$ is the number of pairs of vertex subsets involved in the winning condition and $n$ is the vertex count of the game graph. While this result follows from the lower bounds provided by Calude et al [SIAM J. Comp. 2022], our reduction is simpler and arguably provides more insight into the complexity of the problem. In fact, the analogous lower bounds discussed by Calude et al, for solving Muller games and multidimensional parity games, follow as simple corollaries of our approach. Our reduction also highlights the usefulness of a certain pivot problem -- Permutation SAT -- which may be of independent interest., Comment: 10 pages, 5 figures. To appear in SOSA 2024

In the Maximum Independent Set of Objects problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ objects, where each object is a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F} \subseteq \mathcal{D}$ of maximum cardinality that consists of pairwise disjoint objects. This problem is $\mathsf{NP}$-hard and is equivalent to the problem of finding the maximum number of pairwise disjoint polygons in a given family of polygons in the plane. As shown by Adamaszek et al. (J. ACM '19), the problem admits a \emph{quasi-polynomial time approximation scheme} (QPTAS): a $(1-\varepsilon)$-approximation algorithm whose running time is bounded by $2^{\mathrm{poly}(\log(N),1/\epsilon)} \cdot n^{\mathcal{O}(1)}$. Nevertheless, to the best of our knowledge, in the polynomial-time regime only the trivial $\mathcal{O}(N)$-approximation is known for the problem in full generality. In the restricted setting where the objects are pseudolines in the plane, Fox and Pach (SODA '11) gave an $N^{\varepsilon}$-approximation algorithm with running time $N^{2^{\tilde{\mathcal{O}}(1/\varepsilon)}}$, for any $\varepsilon>0$. In this work, we present an $\text{OPT}^{\varepsilon}$-approximation algorithm for the problem that runs in time $N^{\tilde{\mathcal{O}}(1/\varepsilon^2)} n^{\mathcal{O}(1)}$, for any $\varepsilon>0$, thus improving upon the result of Fox and Pach both in terms of generality and in terms of the running time. Our approach combines the methodology of Voronoi separators, introduced by Marx and Pilipczuk (TALG '22), with a new analysis of the approximation factor., Comment: 20 pages, 2 colored figures, SODA 2024

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: * maintain a $(1-\varepsilon)$-approximation of the maximum weight of an independent set in $G$ with amortized update time $f(\varepsilon)\cdot n^{o(1)}$; and, * under the additional assumption that the maximum degree of the graph is bounded at all times by a constant, also maintain a $(1+\varepsilon)$-approximation of the minimum weight of a dominating set in $G$ with amortized update time $f(\varepsilon)\cdot n^{o(1)}$. In both cases, $f(\varepsilon)$ is doubly-exponential in $\mathrm{poly}(1/\varepsilon)$ and the data structure can be initialized in time $f(\varepsilon)\cdot n^{1+o(1)}$. All our results in fact hold in the larger generality of any graph class that excludes a fixed apex-graph as a minor., Comment: 37 pages, accepted to SODA '24

We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension $k$ as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth of a poset is bounded in terms of the treewidth of the cover graph. For the latter posets, we prove a stronger statement: every such poset with sufficiently large dimension contains the Kelly example of dimension $k$ as a subposet. Using this result, we obtain a full characterization of the minor-closed graph classes $\mathcal{C}$ such that posets with cover graphs in $\mathcal{C}$ have bounded dimension: they are exactly the classes excluding the cover graph of some Kelly example. Finally, we consider a variant of poset dimension called Boolean dimension, and we prove that posets with bounded cliquewidth have bounded Boolean dimension. The proofs rely on Colcombet's deterministic version of Simon's factorization theorem, which is a fundamental tool in formal language and automata theory, and which we believe deserves a wider recognition in structural and algorithmic graph theory.

We give two extensions of the recent theorem of the first author that the odd distance graph has unbounded chromatic number. The first is that for any non-constant polynomial $f$ with integer coefficients and positive leading coefficient, every finite colouring of the plane contains a monochromatic pair of distinct points whose distance is equal to $f(n)$ for some integer $n$. The second is that for every finite colouring of the plane, there is a monochromatic pair of points whose distance is a prime number., Comment: 24 pages

We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA'19] showed that it is also W[1]-hard when parameterized by the size $k$ of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90{\textdegree} before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question. In this work, we make progress towards this goal by showing a PAS under the following assumptions: - both the box and all the input rectangles have integral, polynomially bounded sidelengths; - every input rectangle is wide -- its width is greater than its height; and - the aspect ratio of the box is bounded by a constant.Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.

We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Set, are polynomial-time solvable in the class of $P_6$-free graphs. This generalizes the work of Grzesik, Klimo\v{s}ov\'{a}, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in $P_6$-free graphs~[SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rz\k{a}\.zewski, and Seymour on problems in $P_5$-free graphs~[SODA~2021]. The key step is a new generalization of the framework of potential maximal cliques. We show that instead of listing a large family of potential maximal cliques, it is sufficient to only list their carvers: vertex sets that contain the same vertices from the sought solution and have similar separation properties.

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition's width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth (sd). Here, sd is a bounded-depth analogue of cliquewidth, in the same way as td is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. Precisely, we prove that on $n$-vertex graphs equipped with a tree-model (a decomposition notion underlying sd) of depth $d$ and using $k$ labels, we can solve - Independent Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $O(dk^2\log n)$ space; - Max Cut in time $n^{O(dk)}$ using $O(dk\log n)$ space; and - Dominating Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $n^{O(1)}$ space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of IS the exponent of the parametric factor in the time complexity has to grow with $d$ if one wishes to keep the space complexity polynomial., Comment: Conference version to appear at the European Symposium on Algorithms (ESA 2023)

Let $d$ be a positive integer. For a finite set $X \subseteq \mathbb{R}^d$, we define its integer cone as the set $\mathsf{IntCone}(X) := \{ \sum_{x \in X} \lambda_x \cdot x \mid \lambda_x \in \mathbb{Z}_{\geq 0} \} \subseteq \mathbb{R}^d$. Goemans and Rothvoss showed that, given two polytopes $\mathcal{P}, \mathcal{Q} \subseteq \mathbb{R}^d$ with $\mathcal{P}$ being bounded, one can decide whether $\mathsf{IntCone}(\mathcal{P} \cap \mathbb{Z}^d)$ intersects $\mathcal{Q}$ in time $\mathsf{enc}(\mathcal{P})^{2^{\mathcal{O}(d)}} \cdot \mathsf{enc}(\mathcal{Q})^{\mathcal{O}(1)}$ [J. ACM 2020], where $\mathsf{enc}(\cdot)$ denotes the number of bits required to encode a polytope through a system of linear inequalities. This result is the cornerstone of their XP algorithm for BIN PACKING parameterized by the number of different item sizes. We complement their result by providing a conditional lower bound. In particular, we prove that, unless the ETH fails, there is no algorithm which, given a bounded polytope $\mathcal{P} \subseteq \mathbb{R}^d$ and a point $q \in \mathbb{Z}^d$, decides whether $q \in \mathsf{IntCone}(\mathcal{P} \cap \mathbb{Z}^d)$ in time $\mathsf{enc}(\mathcal{P}, q)^{2^{o(d)}}$. Note that this does not rule out the existence of a fixed-parameter tractable algorithm for the problem, but shows that dependence of the running time on the parameter $d$ must be at least doubly-exponential.

We show that the \textsc{Maximum Weight Independent Set} problem (\textsc{MWIS}) can be solved in quasi-polynomial time on $H$-free graphs (graphs excluding a fixed graph $H$ as an induced subgraph) for every $H$ whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of \textsc{MWIS} in $\mathcal{F}$-free graphs for any finite set $\mathcal{F}$ of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer $t \geq 1$. Let $S_{t,t,t}$ be the graph created from three paths on $t$ edges by identifying one endpoint of each path into a single vertex. We show that, given a graph $G$, one can in polynomial time find either an induced $S_{t,t,t}$ in $G$, or a balanced separator consisting of $\Oh(\log |V(G)|)$ vertex neighborhoods in $G$, or an extended strip decomposition of $G$ (a decomposition almost as useful for recursion for \textsc{MWIS} as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of $G$. This is a strengthening of a result of Majewski et al.\ [ICALP~2022] which provided such an extended strip decomposition only after the deletion of $\Oh(\log |V(G)|)$ vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above., Comment: 58 pages, 4 figures

We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph $G$ excluding a fixed-minor $Q$ on $n$ vertices and an accuracy parameter $\varepsilon>0$, constructs an edge-weighted graph~$H$ and an embedding $\eta\colon V(G)\to V(H)$ with the following properties: * For any constant size $Q$, the treewidth of $H$ is polynomial in $\varepsilon^{-1}$, $\log n$, and the logarithm of the stretch of the distance metric in $G$. * The expected multiplicative distortion is $(1+\varepsilon)$: for every pair of vertices $u,v$ of $G$, we have $\mathrm{dist}_H(\eta(u),\eta(v))\geq \mathrm{dist}_G(u,v)$ always and $\mathrm{Exp}[\mathrm{dist}_H(\eta(u),\eta(v))]\leq (1+\varepsilon)\mathrm{dist}_G(u,v)$. Our embedding is the first to achieve polylogarithmic treewidth of the host graph and comes close to the lower bound by Carroll and Goel, who showed that any embedding of a planar graph with $\mathcal{O}(1)$ expected distortion requires the host graph to have treewidth $\Omega(\log n)$. It also provides a unified framework for obtaining randomized quasi-polynomial-time approximation schemes for a variety of problems including network design, clustering or routing problems, in minor-free metrics where the optimization goal is the sum of selected distances. Applications include the capacitated vehicle routing problem, and capacitated clustering problems.

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 $6k+5$ under the promise that the treewidth of $G$ never grows above $k$. The amortized update time is ${\cal O}_k(2^{\sqrt{\log n}\log\log n})$, where $n$ is the vertex count of $G$ and the ${\cal 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 $\mathsf{CMSO}_2$ logic, 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]., Comment: 80 pages, 2 figures

We show that the edges of any planar graph of maximum degree at most $9$ can be partitioned into $4$ linear forests and a matching. Combined with known results, this implies that the edges of any planar graph $G$ of odd maximum degree $\Delta\ge 9$ can be partitioned into $\tfrac{\Delta-1}{2}$ linear forests and one matching. This strengthens well-known results stating that graphs in this class have chromatic index $\Delta$ [Vizing, 1965] and linear arboricity at most $\lceil(\Delta+1)/2\rceil$ [Wu, 1999].

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\"ahlmann, Siebertz, and Toru\'nczyk, arXiv 2206.13765) and provides an efficient algorithm to compute Flipper's moves in a winning strategy.

In the directed detour problem one is given a digraph $G$ and a pair of vertices $s$ and~$t$, and the task is to decide whether there is a directed simple path from $s$ to $t$ in $G$ whose length is larger than $\mathsf{dist}_{G}(s,t)$. The more general parameterized variant, directed long detour, asks for a simple $s$-to-$t$ path of length at least $\mathsf{dist}_{G}(s,t)+k$, for a given parameter $k$. Surprisingly, it is still unknown whether directed detour is polynomial-time solvable on general digraphs. However, for planar digraphs, Wu and Wang~[Networks, '15] proposed an $\mathcal{O}(n^3)$-time algorithm for directed detour, while Fomin et al.~[STACS 2022] gave a $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$-time fpt algorithm for directed long detour. The algorithm of Wu and Wang relies on a nontrivial analysis of how short detours may look like in a plane embedding, while the algorithm of Fomin et al.~is based on a reduction to the ${\S}$-disjoint paths problem on planar digraphs. This latter problem is solvable in polynomial time using the algebraic machinery of Schrijver~[SIAM~J.~Comp.,~'94], but the degree of the obtained polynomial factor is huge. In this paper we propose two simple algorithms: we show how to solve, in planar digraphs, directed detour in time $\mathcal{O}(n^2)$ and directed long detour in time $2^{\mathcal{O}(k)}\cdot n^4 \log n$. In both cases, the idea is to reduce to the $2$-disjoint paths problem in a planar digraph, and to observe that the obtained instances of this problem have a certain topological structure that makes them amenable to a direct greedy strategy.

In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are given a weighted set of $n$ axis-parallel rectangles in the plane. The task is to find a subset of pairwise non-overlapping rectangles with the maximum possible total weight. This problem is NP-hard and the best-known polynomial-time approximation algorithm, due to by Chalermsook and Walczak (SODA 2021), achieves approximation factor $O(\log\log n )$. While in the unweighted setting, constant factor approximation algorithms are known, due to Mitchell (FOCS 2021) and to G\'alvez et al. (SODA 2022), it remains open to extend these techniques to the weighted setting. In this paper, we consider MWISR through the lens of parameterized approximation. Grandoni et al. (ESA 2019) gave a $(1-\epsilon)$-approximation algorithm with running time $k^{O(k/\epsilon^8)} n^{O(1/\epsilon^8)}$ time, where $k$ is the number of rectangles in an optimum solution. Unfortunately, their algorithm works only in the unweighted setting and they left it as an open problem to give a parameterized approximation scheme in the weighted setting. Our contribution is a partial answer to the open question of Grandoni et al. (ESA 2019). We give a parameterized approximation algorithm for MWISR that given a parameter $k$, finds a set of non-overlapping rectangles of weight at least $(1-\epsilon) \text{opt}_k$ in $2^{O(k \log(k/\epsilon))} n^{O(1/\epsilon)}$ time, where $\text{opt}_k$ is the maximum weight of a solution of cardinality at most $k$. Note that thus, our algorithm may return a solution consisting of more than $k$ rectangles. To complement this apparent weakness, we also propose a parameterized approximation scheme with running time $2^{O(k^2 \log(k/\epsilon))} n^{O(1)}$ that finds a solution with cardinality at most $k$ and total weight at least $(1-\epsilon)\text{opt}_k$ for the special case of axis-parallel segments., Comment: 19 pages, 5 figures (colored)

The $t$-onion star is the digraph obtained from a star with $2t$ leaves by replacing every edge by a triple of arcs, where in $t$ triples we orient two arcs away from the center, and in the remaining $t$ triples we orient two arcs towards the center. Note that the $t$-onion star contains, as an immersion, every digraph on $t$ vertices where each vertex has outdegree at most $2$ and indegree at most $1$, or vice versa. We investigate the structure in digraphs that exclude a fixed onion star as an immersion. The main discovery is that in such digraphs, for some duality statements true in the undirected setting we can prove their directed analogues. More specifically, we show the next two statements. There is a function $f\colon \mathbb{N}\to \mathbb{N}$ satisfying the following: If a digraph $D$ contains a set $X$ of $2t+1$ vertices such that for any $x,y\in X$ there are $f(t)$ arc-disjoint paths from $x$ to $y$, then $D$ contains the $t$-onion star as an immersion. There is a function $g\colon \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ satisfying the following: If $x$ and $y$ is a pair of vertices in a digraph $D$ such that there are at least $g(t,k)$ arc-disjoint paths from $x$ to $y$ and there are at least $g(t,k)$ arc-disjoint paths from $y$ to $x$, then either $D$ contains the $t$-onion star as an immersion, or there is a family of $2k$ pairwise arc-disjoint paths with $k$ paths from $x$ to $y$ and $k$ paths from $y$ to $x$., Comment: 14 pages, 5 figures

We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph $H$ as a minor can be solved by an algorithm working in time $f(H)\cdot n^{O(1)}$, where $f$ is some function. In other words, we show that these problems are fixed-parameter tractable when parameterized by the size of the excluded minor, with the caveat that the bound on the running time is not necessarily computable. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given $H$-minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable $H$-minor-free graphs, performed in a second subordinate manuscript, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth., Comment: Part I of a full version of a paper accepted at STOC 2022

A set $X \subseteq V(G)$ in a graph $G$ is $(q,k)$-unbreakable if every separation $(A,B)$ of order at most $k$ in $G$ satisfies $|A \cap X| \leq q$ or $|B \cap X| \leq q$. In this paper, we prove the following result: If a graph $G$ excludes a fixed complete graph $K_h$ as a minor and satisfies certain unbreakability guarantees, then $G$ is almost rigid in the following sense: the vertices of $G$ can be partitioned in an isomorphism-invariant way into a part inducing a graph of bounded treewidth and a part that admits a small isomorphism-invariant family of labelings. This result is the key ingredient in the fixed-parameter algorithm for Graph Isomorphism parameterized by the Hadwiger number of the graph, which is presented in a companion paper., Comment: Part II of a full version of a paper appearing at STOC 2022

We study the class of rational recursive sequences (ratrec) over the rational numbers. A ratrec sequence is defined via a system of sequences using mutually recursive equations of depth 1, where the next values are computed as rational functions of the previous values. An alternative class is that of simple ratrec sequences, where one uses a single recursive equation, however of depth k: the next value is defined as a rational function of k previous values. We conjecture that the classes ratrec and simple ratrec coincide. The main contribution of this paper is a proof of a variant of this conjecture where the initial conditions are treated symbolically, using a formal variable per sequence, while the sequences themselves consist of rational functions over those variables. While the initial conjecture does not follow from this variant, we hope that the introduced algebraic techniques may eventually be helpful in resolving the problem. The class ratrec strictly generalises a well-known class of polynomial recursive sequences (polyrec). These are defined like ratrec, but using polynomial functions instead of rational ones. One can observe that if our conjecture is true and effective, then we can improve the complexities of the zeroness and the equivalence problems for polyrec sequences. Currently, the only known upper bound is Ackermanian, which follows from results on polynomial automata. We complement this observation by proving a PSPACE lower bound for both problems for polyrec. Our lower bound construction also implies that the Skolem problem is PSPACE-hard for the polyrec class.

We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: i) Binary CSP parameterized by the vertex cover number is $\mathrm{W}[3]$-complete. More generally, for every positive integer $d$, Binary CSP parameterized by the size of a modulator to a treedepth-d graph is $\mathrm{W}[2d+1]$-complete. This provides a new family of natural problems that are complete for odd levels of the W-hierarchy. ii) We introduce a new complexity class XSLP, defined so that Binary CSP parameterized by treedepth is complete for this class. We provide two equivalent characterizations of XSLP: the first one relates XSLP to a model of an alternating Turing machine with certain restrictions on conondeterminism and space complexity, while the second one links XSLP to the problem of model-checking first-order logic with suitably restricted universal quantification. Interestingly, the proof of the machine characterization of XSLP uses the concept of universal trees, which are prominently featured in the recent work on parity games iii) We describe a new complexity hierarchy sandwiched between the W-hierarchy and the A-hierarchy: For every odd $t$, we introduce a parameterized complexity class $\mathrm{S}[t]$ with $\mathrm{W}[t]\subseteq \mathrm{S}[t]\subseteq \mathrm{A}[t]$, defined using a parameter that interpolates between the vertex cover number and the treedepth. We expect that many of the studied classes will be useful in the future for pinpointing the complexity of various structural parameterizations of graph problems.

For a fixed simple digraph $H$ without isolated vertices, we consider the problem of deleting arcs from a given tournament to get a digraph which does not contain $H$ as an immersion. We prove that for every $H$, this problem admits a polynomial kernel when parameterized by the number of deleted arcs. The degree of the bound on the kernel size depends on $H$., Comment: Full version of a paper accepted to ESA 2022

In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in $f(k)n^{O(1)}$ time and $f(k)\log n$ space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on `tree-structured graphs' are complete for this class: we show that List Colouring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by $\log n$, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a `natural home' for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most $f(k)n^{O(1)}$ and use $f(k)\log n$ space. Moreover, we introduce `tree-shaped' variants of Weighted CNF-Satisfiability and Multicolour Clique that are XALP-complete.

We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local types and describe their behavior in contraction sequences -- the decomposition notion underlying twin-width. We showcase the applicability of the methodology by proving the following two algorithmic results. In both statements, we fix a first-order formula $\varphi(x_1,\ldots,x_k)$ and a constant $d$, and we assume that on input we are given a graph $G$ together with a contraction sequence of width at most $d$. (A) One can in time $O(n)$ construct a data structure that can answer the following queries in time $O(\log \log n)$: given $w_1,\ldots,w_k$, decide whether $\phi(w_1,\ldots,w_k)$ holds in $G$. (B) After $O(n)$-time preprocessing, one can enumerate all tuples $w_1,\ldots,w_k$ that satisfy $\phi(x_1,\ldots,x_k)$ in $G$ with $O(1)$ delay. In the case of (A), the query time can be reduced to $O(1/\varepsilon)$ at the expense of increasing the construction time to $O(n^{1+\varepsilon})$, for any fixed $\varepsilon>0$. Finally, we also apply our tools to prove the following statement, which shows optimal bounds on the VC density of set systems that are first-order definable in graphs of bounded twin-width. (C) Let $G$ be a graph of twin-width $d$, $A$ be a subset of vertices of $G$, and $\varphi(x_1,\ldots,x_k,y_1,\ldots,y_l)$ be a first-order formula. Then the number of different subsets of $A^k$ definable by $\phi$ using $l$-tuples of vertices from $G$ as parameters, is bounded by $O(|A|^l)$., Comment: 35 pages. Full version of an extended abstract to appear in the proceedings of ICALP 2022

We prove that for any triangle-free intersection graph of $n$ axis-parallel segments in the plane, the independence number $\alpha$ of this graph is at least $\alpha \ge n/4 + \Omega(\sqrt{n})$. We complement this with a construction of a graph in this class satisfying $\alpha \le n/4 + c \sqrt{n}$ for an absolute constant $c$, which demonstrates the optimality of our result., Comment: 10 pages and 3 figures

The treedepth of a graph $G$ is the least possible depth of an elimination forest of $G$: a rooted forest on the same vertex set where every pair of vertices adjacent in $G$ is bound by the ancestor/descendant relation. We propose an algorithm that given a graph $G$ and an integer $d$, either finds an elimination forest of $G$ of depth at most $d$ or concludes that no such forest exists; thus the algorithm decides whether the treedepth of $G$ is at most $d$. The running time is $2^{O(d^2)}\cdot n^{O(1)}$ and the space usage is polynomial in $n$. Further, by allowing randomization, the time and space complexities can be improved to $2^{O(d^2)}\cdot n$ and $d^{O(1)}\cdot n$, respectively. This improves upon the algorithm of Reidl et al. [ICALP 2014], which also has time complexity $2^{O(d^2)}\cdot n$, but uses exponential space.

We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a static algorithm that solves the given instance efficiently, our goal is to design a data structure that efficiently maintains a solution, or reports a lack thereof, upon updates in the instance. We first consider the Closest String problem, for which we design randomized dynamic data structures with amortized update times $d^{\mathcal{O}(d)}$ and $|\Sigma|^{\mathcal{O}(d)}$, respectively, where $\Sigma$ is the alphabet and $d$ is the assumed bound on the maximum distance. These are obtained by combining known static approaches to Closest String with color-coding. Next, we note that from a result of Frandsen et al.~[J. ACM'97] one can easily infer a meta-theorem that provides dynamic data structures for parameterized string problems with worst-case update time of the form $\mathcal{O}(\log \log n)$, where $k$ is the parameter in question and $n$ is the length of the string. We showcase the utility of this meta-theorem by giving such data structures for problems Disjoint Factors and Edit Distance. We also give explicit data structures for these problems, with worst-case update times $\mathcal{O}(k2^{k}\log \log n)$ and $\mathcal{O}(k^2\log \log n)$, respectively. Finally, we discuss how a lower bound methodology introduced by Amarilli et al.~[ICALP'21] can be used to show that obtaining update time $\mathcal{O}(f(k))$ for Disjoint Factors and Edit Distance is unlikely already for a constant value of the parameter $k$., Comment: 28 pages

Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class $\mathscr{C}$ can be $\mathsf{FO}$-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from $\mathscr{C}$ one cannot $\mathsf{FO}$-transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the $\mathsf{MSO}$-transduction quasi-order, even in the stronger form that concerns $\mathsf{FO}$-transductions instead of $\mathsf{MSO}$-transductions. The backbone of our proof is a graph-theoretic statement that says the following: If a graph $G$ excludes a path, the bipartite complement of a path, and a half-graph as semi-induced subgraphs, then the vertex set of $G$ can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance, it implies that the graphs in question form a class that is linearly $\chi$-bounded.

We prove that for every $t\in \mathbb{N}$ there is a constant $\gamma_t$ such that every graph with twin-width at most $t$ and clique number $\omega$ has chromatic number bounded by $2^{\gamma_t \log^{4t+3} \omega}$. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially $\chi$-bounded. This provides a significant step towards resolving the question of Bonnet et al. [ICALP 2021] about whether they are polynomially $\chi$-bounded., Comment: 21 pages, 2 figures

We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expansion and from nowhere dense classes. In both cases, the decomposition takes the form of a single colored rooted tree of bounded depth where, in addition, there can be links between nodes that are not related in the tree. The constraint is that the structure formed by the tree and the links has to be sparse. Using the decomposition theorem for transductions of nowhere dense classes, we show that they admit low-shrubdepth covers of size $O(n^\varepsilon)$, where $n$ is the vertex count and $\varepsilon>0$ is any fixed~real. This solves an open problem posed by Gajarsk\'y et al. (ACM TOCL '20) and also by Bria\'nski et al. (SIDMA '21)., Comment: 39 pages, 2 figures

We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and ordering the vertices by non-increasing radii of the associated discs. We prove that for every $d\in \mathbb{N}$, any such ordering has $d$-admissibility bounded by $O(d/\ln d)$ and weak $d$-coloring number bounded by $O(d^4 \ln d)$. This in particular shows that the $d$-admissibility of planar graphs is bounded by $O(d/\ln d)$, which asymptotically matches a known lower bound due to Dvo\v{r}\'ak and Siebertz., Comment: 19 pages, 6 figures

We introduce a new data structure for answering connectivity queries in undirected graphs subject to batched vertex failures. Precisely, given any graph G and integer k, we can in fixed-parameter time construct a data structure that can later be used to answer queries of the form: ``are vertices s and t connected via a path that avoids vertices $u_1,..., u_k$?'' in time $2^{2^{O(k)}}$. In the terminology of the literature on data structures, this gives the first deterministic data structure for connectivity under vertex failures where for every fixed number of failures, all operations can be performed in constant time. With the aim to understand the power and the limitations of our new techniques, we prove an algorithmic meta theorem for the recently introduced separator logic, which extends first-order logic with atoms for connectivity under vertex failures. We prove that the model-checking problem for separator logic is fixed-parameter tractable on every class of graphs that exclude a fixed topological minor. We also show a weak converse. This implies that from the point of view of parameterized complexity, under standard complexity assumptions, the frontier of tractability of separator logic is almost exactly delimited by classes excluding a fixed topological minor. The backbone of our proof relies on a decomposition theorem of Cygan et al. [SICOMP '19], which provides a tree decomposition of a given graph into bags that are unbreakable. Crucially, unbreakability allows to reduce separator logic to plain first-order logic within each bag individually. We design our model-checking algorithm using dynamic programming over the tree decomposition, where the transition at each bag amounts to running a suitable model-checking subprocedure for plain first-order logic. This approach is robust enough to provide also efficient enumeration of queries expressed in separator logic.

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., Comment: 24 pages, 2 figures

Let $\varphi$ be a sentence of $\mathsf{CMSO}_2$ (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 $\varphi$ 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 ${\cal O}_{\varphi,k}(\log n)$. By combining this result with a classic theorem of Erd\H{o}s and P\'osa, we give a fully dynamic data structure that maintains whether a graph contains a packing of $k$ vertex-disjoint cycles with amortized update time ${\cal O}_{k}(\log n)$. Our data structure also works in a larger generality of relational structures over binary signatures., Comment: 80 pages, 5 figures

We prove that every class of graphs $\mathscr C$ that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This generalizes analogous results for classes of bounded linear cliquewidth and of bounded cliquewidth. It also implies that monadically stable classes of bounded twin-widthare linearly $\chi$-bounded., Comment: 45 pages, 5 figures