2025-11-10T02:43:56.514804

Discrete-time treatment number

Clarke, Collins, Messinger et al.

We introduce the discrete-time treatment number of a graph, in which each vertex is in exactly one of three states at any given time-step: compromised, vulnerable, or treated. Our treatment number is distinct from other graph searching parameters that use only two states, such as the firefighter problem or Bernshteyn and Lee's inspection number. Vertices represent individuals and edges exist between individuals with close connections. Each vertex starts out as compromised; it can become compromised again even after treatment. Our objective is to treat the entire population so that at the last time-step, no members are vulnerable or compromised, while minimizing the maximum number of treatments that occur at each time-step. This minimum is the treatment number, and it depends on the choice of a pre-determined length of time $r$ that a vertex can remain in a treated state and length of time $s$ that a vertex can remain in a vulnerable state without being treated again. We denote the pathwidth of graph $H$ by $pw(H)$ and prove that the treatment number of $H$ is bounded above by $\lceil \frac{1+pw(H)}{r+s}\rceil$. This equals the best possible lower bound for a cautious treatment plan, defined as one in which each vertex, after being treated for the first time, is treated again within every consecutive $r+s$ time-steps until its last treatment. However, many graphs admit a plan that is not cautious. When $r=s=1$, we find a useful tool for proving lower bounds, show that the treatment number of an $n\times n$ grid equals $\lceil\frac{1+n}{2}\rceil$, characterize graphs that require only one treatment per time-step, and prove that subdividing one edge can reduce the treatment number. It is known that there are trees with arbitrarily large pathwidth; surprisingly, we prove that for any tree $T$, there is a subdivision of $T$ that requires at most two treatments per time-step.

academic

離散時間治療数

基本情報

論文ID: 2408.05313
タイトル: Discrete-time treatment number
著者: N.E. Clarke (Acadia University)、K.L. Collins (Wesleyan University)、M.E. Messinger (Mt. Allison University)、A.N. Trenk (Wellesley College)、A. Vetta (McGill University)
分類: math.CO（組合数学）、physics.soc-ph（社会物理学）
発表日: 2025年10月13日
論文リンク: https://arxiv.org/abs/2408.05313v2

概要

本論文は、グラフの離散時間治療数（discrete-time treatment number）の概念を導入している。各頂点は任意の時間ステップにおいて、侵害状態（compromised）、脆弱状態（vulnerable）、治療済み状態（treated）の3つの状態のいずれかにある。この治療数は、消防士問題やBernshteynおよびLeeの検査数など、2つの状態のみを使用する他のグラフ探索パラメータとは異なる。頂点は個人を表し、辺は密接な関係を持つ個人間に存在する。各頂点は初期状態では侵害状態であり、治療後も再び侵害される可能性がある。目標は全集団を治療することであり、最終時間ステップで誰も脆弱状態または侵害状態にないようにしながら、各時間ステップで発生する最大治療回数を最小化することである。

研究背景と動機

問題の背景

本論文が研究する中核的な問題は、ネットワーク内の汚染影響を制御する動的プロセスである。これは治療と頂点が再び破壊される可能性との間の競争をシミュレートする確定的グラフプロセスである。

実際の応用シナリオ

論文は3つの具体的な応用解釈を提供している：

教室管理シナリオ: 学生は集中状態（緑色）、注意散漫状態（黄色）、または気が散った状態（赤色）の3つの状態にあり、教師はすべての学生が最終的に集中するための戦略を策定する必要がある。
スパイネットワーク: スパイは忠誠的（緑色）、二重スパイになることを検討中（黄色）、または対方に買収された（赤色）の状態にあり、スパイマスターとの会合を通じて忠誠心を維持する必要がある。
医学的治療: SEIS流行病モデルの易感染性（緑色）、暴露（黄色）、感染（赤色）状態に対応し、治療を通じて感染伝播を制御する。

研究動機

既存のグラフ探索問題（消防士問題、ノード探索、検査ゲーム問題など）は主に2状態モデルを使用しているが、本論文は革新的に3状態モデルを導入し、現実の動的伝播プロセスにより適合している。

核心的貢献

