Establishing Herd Immunity is Hard Even in Simple Geometric Networks

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00363799" target="_blank" >RIV/68407700:21240/23:00363799 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/978-3-031-32296-9_5" target="_blank" >https://doi.org/10.1007/978-3-031-32296-9_5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-32296-9_5" target="_blank" >10.1007/978-3-031-32296-9_5</a>

Result language

angličtina

Original language name

Establishing Herd Immunity is Hard Even in Simple Geometric Networks

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA22-19557S" target="_blank" >GA22-19557S: New Frontiers in Computational Social Choice</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 18th Workshop on Algorithms and Models for the Web Graph

ISBN

978-3-031-32295-2

ISSN

0302-9743

e-ISSN

1611-3349

Number of pages

15

Pages from-to

68-82

Publisher name

Springer

Place of publication

Cham

Event location

Toronto

Event date

May 23, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—