Almost disjoint paths and separating by forbidden pairs

DOI10.1016/J.TCS.2023.114272MaRDI QIDQ6199396zbMATH OpenOpenAlexFDO

Authors Oliver Bachtler, Sven O. Krumke

Publication date 23 February 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingcomplexitygraph algorithmsdirected acyclic graphsalmost disjoint pathspath avoiding forbidden pairs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: By Menger's theorem the maximum number of arc-disjoint paths from a vertex s to a vertex t in a directed graph equals the minumum number of arcs needed to disconnect s and t, i.e., the minimum size of an s-t-cut. The max-flow problem in a network with unit capacities is equivalent to the arc-disjoint paths problem. Moreover the max-flow and min-cut problems form a strongly dual pair. We relax the disjointedness requirement on the paths, allowing them to be almost disjoint, meaning they may share up to one arc. The resulting almost disjoint paths problem (ADP) asks for k s-t-paths such that any two of them are almost disjoint. The separating by forbidden pairs problem (SFP) is the corresponding dual problem and calls for a set of k arc pairs such that every s-t-path contains both arcs of at least one such pair. In this paper, we explore these two problems, showing that they have an unbounded duality gap in general and analyzing their complexity. We prove that ADP is NP-complete when k is part of the input and that SFP is Sigma_2P-complete, even for acyclic graphs. Furthermore, we efficiently solve ADP when k<=2 is fixed and present a polynomial time algorithm based on dynamic programming for ADP when k is constant and the considered graphs are acyclic.

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1445327 (Why is no real title available?)
• scientific article; zbMATH DE number 3069630 (Why is no real title available?)
• Alternative Route Graphs in Road Networks
• Complexity of the path avoiding forbidden pairs problem revisited
• Computational Complexity
• Disjoint paths in a network
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• NP-completeness of some edge-disjoint paths problems
• Network flows. Theory, algorithms, and applications.
• On finding dissimilar Pareto-optimal paths
• On finding dissimilar paths
• On paths avoding forbidden pairs of vertices in a graph
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the complexity of paths avoiding forbidden pairs
• On the path avoiding forbidden pairs polytope
• Parameterized complexity in the polynomial hierarchy. Extending parameterized complexity theory to higher levels of the hierarchy
• The directed subgraph homeomorphism problem
• The disjoint paths problem in quadratic time
• The disjoint shortest paths problem

This page was built for publication: Almost disjoint paths and separating by forbidden pairs

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