We study spreading processes in temporal graphs, i. e., graphs whose connections change over time. These processes naturally model real-world phenomena such as infectious diseases or information flows. More precisely, we investigate how such a spreading process, emerging from a given set of sources, can be contained to a small part of the graph. To this end we consider two ways of modifying the graph, which are (1) deleting connections and (2) delaying connections. We show a close relationship between the two associated problems and give a polynomial time algorithm when the graph has tree structure. For the general version, we consider parameterization by the number of vertices to which the spread is contained. Surprisingly, we prove W[1]-hardness for the deletion variant but fixed-parameter tractability for the delaying variant.
翻译:我们研究时间图中的扩展过程,即那些关联随时间而变化的图表。这些过程自然地模拟真实世界现象,例如传染病或信息流动。更准确地说,我们研究如何将从某一组来源产生的这种扩散过程控制在图的一小部分。我们为此考虑修改图的两种方法,即(1) 删除连接和(2) 延迟连接。我们显示了两个相关问题之间的密切关系,并在图形有树结构时给出一个多元时算法。对于一般版本,我们考虑按分布分布所容纳的脊椎数进行参数化。令人惊讶的是,我们证明了删除变量的W[1]-硬度,但延迟变量的固定参数可拉动性。