Menger's Theorem for Temporal Paths (Not Walks)

Basic Information

• Paper ID: 2206.15251
• Title: Menger's Theorem for Temporal Paths (Not Walks)
• Authors: Allen Ibiapina (Universidade Federal do Ceará), Raul Lopes (LAMSADE, Université Paris-Dauphine & École normale supérieure de Paris), Andrea Marino (Università degli Studi di Firenze), Ana Silva (Universidade Federal do Ceará)
• Classification: cs.DM (Discrete Mathematics), math.CO (Combinatorics)
• Publication Date: June 2022 (arXiv v4: October 2025)
• Paper Link: https://arxiv.org/abs/2206.15251

Abstract

This paper investigates Menger's theorem in temporal graphs, which are graph structures where edges are only available at specific times. The article defines temporal paths as temporal walks that do not allow any vertex repetition at any time point, which represents an important distinction from temporal walks in previous work. The research focuses on connectivity problems between vertex pairs (maximum number of vertex-disjoint paths) and robustness problems (minimum cut size). The main result demonstrates that Menger's theorem holds when the maximum number of temporally vertex-disjoint temporal paths equals 1.

Research Background and Motivation

Problem Definition

1. Core Problem: Investigating various variants of Menger's theorem in temporal graphs, particularly the relationship between temporally vertex-disjoint paths and cuts
2. Significance: Temporal graphs have important applications in multi-agent path finding (MAPF), dynamic network analysis, and related fields
3. Existing Limitations:
   • Classical results from static graphs cannot be directly generalized to temporal graphs
   • Previous work conflated the concepts of temporal paths and temporal walks
   • Lack of comprehensive understanding of Menger's theorem completeness in temporal graphs

Research Motivation

• Filling important gaps in temporal graph theory
• Providing theoretical foundations for multi-agent systems
• Clarifying the fundamental distinction between temporal paths and temporal walks

Core Contributions

1. Clear Distinction Between Temporal Paths and Temporal Walks: First rigorous differentiation of these two concepts, correcting confusion in previous literature
2. Complete Complexity Analysis: Providing complexity results for all problem variants (Tables 1 and 2)
3. Main Theoretical Result: Proving that Menger's theorem holds when tp(s,t)=1 (tp(s,t)=tpc(s,t))
4. Algorithmic Contributions:
   • Polynomial-time algorithm for finding 2 temporally vertex-disjoint paths
   • Parameterized algorithm for solving h-temporal vertex path-cut problems
5. Reduction Techniques: Establishing polynomial-time reduction from strict to non-strict models

Methodology Details

Task Definition

Temporal Graph: G = (G, λ), where G is the underlying graph and λ is a time-labeling function mapping each edge to a subset of τ

Key Concepts:

• Temporal Path: A temporal walk without vertex repetition
• Temporally Vertex-Disjoint: Two paths do not pass through the same vertex at the same time
• Temporal Vertex Cut: A set of temporal vertices that breaks all s,t-paths
• Core Problems:
  • tp_G(s,t): Maximum number of temporally vertex-disjoint s,t-paths
  • tpc_G(s,t): Minimum temporal vertex s,t-cut size

Theoretical Framework

1. Reduction from Strict to Non-Strict Models (Theorem 2)

Constructs a reduction from the strict model to the non-strict model preserving temporal vertex-disjointness:

• For each temporal edge (xy,i), add auxiliary vertices w^i_xy and w^i_yx
• Time-labeling transformation: i → 2i and 2i+1
• Establish bijection f: P*{G,λ}(s,t) → P{G',λ'}(s,t)

2. Menger's Theorem for Temporally Vertex-Disjoint Walks (Theorem 3)

Using static expansion technique to prove: tw(s,t) = twc(s,t), computable in polynomial time

3. Main Theoretical Result (Theorem 11)

Core Theorem: tp(s,t) = 1 if and only if tpc(s,t) = 1

Proof Strategy:

• Proof by contradiction: Assume a minimal counterexample G, s, t where tp(s,t) = 1 < tpc(s,t)
• Analyze structural properties of minimum temporal vertex cuts
• Through concepts of extremal cuts and good/bad vertices analysis
• Construct contradiction, proving no such counterexample exists

Technical Innovations

1. Concept Clarification: First rigorous distinction between temporal paths and walks, correcting conceptual confusion in Mertzios et al.'s work
2. Structured Analysis: Introducing extremal cuts and good/bad vertices concepts for systematic temporal graph analysis
3. Reduction Preservation: Designing reduction techniques that preserve all relevant parameters
4. Algorithm Design: Efficient polynomial-time algorithm for the k=2 case

Experimental Setup

This is primarily a theoretical work without traditional experimental setup. Theoretical analysis includes:

Complexity Analysis

