2023/07/19 by Sangam Balchandar Reddy, Reddy, Sangam Balchandar, Anjeneya Swami Kare +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2307.09760
openalex publication_date 2023/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G = (V, E), a non-empty set S ⊆ V is a defensive alliance, if for every vertex v ∈ S, the majority of its closed neighbours are in S, that is, |NG[v] ∩ S| ≥ |NG[v] ∖ S|. The decision version of the problem is known to be NP-Complete even when restricted to split and bipartite graphs. The problem is fixed-parameter tractable for the parameters solution size, vertex cover number and neighbourhood diversity. For the parameters treewidth and feedback vertex set number, the problem is W[1]-hard. \hspace*2em In this paper, we study the defensive alliance problem for graphs with bounded degree. We show that the problem is polynomial-time solvable on graphs with maximum degree at most 5 and NP-Complete on graphs with maximum degree 6. This rules out the fixed-parameter tractability of the problem for the parameter maximum degree of the graph. We also consider the problem from the standpoint of parameterized complexity. We provide an FPT algorithm using the Integer Linear Programming approach for the parameter distance to clique. We also answer an open question posed in \citeAG2 by providing an FPT algorithm for the parameter twin cover.