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 investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph D can be augmented with (any number of) arcs X such that D+X is strongly connected, but still plane and oriented, is NP-hard. The hardness also holds for the planar variant. This question becomes trivial within plane (or planar) digraphs, like most connectivity augmentation problems without a budget constraint. The budgeted variant, Plane Strong Connectivity Augmentation (PSCA) considers a plane oriented graph D along with some integer k, and asks for an X of size at most k ensuring that D+X is strongly connected, while remaining plane and oriented. Our main result is a fixed-parameter tractable algorithm for PSCA, running in time 2^O(k) n² log n. The cornerstone of our procedure is a structural result showing that, for any fixed k, each face admits a bounded number of partial solutions "dominating" all others. Then, our algorithm for PSCA combines face-wise branching with a randomized reduction to the polynomial Minimum Dijoin problem, yielding a Monte-Carlo FPT algorithm, which we derandomize. To the best of our knowledge, this is the first FPT algorithm for a (hard) connectivity augmentation problem constrained by planarity.

Given an oriented graph $D$, the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endpoints in $X$. When the subset $X$ is of size $p$ (resp. at most $p$), this operation is called an $(=p)$-inversion (resp. $(\leq p)$-inversion). Then, an oriented graph is $(=p)$-invertible if it can be made acyclic by a sequence of $p$-inversions. We observe that, for $n=|V(D)|$, deciding whether $D$ is $(=n-1)$-invertible is equivalent to deciding whether $D$ is acyclically pushable, and thus NP-complete. In all other cases, when $p \neq n-1$, we construct a polynomial-time algorithm to decide $(=p)$-invertibility. We then consider the $(= p)$-inversion number, $\text{inv}^{= p}(D)$ (resp. $(\leq p)$-inversion number, $\text{inv}^{\leq p}(D)$), defined as the minimum number of $(=p)$-inversions (resp. $(\leq p)$-inversions) rendering $D$ acyclic. We show that every $(=p)$-invertible digraph $D$ satisfies $\text{inv}^{= p}(D) \leq |A(D)|$ for every integer $p\geq 2$. When $p$ is even, we bound $\text{inv}^{= p}$ by a (linear) function of the feedback arc set number, and rule out the existence of any bounding function for odd $p$. Finally, we study the complexity of deciding whether the $(= p)$-inversion number, or the $(\leq p)$-inversion number, of a given oriented graph is at most a given integer $k$. For any fixed positive integer $p \geq 2$, when $k$ is part of the input, we show that both problems are NP-hard even in tournaments. In general oriented graphs, we prove $W[1]$-hardness for both problems when parameterized by $p$, even for $k=1$. In contrast, we exhibit polynomial kernels in $p + k$ for both problems in tournaments.

International audience

Abstract Given a positive integer d, the class d-DIR is defined as all those intersection graphs formed from a finite collection of line segments in $${\mathbb R}^2$$ R 2 having at most d slopes. Since each slope induces an interval graph, it easily follows for every G in d-DIR with clique number at most $$\omega $$ ω that the chromatic number $$\chi (G)$$ χ ( G ) of G is at most $$d\omega $$ d ω . We show for every even value of $$\omega $$ ω how to construct a graph in d-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $$\chi $$ χ -binding function of d-DIR is $$\omega \mapsto d\omega $$ ω ↦ d ω for $$\omega $$ ω even and $$\omega \mapsto d(\omega -1)+1$$ ω ↦ d ( ω - 1 ) + 1 for $$\omega $$ ω odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $$d=2$$ d = 2 .

We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++.

We describe DreyFVS, a heuristic for Directed Feedback Vertex Set submitted to the 2022 edition of Parameterized Algorithms and Computational Experiments Challenge. The Directed Feedback Vertex Set problem asks to remove a minimal number of vertices from a digraph such that the resulting digraph is acyclic. Our algorithm first performs a guess on a reduced instance by leveraging the Sinkhorn-Knopp algorithm, to then improve this solution by pipelining two local search methods.

A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on contraction sequences. More precisely, if one puts error edges, henceforth red edges, between two vertices representing non-homogeneous subsets, the twin-width is the minimum integer d such that a contraction sequence exists that keeps red degree at most d. By changing the condition imposed on the trigraphs (i.e., graphs with some edges being red) and possibly slightly tweaking the notion of contractions, we show how to characterize the well-established bounded rank-width, tree-width, linear rank-width, path-width –usually defined in the framework of branch-decompositions–, and proper minor-closed classes by means of contraction sequences. Contraction sequences hold a crucial advantage over branch-decompositions: While one can scale down contraction sequences to capture classical width notions, the more general bounded twin-width goes beyond their scope, as it contains planar graphs in particular, a class with unbounded rank-width. As an application we give a transparent alternative proof of the celebrated Courcelle's theorem (actually of its generalization by Courcelle, Makowsky, and Rotics), that MSO2 (resp. MSO1) model checking on graphs with bounded tree-width (resp. bounded rank-width) is fixed-parameter tractable in the size of the input sentence. We are hopeful that our characterizations can help in other contexts. We then explore new avenues along the general theme of contraction sequences both in order to refine the landscape between bounded tree-width and bounded twin-width (via spanning twin-width) and to capture more general classes than bounded twin-width. To this end, we define an oriented version of twin-width, where appearing red edges are oriented away from the newly contracted vertex, and the mere red out-degree should remain bounded. Surprisingly, classes of bounded oriented twin-width coincide with those of bounded twin-width. This greatly simplifies the task of showing that a class has bounded twin-width. As an example, using a lemma by Norine, Seymour, Thomas, and Wollan, we give a 5-line proof that Kt-minor free graphs have bounded twin-width. Without oriented twin-width, this fact was shown by a somewhat intricate 4-page proof in the first paper of the series. Finally we explore the concept of partial contraction sequences, instead of terminating on a single-vertex graph, the sequence ends when reaching a particular target class. We show that FO model checking (resp. ∃FO model checking) is fixed-parameter tractable on classes with partial contraction sequences to a class of bounded degree (resp. bounded expansion), provided such a sequence is given. Efficiently finding such partial sequences could turn out simpler than finding a (complete) sequence.

We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main result is that a polynomial kernel for $k$-Dominating Set on graphs of twin-width at most 4 would contradict a standard complexity-theoretic assumption. The reduction is quite involved, especially to get the twin-width upper bound down to 4, and can be tweaked to work for Connected $k$-Dominating Set and Total $k$-Dominating Set (albeit with a worse upper bound on the twin-width). The $k$-Independent Set problem admits the same lower bound by a much simpler argument, previously observed [ICALP '21], which extends to $k$-Independent Dominating Set, $k$-Path, $k$-Induced Path, $k$-Induced Matching, etc. On the positive side, we obtain a simple quadratic vertex kernel for Connected $k$-Vertex Cover and Capacitated $k$-Vertex Cover on graphs of bounded twin-width. Interestingly the kernel applies to graphs of Vapnik-Chervonenkis density 1, and does not require a witness sequence. We also present a more intricate $O(k^{1.5})$ vertex kernel for Connected $k$-Vertex Cover. Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most optimization/decision graph problems can be solved in polynomial time on graphs of twin-width at most 1.