## Abstract

Let XNLP be the class of parameterized prob-lems such that an instance of size n with parameter k can be solved nondeterministically in time f (k) nO(1) and space f (k) log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[t]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.

Original language | English |
---|---|

Title of host publication | Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021 |

Publisher | IEEE |

Pages | 193-204 |

Number of pages | 12 |

ISBN (Electronic) | 978-1-6654-2055-6 |

ISBN (Print) | 978-1-6654-2056-3 |

DOIs | |

Publication status | Published - 2022 |

Event | 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States Duration: 7 Feb 2022 → 10 Feb 2022 |

### Conference

Conference | 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 |
---|---|

Country/Territory | United States |

City | Virtual, Online |

Period | 7/02/22 → 10/02/22 |

## Keywords

- Bandwidth
- Parameterized complexity
- Whierarchy
- XNLP