Ing. Michal Dvořák

  • Profile
  • Publications

Publications

On the Complexity of Target Set Selection in Simple Geometric Networks

Authors
Dvořák, M.; Knop, D.; Schierreich, Š.
Year
2024
Published
Discrete Mathematics and Theoretical Computer Science. 2024, 26(2), 1-26. ISSN 1365-8050.
Type
Article
Annotation
We study the following model of disease spread in a social network. At first, all individuals are either infected or healthy. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbors are already infected. We represent the social network as a graph. Inspired by the real-world restrictions in the recent epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph classes, such as interval graphs and grid graphs.

Establishing Herd Immunity is Hard Even in Simple Geometric Networks

Year
2023
Published
Proceedings of the 18th Workshop on Algorithms and Models for the Web Graph. Cham: Springer, 2023. p. 68-82. Lecture Notes in Computer Science. vol. 13894. ISSN 0302-9743. ISBN 978-3-031-32295-2.
Type
Proceedings paper
Annotation
We study the following model of disease spread in a social network. In the beginning, all individuals are either ``infected'' or ``healthy''. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbours are already infected. We represent the social network as a graph. Inspired by the real-world restrictions in the current epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph families, such as interval graphs and grid graphs.