Half-integral linkages in highly connected directed graphs

DOI10.4230/LIPICS.ESA.2017.36zbMATH Open1448.05087arXiv1611.01004MaRDI QIDQ5111723FDOQ5111723

Katherine Edwards, Paul Wollan, Irene Muzi

Publication date: 27 May 2020

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$.

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

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

zbMATH Keywords

treewidthdirected graphlinkage

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
• Constant Congestion Brambles in Directed Graphs
• Adapting the Directed Grid Theorem into an FPT Algorithm
• Digraphs of Bounded Width
• Half-integral linkages in highly connected directed graphs
• A relaxation of the directed disjoint paths problem: a global congestion metric helps
• Title not available (Why is that?)

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)