2025-11-21T12:46:15.162143

Menger's Theorem for Temporal Paths (Not Walks)

Ibiapina, Lopes, Marino et al.

A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its (discretized) lifetime $Ï$. In this setting, we ask that walks respect the temporal aspect by defining $\textit{temporal walks}$ as sequences of adjacent edges whose appearing times are either strictly increasing or non-decreasing (here called non-strict), depending on the scenario. The notion of disjointness between walks is also not unique: two walks are $\textit{vertex-disjoint}$ if they do not share a vertex, and are $\textit{temporal vertex-disjoint}$ if they do not share a vertex at the same time. Thus a $\textit{temporal path}$ is a temporal walk where no repetition of vertices, at any time, is allowed. This is an important distinction that separates the interpretation of our results from those of previous works on the topic. In this paper we focus on various questions regarding connectivity (maximum number of disjoint paths) and robustness (minimum size of a cut) between a given pair of vertices. Such problems are related to the well-known Menger's Theorem on static graphs. We explore all possible interpretations of such problems, according to vertex and temporal vertex-disjointness, strict and non-strict temporal paths, and directed and undirected temporal graphs. We present a number of new results, the main of which states that Menger's Theorem holds when the maximum number of temporal vertex-disjoint temporal paths is equal to 1.

academic

時間的パスに対するメンガーの定理（ウォークではなく）

基本情報

論文ID: 2206.15251
タイトル: Menger's Theorem for Temporal Paths (Not Walks)
著者: Allen Ibiapina（セアラ連邦大学）、Raul Lopes（LAMSADE、パリ・ドーフィネ大学＆パリ高等師範学校）、Andrea Marino（フィレンツェ大学）、Ana Silva（セアラ連邦大学）
分類: cs.DM（離散数学）、math.CO（組合論）
発表時期: 2022年6月（arXiv v4: 2025年10月）
論文リンク: https://arxiv.org/abs/2206.15251

中核的問題: 時間的グラフにおけるメンガーの定理の様々な変種を研究し、特に時間的頂点不交パスとカットの関係を調査する
重要性: 時間的グラフは多エージェント経路計画（MAPF）、動的ネットワーク分析などの分野で重要な応用を持つ
既存の限界:
- 静的グラフの古典的結果は時間的グラフに直接拡張できない
- 先行研究は時間的パスと時間的ウォークの概念を混同している
- 時間的グラフにおけるメンガーの定理の完全性に関する理解が不足している

研究動機

時間的グラフ理論における重要な空白を埋める
多エージェントシステムに理論的基礎を提供する
時間的パスと時間的ウォークの根本的な違いを明確にする

核心的貢献

時間的パスと時間的ウォークの明確な区別: 初めてこれら2つの概念を厳密に区別し、先行文献における混同を是正
完全な複雑性分析: すべての変種問題の複雑性結果を提供（表1および表2）
主要な理論的結果: tp(s,t)=1の場合、メンガーの定理が成立することを証明（tp(s,t)=tpc(s,t)）
アルゴリズム的貢献:
- 2つの時間的頂点不交パスを見つけるための多項式時間アルゴリズムを提供
- h-temporal vertex path-Cut問題を解くためのパラメータ化アルゴリズムを提示
帰約技法: 厳密モデルから非厳密モデルへの多項式時間帰約を確立

方法論の詳細

タスク定義

時間的グラフ: G = (G, λ)。ここでGは基礎グラフ、λは時間標識関数で、各辺を時間集合τの部分集合にマッピング

主要概念:

時間的パス: 頂点を重複させない時間的ウォーク
時間的頂点不交: 2つのパスが同じ時間に同じ頂点を通過しない
時間的頂点カット: すべてのs,t-パスを破壊する時間的頂点集合

中核的問題:

tp_G(s,t): 最大時間的頂点不交s,t-パス数
tpc_G(s,t): 最小時間的頂点s,t-カット規模

理論的枠組み

1. 厳密から非厳密への帰約（定理2）

厳密モデルから非厳密モデルへの帰約を構成し、時間的頂点不交性を保持：

各時間的辺(xy,i)に対して、補助頂点w^i_xyおよびw^i_yxを追加
時間標識変換: i → 2iおよび2i+1
双射f: P*{G,λ}(s,t) → P{G',λ'}(s,t)を確立

2. 時間的頂点不交ウォークのメンガーの定理（定理3）

静的展開技術を使用して証明：tw(s,t) = twc(s,t)、かつ多項式時間で計算可能

3. 主要な理論的結果（定理11）

中核定理: tp(s,t) = 1 当且つ当のみ tpc(s,t) = 1

証明戦略:

背理法: 最小反例G, s, tが存在し、tp(s,t) = 1 < tpc(s,t)と仮定
最小時間的頂点カットの構造的性質を分析
極値カットの概念と良好/不良頂点の分析を通じて
矛盾を構成し、そのような反例が存在しないことを証明

技術的革新点

概念の明確化: 初めて時間的パスとウォークを厳密に区別し、Mertzios等の先行研究における概念的混同を是正
構造化分析: 極値カット、良好/不良頂点などの概念を導入し、時間的グラフ構造を体系的に分析
帰約の保持性: 設計された帰約技法がすべての関連パラメータを保持
アルゴリズム設計: k=2の場合に効率的な多項式時間アルゴリズムを設計

実験設定

本論文は主に理論的研究であり、従来の意味での実験設定を持たない。理論分析には以下が含まれる：

複雑性分析

NP完全性証明: (2,2,3)-SAT からの帰約を通じてk-temporal vertex-Disjoint pathsのNP完全性を証明
パラメータ化複雑性: 異なるパラメータに基づく複雑性を分析

構成的証明

具体的な反例構成を提供（図3）
差分tpc(s,t) - tp(s,t)が任意に大きくなることを証明

頂点不交: k≥2の場合NP完全
時間的頂点不交ウォーク: 多項式時間で解決可能
時間的頂点不交パス:
- k=1,2の場合多項式時間で解決可能
- 無向グラフの一般的な場合NP完全
- 有向グラフk≥3の場合NP完全

厳密の場合:

定理2の帰約を通じて、ほとんどの結果は非厳密の場合から継承

アルゴリズム結果

k=2の多項式アルゴリズム（定理29）:
- 時間計算量: O(mnτ²)
- s,t-最小グラフの構成と分析に基づく
パラメータ化アルゴリズム（系25）:
- h-temporal vertex path-Cut: O((hnτ)^h)時間
- カット規模でパラメータ化されたXPアルゴリズム