• NP-Completeness Proofs: Proving NP-completeness of k-temporal vertex-disjoint paths through reduction from (2,2,3)-SAT
• Parameterized Complexity: Analyzing complexity with respect to different parameters

Constructive Proofs

• Providing concrete counterexample constructions (Figure 3)
• Proving that the difference tpc(s,t) - tp(s,t) can be arbitrarily large

Experimental Results

Main Results

Complexity Results Summary (Tables 1 and 2)

Non-Strict Case:

• Vertex-Disjoint: NP-complete for k≥2
• Temporally Vertex-Disjoint Walks: Polynomial-time solvable
• Temporally Vertex-Disjoint Paths:
  • Polynomial-time solvable for k=1,2
  • NP-complete for undirected graphs in general
  • NP-complete for directed graphs when k≥3

Strict Case:

• Most results inherited from non-strict case through Theorem 2 reduction

Algorithmic Results

1. Polynomial Algorithm for k=2 (Theorem 29):
   • Time Complexity: O(mnτ²)
   • Based on construction and analysis of s,t-minimal graphs
2. Parameterized Algorithm (Corollary 25):
   • h-temporal vertex path-cut: O((hnτ)^h) time
   • XP algorithm parameterized by cut size

Theoretical Findings

1. Criticality of Menger's Theorem: Holds only when tp(s,t)=1
2. Parameter Divergence: Constructed examples where tpc(s,t)-tp(s,t) is arbitrarily large
3. Algorithm Reachability: k=2 is the maximum value for polynomial solvability

Related Work

Main Research Directions

1. Temporal Graph Foundations:
   • Kempe, Kleinberg, Kumar (2002): Earliest temporal connectivity research
   • Berman (1996): NP-completeness of vertex-disjoint paths
2. Temporal Path Problems:
   • Mertzios, Michail, Spirakis (2019): Temporally vertex-disjoint "paths" (actually walks)
   • Klobas et al. (2021-2023): Temporal disjoint paths in specific graph structures
3. Parameterized Complexity:
   • Zschoche et al. (2020): Parameterized analysis of temporal cut problems
   • Fluschnik et al. (2020): Temporal separator problems

Advantages of This Work

1. Conceptual Clarity: First rigorous distinction between paths and walks
2. Completeness: Providing complete complexity landscape for all variants
3. Theoretical Depth: Precise characterization of Menger's theorem in temporal graphs

Conclusions and Discussion

Main Conclusions

1. Core Theoretical Result: Menger's theorem in temporal graphs holds only when the maximum path count equals 1
2. Complexity Boundary: k=2 is the boundary for polynomial solvability of temporal vertex-disjoint path problems
3. Algorithmic Contribution: Providing practical parameterized algorithms

Limitations

1. Application Scope: Theoretical results primarily applicable to specific temporal graph models
2. Algorithm Efficiency: Constant factors in certain algorithms may be large
3. Practical Validation: Lack of verification on large-scale real data

Future Directions

The paper proposes four open problems:

1. Complexity of 2 vertex-disjoint paths in non-strict case
2. Complexity of 3 temporally vertex-disjoint paths in strict directed graphs
3. Minimum lifetime problem in strict models
4. Menger's theorem for edge-disjoint version

In-Depth Evaluation

Strengths

1. Significant Theoretical Contributions:
   • Clarifies important conceptual confusion
   • Provides complete complexity analysis
   • Delivers elegant theoretical results
2. High Technical Quality:
   • Rigorous and complete proofs
   • Sophisticated reduction techniques
   • Well-designed algorithms
3. Clear Presentation:
   • Accurate concept definitions
   • Well-organized results
   • Effective table summaries

Weaknesses

1. Limited Practical Applicability:
   • Primarily theoretical results
   • Lacks practical application verification
   • Insufficient algorithm implementation details
2. Complex Proofs:
   • Theorem 11 proof is lengthy
   • Some technical details could be simplified

Impact

1. Academic Value: Establishes important foundations for temporal graph theory
2. Application Potential: Provides theoretical support for practical problems like MAPF
3. Future Research: Initiates systematic study of classical graph theory problems in temporal graphs

Applicable Scenarios

1. Multi-Agent Path Planning: Robot collision-avoidance path design
2. Dynamic Network Analysis: Connectivity analysis in social networks and transportation networks
3. Theoretical Computer Science: Graph algorithms and complexity theory research

References

Important references include:

• Menger (1927): Classical Menger's theorem
• Kempe, Kleinberg, Kumar (2002): Temporal network connectivity
• Mertzios, Michail, Spirakis (2019): Temporal optimization problems
• Berman (1996): Scheduling network vulnerability
• Klobas et al. (2021-2023): Temporal disjoint paths

This paper represents an important contribution to temporal graph theory, clarifying fundamental concepts through rigorous mathematical analysis, establishing complete complexity theory, and laying solid foundations for further development in this field.