Discrete-time treatment number

Basic Information

• Paper ID: 2408.05313
• Title: Discrete-time treatment number
• Authors: 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)
• Classification: math.CO (Combinatorics), physics.soc-ph (Sociophysics)
• Publication Date: October 13, 2025
• Paper Link: https://arxiv.org/abs/2408.05313v2

Abstract

This paper introduces the concept of the discrete-time treatment number for graphs, where each vertex exists in one of three states at any given time step: compromised, vulnerable, or treated. This treatment number differs from other graph search parameters that use only two states, such as the firefighter problem or the inspection number of Bernshteyn and Lee. Vertices represent individuals, and edges exist between individuals who have close contact. Each vertex initially starts in the compromised state and may become compromised again even after treatment. The objective is to treat the entire population such that at the final time step no member is in a vulnerable or compromised state, while minimizing the maximum number of treatments occurring at each time step.

Research Background and Motivation

Problem Context

The core problem studied in this paper concerns the dynamic process of controlling contamination effects in networks. It is a deterministic graph process that models the race between treatment and the potential re-compromise of vertices.

Practical Application Scenarios

The paper provides three concrete interpretive applications:

1. Classroom Management Scenario: Students exist in three states—focused (green), losing attention (yellow), or distracted (red)—and teachers must devise strategies to ensure all students ultimately remain focused.
2. Spy Network: Spies may be loyal (green), considering becoming double agents (yellow), or compromised by the adversary (red), requiring meetings with handlers to maintain loyalty.
3. Medical Treatment: Corresponding to the SEIS epidemic model with susceptible (green), exposed (yellow), and infected (red) states, controlling infection spread through treatment.

Research Motivation

Existing graph search problems (such as the firefighter problem, node search, and inspection games) primarily employ two-state models, while this paper innovatively introduces a three-state model that better reflects real-world dynamic propagation processes.

Core Contributions

1. Introduction of a New Graph Parameter: Proposes the $(r,s)$-treatment number $\tau_{r,s}(H)$, where $r$ is the length of the protection period after treatment and $s$ is the duration of the vulnerable state.
2. Establishment of Upper Bound Theory: Proves that the treatment number is bounded above by $\lceil \frac{1+pw(H)}{r+s}\rceil$, where $pw(H)$ is the pathwidth of graph $H$.
3. Optimality of Cautious Protocols: Proves that for cautious treatment plans, the above upper bound is optimal.
4. Complete Analysis of the Special Case $(r=s=1)$:
   • Characterizes graphs with treatment number 1 (caterpillar graphs)
   • Proves that the treatment number of $n \times n$ grids is $\lceil\frac{1+n}{2}\rceil$
   • Provides important tools for proving lower bounds
5. Surprising Results on Subdivided Graphs: Proves that for any tree $T$, there exists a subdivision of $T$ with treatment number at most 2.

Methodology Details

Task Definition

Input: Connected graph $H = (V(H), E(H))$, protection period length $r \geq 1$, vulnerable period length $s \geq 1$

Output: $(r,s)$-treatment number $\tau_{r,s}(H)$

Constraints:

• Time step 0: All vertices are red (compromised)
• At each time step $t$: Select treatment set $A_t \subseteq V(H)$
• State transition rules: Protection lasts $r$ steps after treatment, vulnerable state lasts $s$ steps
• Goal: There exists time step $N$ such that $G_N = V(H)$ (all vertices are green)

Model Architecture

State Transition Mechanism

The paper defines precise state transition rules (see Table 1):

1. Green Vertex Classification: $G_t = G^r_t \cup G^{r-1}_t \cup \cdots \cup G^1_t$
2. Yellow Vertex Classification: $Y_t = Y^s_t \cup Y^{s-1}_t \cup \cdots \cup Y^1_t$
3. Transition Rules:
   • Treated vertices enter $G^r_t$
   • Protection period decreases: $G^i_t \to G^{i-1}_{t+1}$
   • Compromised neighbors cause: $G^1_t \to Y^s_{t+1}$ (if not re-treated)
   • Vulnerable period decreases: $Y^i_t \to Y^{i-1}_{t+1}$
   • Final transition to red: $Y^1_t \to R_{t+1}$

Protocol Type Classification

Minimal Protocols (Definition 2.7): Avoid unnecessary treatments Monotone Protocols (Definition 3.5): Once treated, vertices never become red again Cautious Protocols (Definition 3.7): Between first and last treatment, treat at least once in every consecutive $r+s$ time steps

Technical Innovations

1. Three-State Model: Compared to traditional two-state models, more accurately simulates gradual degradation processes in reality.
2. Pathwidth Connection: Establishes profound connections between treatment number and graph structural parameters (pathwidth).
3. Protocol Classification Theory: Systematically analyzes properties and relationships among different protocol types.
4. Subdivision Graph Theory: Discovers that subdivision operations can reduce treatment number, which is counterintuitive in graph search theory.

Experimental Setup

Theoretical Verification Examples

The paper primarily verifies results through theoretical analysis and concrete graph examples:

