2025/05/21 by Dutta, Madhura, Anil Maheshwari, Maheshwari, Anil +4
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2505.15949
openalex publication_date 2025/05/21 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28
\em Partial domination problem is a generalization of the \em 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 \em 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.