Parameterized Complexity of Network Dynamics

 

Description:

During the COVID-19 pandemic, we have observed the virus spreading through the network of physical human contacts in complex ways.  Apart from uncertainty about the data and the dynamics, there is another important challenge, and it is the one that we will deal with in this subproject: Even in an idealized situation where we have perfect knowledge of the network as well as of the local rules governing the network's dynamics, the random process can exhibit a behavior of emergent complexity. This means that the behavior is difficult to predict other than by a costly simulation, either because doing so is inherently intractable for reasons that have to do with the computational complexity of the task at hand, or simply because the scientific theory of network dynamics has not been developed far enough yet.  While the subproject is motivated by the COVID-19 pandemic, the results we aim to achieve will generalize to opinion dynamics, Glauber dynamics, graph neural networks, and more.

 

Staff:

 

Publications:

  1. Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer and Manuel Penschuck.
    PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM).
    In 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands 285. 2023, 37:1–37:7.
    URL, DOI BibTeX

    @inproceedings{DBLP:conf/iwpec/LeonhardtDHKM0P23,
	author = "Alexander Leonhardt and Holger Dell and Anselm Haak and Frank Kammer and Johannes Meintrup and Ulrich Meyer and Manuel Penschuck",
	title = "{PACE} Solver Description: Exact {(GUTHMI)} and Heuristic {(GUTHM)}",
	booktitle = "18th International Symposium on Parameterized and Exact Computation, {IPEC} 2023, September 6-8, 2023, Amsterdam, The Netherlands",
	series = "LIPIcs",
	volume = 285,
	pages = "37:1--37:7",
	year = 2023,
	url = "https://doi.org/10.4230/LIPIcs.IPEC.2023.37",
	doi = "10.4230/LIPICS.IPEC.2023.37",
	timestamp = "Wed, 13 Dec 2023 17:20:21 +0100",
	biburl = "https://dblp.org/rec/conf/iwpec/LeonhardtDHKM0P23.bib"
}