Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428479 | Information Processing Letters | 2016 | 5 Pages |
Abstract
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=NPP=NP). Also, we show that the problem is FPT parameterized by the treewidth of the input graph. Furthermore, we show that the problem parameterized by k is W[2]-hard and belongs to W[P].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mehdy Roayaei, Mohammadreza Razzazi,