Almost disjoint paths and separating by forbidden pairs

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

Authors: Oliver Bachtler, Sven O. Krumke 

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

dynamic programmingcomplexitygraph algorithmsdirected acyclic graphsalmost disjoint pathspath avoiding forbidden pairs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)