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

Discrete-time treatment number

基本信息

论文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）。该治疗数与其他仅使用两种状态的图搜索参数不同，如消防员问题或Bernshteyn和Lee的检查数。顶点代表个体，边存在于有密切联系的个体之间。每个顶点初始都是受损状态，即使在治疗后也可能再次受损。目标是治疗整个群体，使得在最后时间步没有成员处于脆弱或受损状态，同时最小化每个时间步发生的最大治疗次数。

研究背景与动机

问题背景

本文研究的核心问题是在网络中控制污染影响的动态过程。这是一个确定性图过程，模拟治疗与顶点可能再次被破坏之间的竞赛。

实际应用场景

论文提供了三个具体的应用解释：

教室管理场景：学生处于专注（绿色）、失去注意力（黄色）或分心（红色）三种状态，教师需要制定策略使所有学生最终专注。
间谍网络：间谍可能是忠诚的（绿色）、考虑成为双重间谍（黄色）或被对方收买（红色），需要通过与间谍头目会面来维持忠诚。
医学治疗：对应SEIS流行病模型中的易感（绿色）、暴露（黄色）和感染（红色）状态，通过治疗控制感染传播。

研究动机

现有的图搜索问题（如消防员问题、节点搜索、检查游戏问题）主要使用两状态模型，而本文创新性地引入了三状态模型，更贴近现实中的动态传播过程。

核心贡献

引入新的图参数：提出了 $(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}$

协议类型分类

最小协议（Definition 2.7）：避免不必要的治疗 单调协议（Definition 3.5）：顶点一旦治疗就不再变红 谨慎协议（Definition 3.7）：在首次和最后治疗之间，每连续 $r+s$ 个时间步中至少治疗一次

技术创新点

三状态模型：相比传统两状态模型，更准确地模拟了现实中的渐进式退化过程。
路径宽度联系：建立了治疗数与图结构参数（路径宽度）的深刻联系。
协议分类理论：系统分析了不同类型协议的性质和相互关系。
细分图理论：发现细分操作可以降低治疗数，这在图搜索理论中是反直觉的。

实验设置

理论验证实例

论文主要通过理论分析和具体图例验证结果：

$K_{1,3}$ 的 $(1,1)$ -协议：展示了宽度为1的协议
Petersen图：证明治疗数为3
$4 \times 4$ 网格：演示路径分解方法
细分图构造：展示 $P_4 \square P_4$ 的细分

评价方法

上界证明：通过路径分解构造协议
下界证明：使用顶点等周值和Theorem 4.4的工具
最优性验证：证明谨慎协议达到上界

实验结果

主要理论结果

一般上界（Theorem 3.4）： $\tau_{r,s}(H) \leq \left\lceil \frac{1+pw(H)}{r+s}\right\rceil$
谨慎协议下界（Theorem 3.10）： $\text{width}(J) \geq \left\lceil \frac{1+pw(H)}{r+s}\right\rceil$
网格的精确值（Theorem 4.7）： $\tau(P_n \square P_n) = \left\lceil\frac{n+1}{2}\right\rceil$
治疗数为1的刻画（Theorem 4.3）：对于包含至少一条边的图 $H$ ， $\tau(H) = 1$ 当且仅当 $H$ 是毛虫图。