Abstract

Graph alliances have wide-ranging applications, including community detection in social networks, the identification of resilient subnetworks in communication systems, and the modeling of stable coalitions in competitive environments. Among the main problems studied in this area is the computation of a minimum defensive alliance, which is known to be computationally challenging. In this paper, we study a recursive algorithmic approach for finding a minimum defensive alliance and analyze its time and space requirements. In particular, we investigate the recursion depth of the algorithm under a uniform-adjacency assumption, that is, at each recursive call of the algorithm, the number of eligible adjacent vertices from which the next vertex can be selected to join the under-construction defensive alliance is uniformly distributed over its feasible values. Under this assumption, for a given graph with n vertices, we show that the expected recursion depth is O(lnn). When the actual recursion depth follows this expected behavior, the algorithm computes a minimum defensive alliance in O(n1.7) time using O(nlnn) space. In the general case, however, the recursive approach may still require exponential time, namely O(n2n), and O(n2) space, which is consistent with the NP-hardness of the minimum defensive alliance problem. These results clarify both the potential efficiency and the worst-case limitations of the proposed algorithmic method.

IPC Classification

Keywords