Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation

Abstract

In this paper, we show that Bandwidth is hard for the complexity class W[t] for all t∈ N, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path PN and integer M, decide if there exists a mapping of the vertices of PN to a path PM, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the pre-image of a vertex from PM equals an integer c. We show that Weighted Path Emulation, with c as parameter, is hard for W[t] for all t∈ N, and is strongly NP-complete. We also show that Directed Bandwidth is hard for W[t] for all t∈ N, for directed acyclic graphs whose underlying undirected graph is a caterpillar.