Almost Disjoint Paths and Separating by Forbidden Pairs

Oliver Bachtler, Tim Bergner, Sven O. KrumkeSSRN 2022 · DOI

TL;DR

This paper introduces and analyzes "almost disjoint paths" (ADP) and its dual problem, "separating by forbidden pairs" (SFP). They demonstrate that these problems have an unbounded duality gap, meaning they are not as tightly linked as their well-known counterparts in network flow. The authors also establish the computational complexity of these problems, proving ADP is NP-complete and SFP is $\Sigma_2^P$-complete, even for simpler graph structures.

What Problem Does This Paper Address?

In network routing and various applications, we often need to find multiple paths between a source and a destination. The classic "disjoint paths" problem requires these paths to share no common edges (or vertices). This is well-understood and directly related to the max-flow min-cut theorem. However, in many real-world scenarios, paths don't need to be perfectly disjoint; they can share some resources.

This paper explores a relaxation of the disjoint paths problem: the Almost Disjoint Paths (ADP) problem. Here, paths are allowed to share at most one arc. This is a more practical constraint for scenarios like distributing risk or providing diverse options to customers. The authors also introduce the Separating by Forbidden Pairs (SFP) problem as the dual of ADP. SFP asks for the minimum number of pairs of arcs such that every path must contain at least one of these forbidden pairs.

The core challenge addressed is understanding the computational complexity of these "almost disjoint" path problems and their duals, and how their relationship differs from the standard disjoint paths problem. Specifically, they investigate:

  • Duality Gap: How does the optimal solution for ADP relate to the optimal solution for SFP? Is it a "strong duality" (optimal values are equal) or "weak duality" (optimal values can differ)?
  • Computational Complexity: Are these problems efficiently solvable, or do they fall into hard complexity classes like NP-complete or $\Sigma_2^P$-complete?

Methods

The paper employs a combination of theoretical computer science techniques:

  • Integer Programming Formulations: The authors use integer programming to formally define ADP and SFP and to analyze their duality. They show that their linear programming relaxations are dual pairs, but the integer versions exhibit a weak duality with an unbounded gap in general.
  • Dynamic Programming: For finding a constant number of almost disjoint paths in acyclic graphs, they develop a dynamic programming approach. This is then adapted for general graphs.
  • NP-Completeness Proofs: To prove ADP is NP-complete, they use a reduction from the NP-complete independent set problem. This involves constructing a specific graph where the existence of $k$ almost disjoint paths corresponds to the existence of an independent set of size $k$.
  • $\Sigma_2^P$-Completeness Proof: For SFP, they prove $\Sigma_2^P$-completeness by reducing the $\Sigma_2^P$-complete problem $\Sigma_2$SAT to SFP. This involves a complex graph construction using "gadgets" that encode Boolean formula variables and clauses.
  • Graph Transformations and Typification: To handle the complexity of the SFP construction, they introduce a "typification" technique to manage interactions between different parts of the constructed graph and ensure that paths correspond to valid assignments.

Datasets

Not discussed in the paper. The paper focuses on theoretical graph problems and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Unbounded Duality Gap: Unlike the standard disjoint paths problem (where max-flow and min-cut are strongly dual), ADP and SFP have an unbounded duality gap. This means the minimum number of forbidden pairs needed to separate paths can be arbitrarily larger than the maximum number of almost disjoint paths. This is a significant theoretical departure.
  • ADP is NP-Complete (Even on Acyclic Graphs): Even with the relaxed "at most one arc in common" rule, finding $k$ almost disjoint paths is computationally hard. The fact that it's NP-complete even on acyclic graphs highlights the inherent difficulty.
  • SFP is $\Sigma_2^P$-Complete: The dual problem, SFP, is even harder, belonging to the second level of the polynomial hierarchy. This suggests that finding a minimal set of forbidden pairs is a more complex computational task than finding almost disjoint paths.
  • Fixed $k$ is Tractable (for Acyclic Graphs): While ADP is NP-complete in general, the paper shows that if the number of paths $k$ is fixed and the graph is acyclic, the problem can be solved efficiently using dynamic programming. This is a common theme in complexity theory: fixing parameters can make hard problems tractable.

Key Results

  • ADP is NP-complete: Proven via reduction from the independent set problem. This holds even for directed acyclic graphs.
  • SFP is $\Sigma_2^P$-complete: Proven via reduction from $\Sigma_2$SAT. This also holds for directed acyclic graphs.
  • Unbounded Duality Gap: Demonstrated with a specific graph construction ($P_k$) showing the gap can be arbitrarily large.
  • Zero Duality Gap (Special Case): If the graph has an $s-t$ cut with only one outgoing arc, ADP and SFP become strongly dual, and both problems can be solved in polynomial time.
  • Polynomial Time for Constant $k$ (Acyclic Graphs): A dynamic programming algorithm is presented that solves ADP in polynomial time when $k$ is fixed and the graph is acyclic.

Limitations and Future Work

  • Complexity for General Graphs (Constant $k$): While ADP is polynomial for constant $k$ on acyclic graphs, the paper mentions adapting this for general graphs, implying it might be more complex or have higher polynomial overhead.
  • Undirected Graphs: The paper focuses on directed graphs. The complexity and behavior of ADP and SFP on undirected graphs are left open.
  • More Than One Arc in Common: The paper briefly mentions that allowing paths to share more than one arc (i.e., $l$ arcs in common) also results in NP-hard problems, but a detailed analysis is not provided.
  • Practical Applications: While the motivation comes from practical applications, the theoretical focus means direct algorithmic implementations for real-world routing systems are not presented.
  • Classes of Graphs for Strong Duality: The paper identifies one class of graphs (single outgoing arc cut) where ADP and SFP are strongly dual. Exploring other such graph classes is a natural direction for future work.

Summary updated

BibTeX
@misc{bachtler2022almost,
  author = {Oliver Bachtler and Tim Bergner and Sven O. Krumke},
  title = {{Almost Disjoint Paths and Separating by Forbidden Pairs}},
  year = {2022},
  doi = {10.2139/ssrn.4289701},
  howpublished = {SSRN},
}
Figure