新しいグラフパラメータの導入: $(r,s)$ -治療数 $\tau_{r,s}(H)$ を提案した。ここで $r$ は治療保護期間の長さ、 $s$ は脆弱状態の継続期間の長さである。
上界理論の確立: 治療数の上界が $\lceil \frac{1+pw(H)}{r+s}\rceil$ であることを証明した。ここで $pw(H)$ はグラフ $H$ のパス幅である。
慎重なプロトコルの最適性: 慎重な治療計画に対して、上記の上界が最適であることを証明した。
特殊ケース $(r=s=1)$ の完全な分析:
- 治療数が1のグラフ（毛虫グラフ）を特性化した
- $n \times n$ グリッドの治療数が $\lceil\frac{1+n}{2}\rceil$ であることを証明した
- 下界を証明するための重要なツールを提供した
細分グラフの驚くべき結果: 任意の木 $T$ に対して、 $T$ の細分グラフが存在し、その治療数は最大2であることを証明した。

方法の詳細

タスク定義

入力: 連結グラフ $H = (V(H), E(H))$ 、保護期間の長さ $r \geq 1$ 、脆弱期間の長さ $s \geq 1$

出力: $(r,s)$ -治療数 $\tau_{r,s}(H)$

制約条件:

時間ステップ0: すべての頂点は赤色（侵害状態）
各時間ステップ $t$ : 治療集合 $A_t \subseteq V(H)$ を選択
状態遷移規則: 治療後 $r$ ステップ保護、脆弱状態は $s$ ステップ継続
目標: 時間ステップ $N$ が存在して $G_N = V(H)$ （すべての頂点が緑色）

モデルアーキテクチャ

状態遷移メカニズム

論文は正確な状態遷移規則を定義している（表1参照）:

緑色頂点の分類: $G_t = G^r_t \cup G^{r-1}_t \cup \cdots \cup G^1_t$
黄色頂点の分類: $Y_t = Y^s_t \cup Y^{s-1}_t \cup \cdots \cup Y^1_t$
遷移規則:
- 治療された頂点は $G^r_t$ に進む
- 保護期間は段階的に減少: $G^i_t \to G^{i-1}_{t+1}$
- 侵害された隣接点は以下を引き起こす: $G^1_t \to Y^s_{t+1}$ （再治療されない場合）
- 脆弱期間は減少: $Y^i_t \to Y^{i-1}_{t+1}$
- 最終的に赤色に: $Y^1_t \to R_{t+1}$

プロトコルタイプの分類

最小プロトコル（定義2.7）: 不要な治療を回避 単調プロトコル（定義3.5）: 頂点が一度治療されると再び赤色にならない 慎重なプロトコル（定義3.7）: 最初の治療と最後の治療の間で、連続する $r+s$ 個の時間ステップごとに少なくとも1回治療

技術的革新点

3状態モデル: 従来の2状態モデルと比較して、現実の段階的な劣化プロセスをより正確にシミュレートする。
パス幅との関連性: 治療数とグラフ構造パラメータ（パス幅）の深い関連性を確立した。
プロトコル分類理論: 異なるタイプのプロトコルの性質と相互関係を体系的に分析した。
細分グラフ理論: 細分操作が治療数を低減できることを発見した。これはグラフ探索理論では反直感的である。

実験設定

理論検証の例

論文は主に理論分析と具体的なグラフ例を通じて結果を検証している：

$K_{1,3}$ の $(1,1)$ -プロトコル: 幅1のプロトコルを示す
Petersen グラフ: 治療数が3であることを証明
$4 \times 4$ グリッド: パス分解方法を実演
細分グラフ構成: $P_4 \square P_4$ の細分を示す

評価方法

上界証明: パス分解を通じたプロトコル構成
下界証明: 頂点等周値とTheorem 4.4のツールを使用
最適性検証: 慎重なプロトコルが上界に達することを証明

実験結果

主要な理論的結果

一般的な上界（定理3.4）: $\tau_{r,s}(H) \leq \left\lceil \frac{1+pw(H)}{r+s}\right\rceil$
慎重なプロトコルの下界（定理3.10）: $\text{width}(J) \geq \left\lceil \frac{1+pw(H)}{r+s}\right\rceil$
グリッドの正確な値（定理4.7）: $\tau(P_n \square P_n) = \left\lceil\frac{n+1}{2}\right\rceil$
治療数が1のグラフの特性化（定理4.3）: 少なくとも1つの辺を含むグラフ $H$ に対して、 $\tau(H) = 1$ 当且つつ $H$ が毛虫グラフである。