WG Papers

Two papers of the group we accepted for presentation at this year's Workshop on Graph-Theoretic Concepts in Computer Science, WG 2026External link, one of our favorite conferences! 

In Clustering with Locally Bounded Ignorance coauthored by Jaroslav Garvardt and Christian Komusiewicz, we study Correlation Clustering, one of the most important graph-based clustering problems. The paper presents new kernelizations, that is, data reduction algorithms that provide guarantees on the size of the resulting instance. The main novelty is that these algorithms work even in the presence of uncertainty in the data. 

In Preventing Small Global Cuts by Protecting Edges, coauthored by Christian Komusiewicz, Zhenwei Liu, Nils Morawietz and Frank Sommer, we consider a 2-player game where a defender aims to preserve the connectivity of a graph against an attacker that wants to delete edges. This hard game generalizes the Minimum Cut problem. We provide an overview on the parameterized complexity of the problem.