Parameterized Complexity of Minimum Membership Dominating Set

Given a graph G= (V, E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set S⊆ V of G such that for each v∈ V, | N[ v] ∩ S| is at most k. We investigate the parameterized complexity of the problem and obtain the following results about MMDS: 1.W[1]-hardness of the problem parameterized by the pathwidth (and thus, treewidth) of the input graph.2.W[1]-hardness parameterized by k on split graphs.3.An algorithm running in time 2 O(vc)| V| O(1), where vc is the size of a minimum-sized vertex cover of the input graph.4.An ETH-based lower bound showing that the algorithm mentioned in the previous item is optimal.