Eventful graphs: the computational complexity of recognizing and realizing properties in changing networks

Abstract

Graph theory and computational complexity are two foundational fields of theoretical computer science. Graphs are excellent models of many real-world systems, but are classically static, whereas the real world changes over time (by design, by nature, or by accident).
This thesis explores the computational complexity of problems on so-called eventful graphs: that is, graphs which have in some way been extended to express the changeability of the systems they seek to model. A recurring theme throughout this work is the increase in difficulty which results directly from the eventfulness of our models.
The first chapter is an introduction to the thesis, in which we introduce the general themes of the thesis (namely, eventful graphs and computational complexity) and informally describe the subjects of later chapters.
Payment scheduling in the Interval Debt Model studies financial networks in which entities are interconnected by debts and the aim is to compute when they should pay one another to optimize some objective (e.g., minimize bankruptcies).
Temporal Reachability Dominating Sets: contagion in temporal graphs considers the problem of finding (or preventing) small sets of vertices which collectively reach all other vertices in temporal graphs, a well-studied eventful graph model in which edges appear and disappear over time.
In Reconfigurable Routing in Data Center Networks, we examine a problem motivated by new technology in interconnection networks, which enables the rewiring of data centers on-the-fly to serve fluctuating demands.
Detours and Distractions is an assortment of smaller subchapters on various topics: Maximal Independent Sets and Boolean Networks examines a generalization of a classic graph algorithm through the lens of Boolean Networks (also well-studied eventful graphs); Better Late, then? Delaying connections in temporal graphs considers a temporal graph problem motivated by train delays; Partial Domination delves deeper into some computational complexity questions arising from Chapter 4; and A nifty Constraint Satisfaction Problem is dedicated to a proof that a particular combinatorial problem is NP-complete.