Articles & pre-prints

A digraph is $h$-semicomplete if every vertex has at most $h$ non-neighbors. In semicomplete digraphs, $k$-triples are obstructions to bounded directed pathwidth with many algorithmic applications: Fradkin and Seymour [JCTB 2013] showed that a large triple contains a subdivision of every small digraph, and triples were used for irrelevant vertex arguments in routing problems by Fomin and Pilipczuk [JCTB 2019] and Gomes, Lopes, and Sau [ICALP 2025]. Fradkin and Seymour also showed that there is a function $f(k)$ such that every semicomplete digraph of directed pathwidth at least $f(k)$ contains a $k$-triple, and their proof gives $f(k)$ triply exponential in $k$. For $h$-semicomplete digraphs, a result of Kitsunai et al. [ESA 2015] also yields a $k$-triple, but only existentially, and finding one in fixed-parameter time remained open. We improve the bound on $f(k)$ to a single exponential and extend the result to $h$-semicomplete digraphs: we show that every $h$-semicomplete digraph of directed pathwidth greater than $(h+1) \cdot k \cdot 2^{27k+9}$ contains a $k$-triple, which we find in polynomial time, and no bound subexponential in $k$ or sublinear in $h$ is possible. We also extend the approximation algorithm for directed pathwidth of Fomin and Pilipczuk to $h$-semicomplete digraphs, so its certificates of large directed pathwidth remain valid. Our proof is much shorter than the analysis of Kitsunai et al., and while their algorithm is exact, ours runs in polynomial time. As an application, we show that Arc-Disjoint Paths on $h$-semicomplete digraphs is fixed-parameter tractable parameterized by the number of paths and $h$, generalizing the semicomplete case. Finally, unlike in semicomplete digraphs, directed pathwidth does not bound directed cliquewidth: for every $k$, some acyclic $1$-semicomplete digraph, so of directed pathwidth zero, has directed cliquewidth at least $k$.

In the ARRIVAL problem, a token travels through a switch digraph: at every vertex, it leaves along one of two out-arcs, and the two are used alternately. The question is which of two terminals the token reaches first. ARRIVAL lies in $\mathsf{NP} \cap \mathsf{coNP}$, but no polynomial-time algorithm is known. The fastest known algorithms turn some vertices into terminals and search for consistent guesses of the numbers of tokens that these vertices send out. The first, due to Gärtner et al. [ICALP 2021], searches all vertices at once with an algorithm for fixed points of monotone maps, and the second, due to Haslebacher [ICALP 2025], searches one vertex at a time by binary search. Both search for a fixed point of the same map, which returns how many tokens arrive at the guessed vertices.

We guess the vertices in blocks of $k$, between these two extremes, which needs a search in $k$ dimensions with few evaluations of this map. To do so, we build on the connection between ARRIVAL and $\ell_1$-contractions established in the second of these works. We search with $\ell_1$-centerpoints of the remaining guesses, which are guaranteed to exist by Haslebacher et al. [FOCS 2025], and which we approximate deterministically. In order to prove our results, we show how to find the least fixed points of maps from $\{0, \ldots, N\}^k$ to itself that have unit increments.

For ARRIVAL on $n$-vertex switch digraphs, this gives run time $2^{\mathcal{O}(n^{1/3} \cdot \log^{2/3} n)}$, improving the previous time bound of $n^{\mathcal{O}(\sqrt{n})}$. We work with the more general Multi-ARRIVAL problem, with many tokens and several terminals, and solve it in the same time when there are at most $2^n$ tokens.

Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function $f_c(k)$ such that if a digraph has directed treewidth at least $f_c(k)$, then it contains a bramble of size at least $k$ and congestion at most $c$. By the Directed Grid Theorem of Kawarabayashi and Kreutzer [STOC 2015], such a function $f_c(k)$ exists for every value $c \geq 2$ of the congestion. However, even using the recent improvements due to Hatzel et al. [FOCS 2024], the resulting function is a power tower of height $22$. Recently, Masařík et al. [SIAM J. Discrete Math. 2022] proved that, for congestion $8$, the function $f_8(k)$ can be made polynomial; more precisely, they showed that $f_8(k) = \mathcal{O}(k^{48} \cdot \log^{13} k)$. They asked whether it is possible to decrease the congestion, ideally to $2$, even at the cost of a higher polynomial function. In this work we answer their question affirmatively with the best possible value of the congestion, by proving that $f_2(k) = \mathcal{O}(k^{96}\cdot \log^{23} k)$. We also obtain smaller polynomials for higher congestion, namely $f_4(k) = \mathcal{O}(k^{72} \cdot \log^{21} k)$ and $f_6(k) = \mathcal{O}(k^{66} \cdot \log^{18} k)$. Our results are inspired by the proof for congestion $8$, which we improve by introducing walkages. Walkages allow us to avoid technicalities of the original proof by translating ideas due to Reed and Wood [Eur. J. Comb. 2012] that work for undirected graphs to the directed setting. Our proofs are constructive and naturally yield polynomial-time algorithms to find the brambles assuming a certificate for large directed treewidth is given. Moreover, we discuss algorithmic applications of our results for the Directed Disjoint Paths with Congestion problem, and to half-integral packings of subgraphs with large directed treewidth.

