On the Complexity of Finding Optimal Global Alliances

Abstract

A defensive alliance in a graph $G(V,E)$ is a set of vertices $S\subseteq V$ such that for every vertex $v\in S$, the closed neighborhood $N_G[v]$ of $v$ has at least as many vertices in $S$ as it has in $V–S$. An offensive alliance is a set of vertices $S\subseteq V$, such that for every vertex $v$ in the boundary $\mathrm{\partial }(S)$ of $S$ the number of neighbors that $v$ has in $S$ is greater than or equal to the number of neighbors it has in $V–S$. A subset of vertices which is both an offensive and a defensive alliance is called a powerful alliance. An alliance which is also a dominating set is called a global alliance. In this paper, we show that finding an optimal defensive (offensive, powerful) global alliance is an NP-hard problem.