1. $(1,1)$-Protocol for $K_{1,3}$: Demonstrates a protocol of width 1
2. Petersen Graph: Proves treatment number equals 3
3. $4 \times 4$ Grid: Demonstrates pathwidth decomposition method
4. Subdivision Construction: Shows subdivision of $P_4 \square P_4$

Evaluation Methods

• Upper Bound Proofs: Construct protocols via pathwidth decomposition
• Lower Bound Proofs: Use vertex isoperimetric values and tools from Theorem 4.4
• Optimality Verification: Prove cautious protocols achieve the upper bound

Experimental Results

Main Theoretical Results

1. General Upper Bound (Theorem 3.4): $\tau_{r,s}(H) \leq \left\lceil \frac{1+pw(H)}{r+s}\right\rceil$
2. Lower Bound for Cautious Protocols (Theorem 3.10): $\text{width}(J) \geq \left\lceil \frac{1+pw(H)}{r+s}\right\rceil$
3. Exact Values for Grids (Theorem 4.7): $\tau(P_n \square P_n) = \left\lceil\frac{n+1}{2}\right\rceil$
4. Characterization of Graphs with Treatment Number 1 (Theorem 4.3): For a graph $H$ containing at least one edge, $\tau(H) = 1$ if and only if $H$ is a caterpillar graph.

Surprising Results on Subdivided Graphs

Main Theorem (Corollary 5.8): For any tree $T$, there exists a subdivision of $T$ with treatment number at most 2.

This result is particularly surprising because:

• Trees of arbitrarily large pathwidth exist
• Yet through appropriate subdivision, the treatment number can always be reduced to 2

Specific Computational Examples

• Petersen Graph: $\tau(\text{Petersen}) = 3$
• Cycle Graphs: $\tau(C_n) = 2$ for $n \geq 3$
• $K'_{1,3}$ (subdivision of $K_{1,3}$): $\tau(K'_{1,3}) = 2$

Related Work

Comparison with Graph Search Problems

1. Firefighter Problem: Vertices remain colored once marked, whereas this paper allows re-compromise
2. Node Search: Focuses on edge clearing, whereas this paper focuses on vertex states
3. Inspection Games: Seeks intruders, whereas this paper treats the entire network

Relationship with Inspection Number

Bernshteyn and Lee proved that the inspection number is bounded above by $1 + pw(H)$, while this paper's bound $\lceil \frac{1+pw(H)}{r+s}\rceil$ is tighter when $r+s > 1$.

Conclusions and Discussion

Main Conclusions

1. Complete Theoretical Framework: Establishes a comprehensive theoretical framework for the discrete-time treatment model
2. Central Role of Pathwidth: Reveals the fundamental importance of pathwidth in treatment problems
3. Unexpected Properties of Subdivided Graphs: Discovers the powerful effect of subdivision operations in reducing treatment number

Limitations

1. Computational Complexity: The paper does not discuss the algorithmic complexity of computing treatment number
2. Stochastic Models: Only considers deterministic models, does not address stochastic propagation
3. Practical Validation: Lacks verification on real network data

Future Directions

The paper proposes six open problems in Section 6:

1. Time Step Optimization (Question 6.1)
2. Characterization of Width 1 Protocols (Question 6.2)
3. Parameter Symmetry: $\tau_{r,s}(H) = \tau_{s,r}(H)$? (Question 6.3)
4. Treatment Number of Minimal Trees (Question 6.4)
5. General Theory of Subdivided Graphs (Question 6.5)
6. Relationship with Cops and Robbers Games (Question 6.6)

In-Depth Evaluation

Strengths

1. Theoretical Depth: Establishes a complete mathematical theoretical framework with rigorous proofs
2. Novelty: The three-state model represents an important extension to existing graph search theory
3. Practical Value: The model is applicable to epidemic control, network security, and other practical problems
4. Unexpected Discoveries: The subdivision graph results defy intuition and possess significant theoretical value

Weaknesses

1. Missing Algorithms: Lacks concrete algorithms for computing treatment number
2. Insufficient Experimental Validation: Primarily theoretical analysis, lacks experiments on real networks
3. Lack of Parameter Selection Guidance: Provides no guidance on how to choose $r$ and $s$ in practical applications

Impact

1. Theoretical Contribution: Opens new directions in graph search theory
2. Interdisciplinary Value: Connects combinatorics, network science, and epidemiology
3. Potential for Follow-up Research: The proposed open problems provide clear directions for future research

Applicable Scenarios

1. Epidemic Control: Optimization of vaccination strategies
2. Network Security: Control of malware propagation
3. Social Networks: Information dissemination management
4. Educational Management: Classroom attention maintenance strategies

References

The paper cites 18 relevant references, primarily including:

• Bernshteyn & Lee (2022): Inspection game theory
• Bodlaender (1998): Pathwidth theory
• Bonato (2022): Survey on pursuit-evasion games
• Finbow & MacGillivray (2009): Survey on firefighter problem

These references provide important support for the theoretical foundations of this paper.