Parameterized Complexity of Network Dynamics

Applicant Professor Dr. Holger Dell
Subject Area Theoretical Computer Science
Term since 2023
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 411362735
 

Project Description

This project uses the vantage point of parameterized complexity theory to shed new light on problems that occur in network dynamics. The objectives include applying methods from structural graph theory to study the convergence time of rumor spreading and opinion dynamics in non-random networks, classifying the parameterized complexity of NP-hard problems related to inference, influence, and control problems in network dynamics, and extensions of these insights to dynamic environments using the notion of temporal graphs.
DFG Programme Research Units
Subproject of FOR 2975:  Algorithms, Dynamics, and Information Flow in Networks