XALP-completeness of parameterized problems on planar graphs

DOI10.1016/J.DAM.2026.01.021MaRDI QIDQ7230333zbMATH OpenFDO

Authors Hans L. Bodlaender, Krisztina Szilágyi

Publication date 17 April 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.01.021

zbMATH Keywords

outerplanarityparameterized complexityplanar graphsXALPXNLP

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Approximation algorithms for NP-complete problems on planar graphs
• Capacitated Domination and Covering: A Parameterized Perspective
• Determining the Smallest k Such That G Is k-Outerplanar
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Generalized coloring for tree-like graphs
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• List colouring trees in logarithmic space
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On space efficiency of algorithms working on structural decompositions of graphs
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• Planar capacitated dominating set is \(W[1]\)-hard
• Polynomial-time data reduction for dominating set
• Problems hard for treewidth but easy for stable gonality
• Structurally parameterized \(d\)-scattered set
• The parameterised complexity of integer multicommodity flow
• Treewidth governs the complexity of target set selection
• Treewidth. Computations and approximations
• Upper bounds for \(f\)-domination number of graphs
• Upward and orthogonal planarity are W[1]-hard parameterized by treewidth

This page was built for publication: XALP-completeness of parameterized problems on planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7230333)