Algorithms for Minimum Membership Dominating Set Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913455827582976 |
|---|---|
| author | Reddy, Sangam Balchandar Kare, Anjeneya Swami |
| author_facet | Reddy, Sangam Balchandar Kare, Anjeneya Swami |
| contents | Given a graph $G = (V, E)$ and an integer $k$, the Minimum Membership Dominating Set problem asks to compute a set $S \subseteq V$ such that for each $v \in V$, $1 \leq |N[v] \cap S| \leq 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 $\mathcal{O}^*(1.747^n)$ 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 $\mathcal{O}^*(2^{o(n)})$ for bipartite graphs, for any $k \geq 2$. We also prove that the problem is NP-complete when $Δ= k+2$, for any $k\geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00797 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algorithms for Minimum Membership Dominating Set Problem Reddy, Sangam Balchandar Kare, Anjeneya Swami Data Structures and Algorithms Computational Complexity 05C85, 68Q17, 68Q27 Given a graph $G = (V, E)$ and an integer $k$, the Minimum Membership Dominating Set problem asks to compute a set $S \subseteq V$ such that for each $v \in V$, $1 \leq |N[v] \cap S| \leq 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 $\mathcal{O}^*(1.747^n)$ 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 $\mathcal{O}^*(2^{o(n)})$ for bipartite graphs, for any $k \geq 2$. We also prove that the problem is NP-complete when $Δ= k+2$, for any $k\geq 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. |
| title | Algorithms for Minimum Membership Dominating Set Problem |
| topic | Data Structures and Algorithms Computational Complexity 05C85, 68Q17, 68Q27 |
| url | https://arxiv.org/abs/2408.00797 |