XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

Abstract In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W [1]-hardness proofs for these problems, since XNLP-hardness implies W [ t ]-hardness for all t . It also indicates, via a conjecture by Pilipczuk and Wrochna (ACM Trans Comput Theory 9:1–36, 2018), that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set , Dominating Set , Odd Cycle Transversal , ( q -)Coloring , Max Cut , Maximum Regular Induced Subgraph , Feedback Vertex Set , Capacitated (Red-Blue) Dominating Set , Capacitated Vertex Cover and Bipartite Bandwidth .