Half-integral linkages in highly connected directed graphs

DOI10.4230/LIPICS.ESA.2017.36MaRDI QIDQ5111723zbMATH OpenFDO

Authors Katherine Edwards, Irene Muzi, Paul Wollan

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1611.01004

zbMATH Keywords

directed graphlinkagetreewidth

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study the half-integral $k$-Directed Disjoint Paths Problem ($frac12$kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where $k=2$, and the input graph is $L$-strongly connected, for any $Lgeq1$. We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with $k$ as part of the input). Specifically, we show that there is an absolute constant $c$ such that for each $kgeq2$ there exists $L(k)$ such that $frac12$kDDPP is solvable in time $O(|V(G){|}^c)$ for a $L(k)$-strongly connected directed graph $G$. As the function $L(k)$ grows rather quickly, we also show that $frac12$kDDPP is solvable in time $O(|V(G){|}^{f(k)})$ in $(36k^3+2k)$-strongly connected directed graphs. We also show that for each $epsilon<1$ deciding half-integral feasibility of kDDPP instances is NP-complete when $k$ is given as part of the input, even when restricted to graphs with strong connectivity $epsilonk$.

Recommendations

• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• Disjoint paths in decomposable digraphs
• Improved algorithm for the half-disjoint paths problem
• An improved algorithm for the half-disjoint paths problem
• A nearly linear time algorithm for the half integral parity disjoint paths packing problem

Cites work

• 2-linked graphs
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• An Improved Algorithm for Finding Cycles Through Elements
• Directed tree-width
• Finding k Disjoint Paths in a Directed Planar Graph
• Graph minors. XIII: The disjoint paths problem
• Half-integral linkages in highly connected directed graphs
• Highly connected non-2-linked digraphs
• Highly connected sets and the excluded grid theorem
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• The directed grid theorem
• The directed subgraph homeomorphism problem

Cited in

(9)

• A relaxation of the directed disjoint paths problem: a global congestion metric helps
• Digraphs of bounded width
• Constant congestion brambles in directed graphs
• A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
• Adapting the directed grid theorem into an FPT algorithm
• Half-integral linkages in highly connected directed graphs
• scientific article; zbMATH DE number 6539682 (Why is no real title available?)
• Constant congestion linkages in polynomially strong digraphs in polynomial time
• New Menger-like dualities in digraphs and applications to half-integral linkages

This page was built for publication: Half-integral linkages in highly connected directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111723)