2026-07-23T05:05:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7876 2024-03-06T10:41:19Z ddc:004 open_access

Half-Integral Linkages in Highly Connected Directed Graphs Edwards, Katherine Muzi, Irene Wollan, Paul linkage directed graph treewidth We study the half-integral k-Directed Disjoint Paths Problem (1/2 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 L >= 1. 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 k >= 2 there exists L(k) such that 1/2 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 1/2 kDDPP is solvable in time O(|V(G)|^{f(k)}) in (36k^3+2k)-strongly connected directed graphs. We 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 epsilon k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Katherine Edwards and Irene Muzi and Paul Wollan 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.36 urn:nbn:de:0030-drops-78769 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.36 eng https://creativecommons.org/licenses/by/3.0/legalcode