A generalization of the pentomino exclusion problem: Dislocation of graphs

In this paper, we first investigate the pentomino exclusion problem, due to Golomb. We solve this problem on the 5×n5×n grid and we give some lower and upper bounds for the k×nk×n grid for all kk and nn.We then give a generalization of this problem in graphs, the ΔΔ-dislocation problem  , which consists in finding the minimum number of vertices to be removed from a graph so as all the remaining connected components have cardinality at most ΔΔ.We investigate the algorithmic aspects of the ΔΔ-dislocation problem: we first prove the problem is NP-Complete, then we give a sublinear algorithm which solves the problem on a restricted class of graphs which includes the k×nk×n grid graphs, provided kk is not part of the input.