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

01/31/2022
by   Hans L. Bodlaender, et al.
0

In this paper, we show several parameterized problems to be complete for the class XNLP: parameterized problems that can be solved with a non-deterministic algorithm that uses f(k)log n space and f(k)n^c time, with f a computable function, n the input size, k the parameter and c a constant. The problems include Maximum Regular Induced Subgraph and Max Cut parameterized by linear clique-width, Capacitated (Red-Blue) Dominating Set parameterized by pathwidth, Odd Cycle Transversal parameterized by a new parameter we call logarithmic linear clique-width (defined as k/log n for an n-vertex graph of linear clique-width k), and Bipartite Bandwidth.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset