Algorithms for Minimum Membership Dominating Set problem

Given a graph G = (V, E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem asks to compute a dominating set S ⊆ V such that for each vertex u ∈ V , 1 ≤ |N[u] ∩ S| ≤ k. The problem is known to be NP-complete even on split graphs and planar bipartite graphs. In this paper, we approach the problem from an algorithmic standpoint and obtain several interesting results. We give an 𝒪*(1.5719n) time exact algorithm for the problem on split graphs. Following a reduction from a special case of the 1-in-3 SAT problem, we show that there is no sub-exponential time algorithm that runs in time 𝒪*(2°(n)) for bipartite graphs, for any k ≥ 2. We also prove that the problem is NP-complete when Δ = k + 2, for any k ≥ 5, even for bipartite graphs. We investigate the parameterized complexity of the problem for the parameter twin cover number and the combined parameter distance to cluster, membership(k) and prove that the problem is fixed-parameter tractable. Using a dynamic programming based approach, we obtain a linear-time algorithm for trees.