Almost disjoint paths and separating by forbidden pairs

DOI10.1016/J.TCS.2023.114272arXiv2202.10090OpenAlexW4387967528MaRDI QIDQ6199396

Sven O. Krumke, Oliver Bachtler, Unnamed Author

Publication date: 23 February 2024

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

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.

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

zbMATH Keywords

complexitydynamic programminggraph algorithmsdirected acyclic graphsalmost disjoint pathspath avoiding forbidden pairs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the path avoiding forbidden pairs polytope
• The disjoint paths problem in quadratic time
• On paths avoding forbidden pairs of vertices in a graph
• On finding dissimilar Pareto-optimal paths
• On the complexity of paths avoiding forbidden pairs
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• On finding dissimilar paths
• Parameterized complexity in the polynomial hierarchy. Extending parameterized complexity theory to higher levels of the hierarchy
• Complexity of the path avoiding forbidden pairs problem revisited
• Alternative Route Graphs in Road Networks
• Disjoint paths in a network
• On the Complexity of Timetable and Multicommodity Flow Problems
• Computational Complexity

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