The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete

Abstract

It is shown that the Bandwidth Minimization problem remains NP-complete even when restricted to “caterpillars with hairs of length at most three”. “Caterpillars” are special trees; they consist of a simple chain (the “body”) with various simple chains attached to thee vertices of the body (the attached chains are called “hairs”). A previous result in the literature shows that the bandwidth of caterpillars with hairs of length at most 2 can be found in $O( n\log n )$ time (this Journal, 2 (1981), pp. 387–393). We also show that the bandwidth problem is NP-complete when restricted to caterpillars with at most one hair attached to each vertex of the body. The proof is relatively straightforward and thereby also provides an easier proof than found in (SIAM J. Appl. Math., 34 (1978), pp. 477–495) that the bandwidth problem is NP-complete for trees with maximum vertex degree 3.