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.