It is well known that directed treewidth does not enjoy the nice algorithmic properties of its undirected counterpart. There exist, however, some positive results that, essentially, present XP algorithms for the problem of finding, in a given digraph $D$, a subdigraph isomorphic to a digraph $H$ that can be formed by the union of $k$ directed paths (with some extra properties), parameterized by $k$ and the directed treewidth of $D$. Our motivation is to tackle the following question: Are there subdigraphs, other than the directed paths, that can be found efficiently in digraphs of bounded directed treewidth? In a nutshell, the main message of this article is that, other than the directed paths, the only digraphs that seem to behave well with respect to directed treewidth are the stars. For this, we present a number of positive and negative results, generalizing several results in the literature, as well as some directions for further research.

In the Directed Disjoint Paths problem ($k$-DDP), we are given a digraph $k$ pairs of terminals, and the goal is to find $k$ pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen [SIAM J. Discrete Math. 1992] claimed that $k$-DDP is NP-complete on tournaments, and this result triggered a very active line of research about the complexity of the problem on tournaments and natural superclasses. We identify a flaw in their proof, which has been acknowledged by the authors, and provide a new NP-completeness proof. From an algorithmic point of view, Fomin and Pilipczuk [J. Comb. Theory B 2019] provided an FPT algorithm for the edge-disjoint version of the problem on semicomplete digraphs, and showed that their technique cannot work for the vertex-disjoint version. We overcome this obstacle by showing that the version of $k$-DDP where we allow congestion $c$ on the vertices is FPT on semicomplete digraphs provided that $c$ is greater than $k/2$. This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of $c$ is best possible for this technique, with a counterexample with no irrelevant vertices when $c \leq k/2$. We also prove that $k$-DDP on digraphs that can be partitioned into $h$ semicomplete digraphs is $W[1]$-hard parameterized by $k+h$, which shows that the XP algorithm presented by Chudnovsky, Scott, and Seymour [J. Comb. Theory B 2019] is essentially optimal.

A temporal (directed) graph is a (directed) graph whose edge availability varies over time, and temporal walks are sequences of adjacent edges respecting these availabilities. A third component of this scenario imposes time constraints on the vertices, known as “waiting time constraints.” Drawing a parallel with a transportation network, these constraints can be envisioned as the minimum and maximum time a person would need or be willing to stay at the same location. It is known that computing a temporal walk between a pair of vertices under waiting time constraints can be achieved in polynomial time, even when optimizing certain criteria. In this article, we extend these investigations to the problem of finding $k$ temporal walks such that no two distinct walks overlap in time. Given a multiset $\{(s_1, z_1), \ldots, (s_k, z_k)\}$ of pairs of vertices of a temporal graph $\mathcal{G}$, we consider the problem of finding a set of pairwise temporally disjoint walks $P_1, \ldots, P_k$ such that each $P_i$ is a temporal walk from $s_i$ to $z_i$. Under a given set of waiting time constraints, when $s_i = s$ and $z_i = z$ for all $i \in [k]$ we show that determining the existence of such walks is W[1]-hard when parameterized by $k$, and that it is NP-complete to decide the existence of a separator (i.e., a set of vertex occurrences in time intersecting all such walks) of size at most $h$. In the more general case, when the vertices $s_i$ and $z_i$ are allowed to be disjoint, we show that the walks can be found in XP time parameterized by $k$ when each walk has to wait at least $\omega_L(u) \geq 1$ units of time on each occurrence of each vertex $u$ used by the walk, and that the separator can be found in XP time with parameter $h$.

