| Autor: |
Agrawal, Akanksha, Choudhary, Pratibha, Narayanaswamy, N. S., Nisha, K. K., Ramamoorthi, Vijayaragunathan |
| Rok vydání: |
2021 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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}(\textbf{vc})} |V|^{\mathcal{O}(1)}$, where $\textbf{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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
