XNLP-Hardness of Parameterized Problems on Planar Graphs

Abstract

The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)nO(1) time and g(k)logn space, where n is the size of the input instance and k the parameter. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. These two classes are a “natural home” for many standard graph problems and their generalizations. 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.