| dc.description.abstract | In this paper, we study the Maximum Remove-r Distance-d Independence Set (MRrDdIS for short) problem. The goal of this problem is to maximize the size of a distance d-independent set by removing at most a specified number r of vertices from a given graph. This problem generalizes the Maximum Distance-d Independent Set problem, where we look for a maximum size set of vertices for which the minimum distance between every pair of vertices from the set is at least d. The latter problem in turn generalizes the well known Maximum Independent Set problem.
From this problem we derived two more problems, which both revolve around finding sets of nodes that we want to remove. One of them, called the d-Minimum Removal Set (d-MRS for short) problem, is about finding a minimum set of nodes to remove such that a given Independent Set becomes a Distance-d Independent Set on a given graph. The other one, called the (r,d)-Optimal Removal Set ((r,d)-ORS for short) problem, is about finding a set of at most r nodes that when removed from a graph maximizes its Maximum Distance-d Independent Set.
In this paper, we prove that the decision variants of the MRrDdIS problem and the d-MRS problem are NP-complete. We present an algorithm for the MRrDdIS problem that in the worst case runs in $O(r^2n^3)$ time on trees. For the d-MRS problem we not only present a linear time algorithm, but also prove that a linear time algorithm can be generated for graphs with bounded treewidth. | |
