Parameterized Complexity of Minimum Membership Dominating Set

Abstract

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