A class of acyclic digraphs $\mathscr{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in \mathscr{C}$ is contained in all tournaments of order $c\cdot |V(D)|$. The class of all acyclic digraphs is not linearly avoidable, and Fox, He, and Widgerson recently showed that this is not even the case for acyclic digraphs with bounded maximum degree. On the positive side, Thomason and Häggkvist proved that the class of oriented trees is linearly unavoidable. In this work, we generalize this result to acyclic digraphs obtained from an oriented tree by adding at most $k$ vertices, and $k$-blow-ups of oriented trees, for every fixed integer $k$. More precisely, we show that if $D$ is obtained from an oriented tree $F$ of order $n$ by adding $k$ universal vertices, then $D$ is contained in every tournament of order $2\cdot 3^{(k+1)(2k+1)} \cdot n$; and if $D$ is obtained from $F$ by replacing each vertex $u$ by an independent set $X_u$ of size $k$ and every arc $uv$ by all possible arcs from $X_u$ to $X_v$, then $D$ is contained in every tournament of order $2^{10+18k}k \cdot n$.

Given integers $k,c > 0$, we say that a digraph $D$ is $(k,c)$-linked if for every pair of ordered sets $\{s_1, \ldots, s_k\}$ and $\{t_1, \ldots, t_k\}$ of vertices of $D$, there are $P_1, \ldots, P_k$ such that for $i \in [k]$ each $P_i$ is a path from $s_i$ to $t_i$ and every vertex of $D$ appears in at most $c$ of those paths. Thomassen [Combinatorica, 1991] showed that for every fixed $k \geq 2$ there is no integer $p$ such that every $p$-strong digraph is $(k,1)$-linked. Edwards et al. [ESA, 2017] showed that every digraph $D$ with directed treewidth at least some function $f(k)$ contains a large bramble of congestion $2$ and that every $(36k^3 + 2k)$-strong digraph containing a bramble of congestion $2$ and size roughly $188k^3$ is $(k,2)$-linked. Since the directed treewidth of a digraph has to be at least its strong connectivity, this implies that there is a function $L(k)$ such that every $L(k)$-strong digraph is $(k,2)$-linked. This result was improved by Campos et al. [ESA, 2023], who showed that any $k$-strong digraph containing a bramble of size at least $2k(c\cdot k -c + 2) + c(k-1)$ and congestion $c$ is $(k,c)$-linked. Regarding the bramble, although the given bound on $f(k)$ is very large, Masařík et al. [SIDMA, 2022] showed that directed treewidth $\mathcal{O}(k^{48}\log^{13} k)$ suffices if the congestion is relaxed to $8$. We first show how to drop the dependence on $c$, for even $c$, on the size of the bramble that is needed in the work of Campos et al. [ESA, 2023]. Then, by making two local changes in the proof of Masařík et al. [SIDMA, 2022] we show how to build in polynomial time a bramble of size $k$ and congestion $8$ assuming that a large obstruction to directed treewidth (namely, a path system) is given. Applying these results, we show that there is a polynomial function $g(k)$ such that every $g(k)$-strong digraph is $(k,8)$-linked.

Given a class of (undirected) graphs $\mathcal{C}$, we say that a Feedback Arc Set (FAS for short) $F$ is a $\mathcal{C}$-FAS if the graph induced by the edges of $F$ (forgetting their orientations) belongs to $\mathcal{C}$. We show that deciding if a tournament has a $\mathcal{C}$-FAS is NP-complete when $\mathcal{C}$ is the class of all forests. We are motivated by connections between $\mathcal{C}$-FAS and structural parameters of tournaments, such as the dichromatic number, the clique number of tournaments, and the strong Erdős-Hajnal property.

Given a digraph $D$ together with an ordering $\prec$ of its vertices, the backedge graph of $D$ with respect to $\prec$ is the undirected graph $D^{\prec}$ with the same vertex set as $D$, where $xy \in E(D^{\prec})$ if $xy \in A(D)$ and $y \prec x$. We introduce the notion of the clique number of a digraph $D$, defined as the minimum clique number over all backedge graphs of $D$. We investigate its relationship with the dichromatic number. In particular, this concept allows us to define $\dic$-bounded classes of digraphs, which constitute the main topic of this paper, with a primary focus on tournaments. A class of tournaments is $\dic$-bounded if, for every tournament in the class, its dichromatic number is bounded by a function of its clique number. We study for which tournaments $H$ the class of $H$-free tournaments is $\dic$-bounded, and prove in particular that $H$ must have a backedge graph that is a forest. We prove that if a class of tournaments is $\dic$-bounded, then so is its closure under substitution. We also explore the relationship between $\dic$-bounded classes of tournaments and certain conjectures on tournaments. We prove that a $\dic$-bounded class of tournaments satisfies the $BIG \Rightarrow BIG$ Conjecture, and that a polynomially $\dic$-bounded class of tournaments satisfies the (tournament) Erdős-Hajnal Conjecture.

We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of congestion two (or any other constant) from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger's Theorem on appropriately defined auxiliary digraphs, and an alternative simpler one using matroids, however with worse polynomial running time. As an application, we manage to simplify and improve several results of Edwards et al. [ESA 2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large, which is the hard case). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular topology. We hope that our min-max relations will find further applications as, in our opinion, they are simple, robust, and versatile to be easily applicable to different types of routing problems in digraphs.

A temporal (directed) graph is a graph whose edges are available only at specific times during its lifetime, $\tau $. Paths are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasingly (i.e., non-decreasing) depending on the scenario. Then, the classical concept of connected components and also of unilateral connected components in static graphs and digraphs naturally extends to the temporal setting. In this paper, we answer to the following fundamental questions in temporal graphs. (i) What is the complexity of deciding the existence of a component of size $k$, parameterized by $\tau $, by $k$, and by $k+\tau $? We show that this question has a different answer depending on the considered definition of component and whether the temporal graph is directed or undirected. (ii) What is the minimum running time required to check whether a subset of vertices are pairwise reachable? A quadratic algorithm is known but, contrary to the static case, we show that a better running time is unlikely unless SETH fails. (iii) Is it possible to verify whether a subset of vertices is a component in polynomial time? We show that depending on the definition of temporal component this test is NP-complete.

A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its (discretized) lifetime $\tau $. In this setting, we ask that walks respect the temporal aspect by defining $\textit{temporal walks}$ as sequences of adjacent edges whose appearing times are either strictly increasing or non-decreasing (here called non-strict), depending on the scenario. The notion of disjointness between walks is also not unique: two walks are $\textit{vertex-disjoint}$ if they do not share a vertex, and are $\textit{temporal vertex-disjoint}$ if they do not share a vertex at the same time. Thus a $\textit{temporal path}$ is a temporal walk where no repetition of vertices, at any time, is allowed. This is an important distinction that separates the interpretation of our results from those of previous works on the topic. In this paper we focus on various questions regarding connectivity (maximum number of disjoint paths) and robustness (minimum size of a cut) between a given pair of vertices. Such problems are related to the well-known Menger's Theorem on static graphs. We explore all possible interpretations of such problems, according to vertex and temporal vertex-disjointness, strict and non-strict temporal paths, and directed and undirected temporal graphs. We present a number of new results, the main of which states that Menger's Theorem holds when the maximum number of temporal vertex-disjoint temporal paths is equal to 1.

We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for a class $\mathcal C$ implies that tractable FO model checking on $\mathcal C$ is perfectly understood: On hereditary closures $\mathcal D$ of subclasses of $\mathcal C$, FO model checking is fixed-parameter tractable (FPT) exactly when $\mathcal D$ has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we show that segment graphs, directed path graphs, and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that $K_{t,t}$-free segment graphs, and axis-parallel $H_t$-free unit segment graphs have bounded twin-width, where $H_t$ is the half-graph or ladder of height $t$. In contrast, axis-parallel $H_4$-free two-lengthed segment graphs have unbounded twin-width. Our new results, combined with the known FPT algorithm for FO model checking on graphs given with $O(1)$-sequences, lead to win-win arguments. For instance, we derive FPT algorithms for $k$-Ladder on visibility graphs of 1.5D terrains, and $k$-Independent Set on visibility graphs of simple polygons.

Chordal graphs are the intersection graphs of subtrees of a tree, while interval graphs of subpaths of a path. Undirected path graphs, directed path graphs and rooted directed path graphs are intermediate graph classes, defined, respectively, as the intersection graphs of paths of a tree, of directed paths of an oriented tree, and of directed paths of an out branching. All of these path graphs have vertex leafage 2. Dominating Set, Connected Dominating Set, and Steiner Tree problems are W[2]-hard parameterized by the size of the solution on chordal graphs, NP-complete on undirected path graphs, and polynomial-time solvable on rooted directed path graphs, and hence also on interval graphs. We further investigate the (parameterized) complexity of all these problems when constrained to chordal graphs, taking the vertex leafage and the aforementioned classes into consideration. We prove that Dominating Set, Connected Dominating Set, and Steiner Tree are FPT on chordal graphs when parameterized by the size of the solution plus the vertex leafage, and that Weighted Connected Dominating Set is polynomial-time solvable on strongly chordal graphs. We also introduce a new subclass of undirected path graphs, which we call in–out rooted directed path graphs, as the intersection graphs of directed paths of an in–out branching. We prove that Dominating Set, Connected Dominating Set, and Steiner Tree are solvable in polynomial time on this class, generalizing the polynomiality for rooted directed path graphs proved by Booth and Johnson (SIAM J. Comput. 11 (1982), 191-199.) and by White et al. (Networks 15 (1985), 109-124.).

An $s$-branching flow $f$ in a network $\mathcal{N} = (D, u)$, where $u$ is the capacity function, is a flow that reaches every vertex in $V(D)$ from $s$ while loosing exactly one unit of flow in each vertex other than $s$. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity $n-1$, a network $\mathcal{N}$ admits $k$ arc-disjoint $s$-branching flows if and only if its associated digraph $D$ contains $k$ arc-disjoint $s$-branchings. Thus, a classical result by Edmonds stating that a digraph contains $k$ arc-disjoint $s$-branchings if and only if the in-degree of every set $X \subseteq V(D) \setminus \{s\}$ is at least $k$ also characterizes the existence of $k$ arc-disjoint $s$-branching flows in those networks, suggesting that the larger the capacities are, the closer an $s$-branching flow is from simply being an $s$-branching. This observation is further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomial algorithm to find the flows (if they exist) when every arc has capacity $n-c$, for every fixed $c \geq 1$, and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper, we investigate how a property that is a natural extension of the characterization by Edmonds’ relates to the existence of $k$ arc-disjoint $s$-branching flows in networks. Although this property is always necessary for the existence of the flows, we show that it is not always sufficient and that it is hard to decide if the desired flows exist even if we know beforehand that the network satisfies it. On the positive side, we show that it guarantees the existence of the desired flows in some particular cases depending on the choice of the capacity function or on the structure of the underlying graph of $D$, for example. We remark that, in those positive cases, polynomial time algorithms to find the flows can be extracted from the constructive proofs.

We investigate a number of coloring problems restricted to bipartite graphs with bounded diameter. First, we investigate the $k$-List Coloring, List $k$-Coloring, and $k$-Precoloring Extension problems on bipartite graphs with diameter at most $d$, proving NP-completeness in most cases, and leaving open only the List $3$-Coloring and $3$-Precoloring Extension problems when $d=3$. Some of these results are obtained through a proof that the Surjective $C_6$-Homomorphism problem is NP-complete on bipartite graphs with diameter at most four. Although the latter result has been already proved [Vikas, 2017], we present ours as an alternative simpler one. As a byproduct, we also get that $3$-Biclique Partition is NP-complete. An attempt to prove this result was presented in [Fleischner, Mujuni, Paulusma, and Szeider, 2009], but there was a flaw in their proof, which we identify and discuss here. Finally, we prove that the $3$-Fall Coloring problem is NP-complete on bipartite graphs with diameter at most four, and prove that NP-completeness for diameter three would also imply NP-completeness of $3$-Precoloring Extension on diameter three, thus closing the previously mentioned open cases. This would also answer a question posed in [Kratochvíl, Tuza, and Voigt, 2002].

A temporal digraph $\mathcal{G}$ is a triple $(G, \gamma , \lambda )$ where $G$ is a digraph, $\gamma $ is a function on $V(G)$ that tells us the timestamps when a vertex is active, and $\lambda $ is a function on $E(G)$ that tells for each $uv \in E(G)$ when $u$ and $v$ are linked. Given a static digraph $G$, and a subset $R\subseteq V(G)$, a spanning branching with root $R$ is a subdigraph of $G$ that has exactly one path from $R$ to each $v\in V(G)$. In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding $k$ edge-disjoint spanning branchings respectively rooted at given $R_1,\cdots,R_k$. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal graphs. A branching $\mathcal{B}$ is vertex-spanning if the root is able to reach each vertex $v$ of $G$ at some time where $v$ is active, while it is temporal-spanning if $v$ can be reached from the root at every time where $v$ is active. On the other hand, two branchings $\mathcal{B}_1$ and $\mathcal{B}_2$ are edge-disjoint if they do not use the same edge of $G$, and are temporal-edge-disjoint if they can use the same edge of $G$ but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are $\mathsf{NP}$-complete, even under very strict assumptions.

In the Directed Disjoint Paths problem, we are given a digraph $D$ and a set of requests $\{(s_1, t_1), \ldots, (s_k, t_k)\}$, and the task is to find a collection of pairwise vertex-disjoint paths $\{P_1, \ldots, P_k\}$ such that each $P_i$ is a path from $s_i$ to $t_i$ in $D$. This problem is NP-complete for fixed $k=2$ and W[1]-hard with parameter $k$ in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Positive results are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified part of size prescribed by a parameter. Namely, in the Disjoint Enough Directed Paths problem, given an $n$-vertex digraph $D$, a set of $k$ requests, and non-negative integers $d$ and $s$, the task is to find a collection of paths connecting the requests such that at least $d$ vertices of $D$ occur in at most $s$ paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of $D$. Among other results, we show that the problem is W[1]-hard in DAGs with parameter $d$ and, on the positive side, we give an algorithm in time $\mathcal{O}(n^{d+2} \cdot k^{d\cdot s})$ and a kernel of size $d \cdot 2^{k-s}\cdot \binom{k}{s} + 2k$ in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number $k$ of terminals and $p$, where $p = n - q$ and $q$ is the size of the solution.

The Grid Theorem of Robertson and Seymour [JCTB, 1986], is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001], and proved by Kawarabayashi and Kreutzer [STOC, 2015]. Namely, they showed that there is a function $f(k)$ such that every digraph of directed tree-width at least $f(k)$ contains a cylindrical grid of size $k$ as a butterfly minor and stated that their proof can be turned into an XP algorithm, with parameter $k$, that either constructs a decomposition of the appropriate width, or finds the claimed large cylindrical grid as a butterfly minor. In this paper, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer to improve this XP algorithm into an FPT algorithm. Towards this, our main technical contributions are two FPT algorithms with parameter $k$. The first one either produces an arboreal decomposition of width $3k-2$ or finds a haven of order $k$ in a digraph $D$, improving on the original result for arboreal decompositions by Johnson et al. The second algorithm finds a well-linked set of order $k$ in a digraph $D$ of large directed tree-width. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices $T$ in FPT time with parameter $|T|$, a result that we consider to be of its own interest.

A $(k_1+k_2)$-bispindle is the union of $k_1$ $(x,y)$-dipaths and $k_2$ $(y,x)$-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every $(1,1)$- bispindle $B$, there exists an integer $k$ such that every strongly connected digraph with chromatic number greater than $k$ contains a subdivision of $B$. We investigate generalisations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any $(3,0)$-bispindle or $(2,2)$-bispindle. Then we show that strongly connected digraphs with large chromatic number contains a $(2,1)$-bispindle, where at least one of the $(x,y)$-dipaths and the $(y,x)$-dipath are long.

The Turán number $\mathrm{ex}(n, H)$ is the maximum number of edges in a graph on $n$ vertices which does not contain $H$ as a subgraph. Gorgol gives a lower bound for $\mathrm{ex}(n, H)$ when $H$ is the disjoint union of $k$ copies of $P_3$ and conjectures this bound is tight. In this paper, we give an algorithmic proof of Gorgol’s Conjecture.