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

Conference paper (2022)

Authors

Hans L. Bodlaender Universiteit Utrecht
C.E. Groenland Universiteit Utrecht
Hugo Jacob ENS Paris-Saclay
Lars Jaffke University of Bergen and Bjerknes Centre for Climate Research
Paloma T. Lima University of Copenhagen
Affiliation
External organisation
Bandwidth Parameterized complexity W-hierarchy Pathwidth XNLP Linear clique-width Linear mim-width
More Info
expand_more

Published Date

2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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 [ToCT 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, and Bipartite Bandwidth.