Abstract

A Sketch of Parameterized Complexity

Hans L. Bodlaender ORCID Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
Abstract

In the field of parameterized complexity, we study algorithms for and the complexity of problems where one part of the input is a parameter that is assumed to be small. In this talk, a survey will be given of several central notions from parameterized complexity, and discuss some recent developments, including the classes XNLP and XALP. These topics will be illustrated with examples from results on graph layout and graph drawing.

Keywords and phrases:
Parameterized complexity, XNLP, XALP
Category:
Invited Talk
Copyright and License:
[Uncaptioned image] © Hans L. Bodlaender; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing → Graph algorithms ; Theory of computation → Fixed parameter tractability
DOI:
10.4230/LIPIcs.GD.2025.1
Event:
33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)
Editors:
Vida Dujmović and Fabrizio Montecchiani
Series and Publisher:
LIPIcs Logo Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik