Partial Domination in Some Geometric Intersection Graphs and Some Complexity Results

Partial domination problem is a generalization of the minimum dominating set problem on graphs. Here, instead of dominating all the nodes, one asks to dominate at least a fraction of the nodes of the given graph by choosing a minimum number of nodes. For any real number (0, 1], -partial domination problem can be proved to be NP-complete for general graphs. In this paper, we define the maximum dominating k-set of a graph, which is polynomially transformable to the partial domination problem. The existence of a graph class for which the minimum dominating set problem is polynomial-time solvable, whereas the partial dominating set problem is NP-hard, is shown. We also propose polynomial-time algorithms for the maximum dominating k-set problem for the unit and arbitrary interval graphs. The problem can also be solved in polynomial time for the intersection graphs of a set of 2D objects intersected by a straight line, where each object is an axis-parallel unit square, as well as in the case where each object is a unit disk. Our technique also works for axis-parallel unit-height rectangle intersection graphs, where a straight line intersects all the rectangles. Finally, a parametrized algorithm for the maximum dominating k-set problem in a disk graph where the input disks are intersected by a straight line is proposed; here the parameter is the ratio of the diameters of the largest and smallest input disks.