Résumé
Given positive integers k and c, we say that a digraph D is (k, c)-linked if for every pair of ordered sets {s1,...,sk} and {t1,...,tk} of vertices of D, there are paths P1,..., Pk such that for i is an element of [k] each Pi is a path from si to ti and every vertex of D appears in at most c of those paths. A classical result by Thomassen [Combinatorica, 1991] states that, for every fixed k >= 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. Then, they showed that every (36k3 + 2k)-strong digraph containing a bramble of congestion 2 and size roughly 188k3 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. The result by Edwards et al. was improved by Campos et al. [ESA, 2023], who showed that any k-strong digraph containing a bramble of size at least 2k(c.k-c + 2) + c(k-1) and congestion cis (k, c)-linked. Regarding how to find the bramble, although the given bound on f (k) is very large, Masar & iacute;k et al. [SIDMA, 2022] showed that directed treewidth O(k48 log13 k) suffices if the congestion is relaxed to 8. In this article, 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 Masar & iacute;k et al. [SIDMA, 2022] we show how to construct 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 those two results, we show that there is polynomial function g(k) such that every g(k)-strong digraph is (k, 8)-linked. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.