Three Accepted Papers

Three papers coauthored by members of the group have been accepted for publication. The paper A Complexity Analysis of the c-Closed Vertex Deletion Problem was accepted at the 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, which will be held in Perugia, Italy in March 2026. The c-closed property is motivated by the triadic closure phenomenon in social network analysis and the paper, coauthored by Lisa Lehner, Christian Komusiewicz and Luca Staus, focuses on the problem of finding a largest subgraph that is c-closed. The work is based on Lisa Lehner's Bachelor's thesis and presents an overview of the complexity of the problem.

The paper Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree, coauthored by Diptapriyo Majumdar from IIIT Delhi and Christian Komusiewicz, presents kernelizations for a graph-theoretic enumeration problem. In these kernelizations the aim is, roughly speaking, to compress large input instances to small ones from which all solutions can be quickly generated. The paper will be presented at the 51st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2026, which will be held in Kraków, Poland in January 2026.

The third paper, A Parameterized-Complexity Framework for Finding Local Optima considers local search problems as solved for example by hill-climbing algorithms. It studies the difficulty of finding a local optimum, in particular whether it is possible to avoid long chains of local improvements and presents positive results as well as running time lower bounds based on assumptions in parameterized complexity.
The paper is coauthored by Robert Ganian and Hung Hoang from TU Wien and Christian Komusiewicz and Nils Morawietz and will be presented at the 17th Innovations in Theoretical Computer Science Conference, ITCS 2026, which will take place at Bocconi University in Milan, Italy in January 2026.