An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification

In this paper, we study the problem of modifying a graph such that the resulting graph has a dominating set of size at most k. Solving this problem determines the minimum number of edges to be added to a given graph such that at most k vertices can dominate all vertices. We show that this problem is NP-hard, and therefore, has no polynomial-time algorithm (unless P=NP). Also, we show that the problem is FPT parameterized by the treewidth of the...