18. 11. 2024
Krisztina Szilágyi discusses the complexity of parameterized problems on planar graphs, particularly their hardness within the XNLP and XALP classes. Her findings establish new lower bounds by proving XNLP-hardness and XNLP-completeness for various problems parameterized by outerplanarity, treewidth, and pathwidth.