On the complexity of Min-Max Star Partitioning and firefighting, and the impact of selfish behavior in packet routing

This dissertation investigates three central problems in the realm of graph theory, combinatorial optimization, and algorithmic game theory. The focus lies on computational complexity, efficient algorithms, and the impact of selfish behavior in networks.

Star Partitioning:
We introduce a novel Star Partitioning problem, where the edges of a graph are partitioned into stars to minimize the maximum number of stars a node participates in, while respecting node-specific capacities.

Firefighting on Graphs:
We investigate a pursuit–evasion game, where a fire spreads across the nodes of a graph, and a limited number of firefighters try to extinguish it.

Selfish Behavior in Packet Routing:
We analyze a packet routing game with discrete time steps, where players select source-to-destination paths in networks with limited edge capacities. The social objective is to minimize the completion time, that is, the time it takes for the last player to reach the destination.