Abstract
The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)nᴼ⁽¹⁾ time and g(k) log n space. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. In this paper, we show the hardness of several problems on planar graphs, parameterized by outerplanarity, treewidth and pathwidth, thus strengthening several existing results. In particular, we show XNLP-hardness of the following problems parameterized by outerplanarity: All-or-Nothing Flow, Target Outdegree Orientation, Capacitated (Red-Blue) Dominating Set, Target Set Selection etc. We also show the XNLP-completeness of Scattered Set parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity.