Approximating temporal modularity on graphs of small underlying treewidth

As with the other papers in my PhD, this one concerns the detection of community structure in graphs. The difference is that we notice something new about reality: Time exists. Things change over time - new connections are added to our graphs. How does this affect the problem of detecting the community structure in said graph?

A priori, one should expect that this makes it considerably harder, since time adds an entirely new dimension, and a naïve approach would have to consider every time simultaneously. However, in this paper, we demonstrate that similar guarantees for when an approximate solution can be found in fact apply also in the temporal case, if we apply some extra tricks and new approximation results.

This paper was accepted at ALGOWIN 2025, where it also won the Best Student Paper award!