Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ arXiv.org e-Print Ar...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Discrete Mathematics
Article . 2026 . Peer-reviewed
License: Elsevier TDM
Data sources: Crossref
https://dx.doi.org/10.48550/ar...
Article . 2024
License: arXiv Non-Exclusive Distribution
Data sources: Datacite
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Constant congestion linkages in polynomially strong digraphs in polynomial time

Authors: Raul Lopes; Ignasi Sau;

Constant congestion linkages in polynomially strong digraphs in polynomial time

Abstract

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.

Keywords

FOS: Computer and information sciences, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Computational Complexity (cs.CC)

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green
Funded by