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

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