Algorithms for Minimum Membership Dominating Set Problem

Given a graph G = (V, E) and an integer k, the Minimum Membership Dominating Set problem asks to compute a set S V such that for each v V, 1 |Nv 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 the algorithmic standpoint and obtain several interesting results. We give an O^* (1. 747ⁿ) time algorithm for the problem on split graphs. Following a reduction from a special case of 1-in-3 SAT problem, we show that there is no sub-exponential time algorithm running in time O^* (2^o (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 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.