Restricting infections on graphs: immunization problems

Abstract

Consider a graph G in which cv(τ) ∈ {0,1} denotes the state of the vertex v ∈ V(G) at a given time τ ∈ N. If cv(τ) = 0, we say that vertex v is inactive or uninfected at time τ; otherwise, we say that v is active or infected at time τ. A collection of states Cτ = (cv(τ))v∈V(G) is said to be a configuration of G at time τ. A sequence of configurations P = (Cτ)τ∈N of G is called a discrete dynamic process on G. Given a graph G, a function t : V(G) → N that assigns to each vertex v of G a value called the threshold of v, and a set S ⊆ V(G) of initially infected vertices, we say that P = It(G,S) is a t-irreversible process in G if P is a discrete dynamical process in G such that, for all v ∈V(G), we have that cv(0) = 1 if and only if v ∈ S and cv(τ +1) = 1 if and only if |{u ∈ NG(v) | cu(τ) = 1}| ≥ t(v). In other words, in a t-irreversible process P = It(G,S), we start with all the vertices of S infected at time τ = 0 and, at each successive time step, an uninfected vertex v becomes infected if it has at least its threshold t(v) of neighbors infected at the previous time step. Furthermore, once a vertex is infected, it remains infected. We say that the process ends when no more vertices can be infected. Irreversible processes are used to model various phenomena, including the spread of (dis-)information and contagious diseases. Irreversible t-processes are widely studied in the literature, mainly with the aim of finding a set of initially infected vertices that satisfies some criterion. This criterion is usually to maximize the number of infected vertices; or to minimize the time needed to infect all vertices; among other similar ones. In contexts of contagion and diffusion such as those mentioned above, however, it becomes natural to think about how to contain the infection, that is, to restrict the number of infected vertices at the end of the process to a small set. We do this through what we call vertex immunization. An immunized vertex cannot be infected and does not contribute to infecting other vertices. (CORDASCO et al., 2023) introduced the problem INFLUENCE IMMUNIZATION BOUNDING (IIB) in which, given a t-irreversible process P = It(G,S) and naturals k and `, the goal is to find a set Y ⊆ V(G) of vertices to be immunized such that |Y| ≤ ` and the number of infected vertices at the end of the process is at most k. We say that Y is a k-restricting set. In the same paper, the authors showed that the problem is W[1]-hard and W[2]-hard parameterized by some parameters, including k, `, the treewidth of the graph and the neighborhood diversity of the graph. They also showed some FPT algorithms parameterized by combinations of these parameters. In this work, we study IIB on several classes of graphs. For bipartite and split graphs, we show that the problem remains W[2]-hard parameterized by `. We also show that IIB is NP-complete even for subcubic bipartite planar graphs. For trees, we conjecture that the problem also remains NP-complete. For complete graphs where the thresholds of all vertices are equal, we show how to find a minimum k-restricting set. We also show some upper bounds for the size of a k-restricting set for paths, trees, planar and outerplanar graphs and other classes of graphs when k is large enough and the subgraph induced by S is connected.