| dc.description.abstract | A Defensive Alliance in a graph is a subset of the vertices where each vertex in the alliance has more neighbours in the alliance, than outside it. They were originally introduced to model military alliances, but the concept has application in areas such as modelling communities and also fault tolerant computing.
Finding small Defensive Alliances is known to be a NP-Complete problem, even in restrictive graph classes such as planar graphs. The difficulty of finding small Defensive Alliances provides the motivation to look at the parameterised complexity of the problem, which in the literature is documented only for a small number of parameters such as Solution Size, Vertex Cover and Neighbourhood Diversity. Further, a restricted set of variants were considered in the literature, with limited practical work done in finding alliances.
This thesis endeavored to address these limitations by studying the parameterised complexity of variants of Defensive Alliance, considers new parameters for Defensive Alliance and conducts computational experiments using implementations of some of the algorithms discussed in the thesis. For the variants, the general results involve several novel variants, such as one that generalises the number of neighbours required for each vertex, several that force larger components of the alliance to depend on sets of constraints, vertex and edge weighted variants. For these, whether or not it was possible to extend the existing algorithms to the variants is discussed.
Results are given for several new parameters, including Modular Width and Distance to Clique, for Defensive Alliance, along with minor results covering the use of multiple parameters. Further, a previously studied problem called Globally Minimal Defensive Alliance is shown to be in para-NP when parameterised by Solution Size.
Finally, experimental results for a variety of exact algorithms and heuristics are discussed. | |
