Research Interests
Research Interests
Broadly speaking, I am interested in graph algorithms and their complexity, in particular:
Parameterized complexity: Many problems are hard on general graphs, so we are interested in whether they become easier if our input graph has some special properties. In particular, if we know that our input graph is such that it has certain small parameters, how can we exploit that?
Graph embeddings: How can we generalize the concept of outerplanarity to other surfaces? If we are given a subset of vertices of a planar graph, can we efficiently compute how many faces we need to cover it?
Graphs and geometry: I have always been fascinated by the relationship between (continuous) geometric and discrete structures. There are many results about planar graphs, but much less is known for geometric intersection graphs, even (seemingly) simple ones like unit disk graphs or unit interval graphs. I'm interested in the ways in which geometric insights can help us solve problems quicker or easier.
M. Dvořák, D. Knop, M. Opler, J. Pokorný, O. Suchý, K. Sz. Pathfinding in Self-Deleting Graphs. (accepted to ISAAC 2025) arxiv version
M. Dvořák, D. Knop, M. Opler, J. Pokorný, O. Suchý, K. Sz. Density of Traceable Graphs. (submitted) arxiv version
N. Bojikian, A. Firbas, R. Ganian, H. Hoang, K. Sz. Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees. (submitted) arxiv version
H. L. Bodlaender, K. Sz. XALP-completeness of Parameterized Problems on Planar Graphs. (submitted) arxiv version
PhD thesis: Parameterized Complexity of Restricted Variants of Some Classical Problems, Utrecht University, 2024.
H. L. Bodlaender, K. Sz. XNLP-hardness of Parameterized Problems on Planar Graphs. In Proceedings of 50th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2024), Springer International Publishing, 2024. arxiv version
I. Bliznets, J. Nederlof, K. Sz. Parameterized Algorithms for Covering by Arithmetic Progressions. In Proceedings of 49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2024), Springer Nature Switzerland, 2024. arxiv version
J. Nederlof, K. Sz. Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs. In Proceedings of 49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2024), Springer Nature Switzerland, 2024. Best Paper Award, invited to the special issue of Journal of Computer and System Sciences
C. Groenland, J. Nederlof, I. Mannens, K. Sz. Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth. In Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
I. Mannens, J. Nederlof, C. Swennenhuis, K. Sz. On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem. In Proceedings of 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021), Springer, Cham, 2021.