The Minimum Neighbourhood Problem

Abstract

Given a graph G = (V,E) with n vertices and a positive integer s ≤ n, we want to find a set S ⊆ V of size s such that |N[S]| is minimum, where N[S] denotes closed neighbourhood of S. We call this problem as the minimum neighbourhood problem (MNP). In this project, we give a parameterized algorithm which takes as input a graph G, its tree decomposition with width at most k, and a positive integer s, and returns |N[S]| such that S ⊆ V , |S| = s and S has minimum neighbours in G, where the parameter is k.