We are given an undirected graph G=(V,E) where the vertices are indexed from 0 to n−1 , i.e., we have V={0,1,…,n−1} . A global defensive alliance of G is a subset S⊆V , such that: – Any vertex in V\S is adjacent to at least one vertex in S – Any vertex in S is such that the number of its neighbors in S is larger than or equal to the number of its neighbors in V\S . The Minimum Global Defensive Alliance Problem (MGDA) is to determine a global defensive alliance of G of minimum cardinality. Question 4.1: Is S=V\{6} a feasible solution to MGDA? Is it an optimal solution? Question 4.2: State the decision problem associated with MGDA. Question 4.3: Prove that MGDA is a problem of the class NP. Question 4.4: Knowing that MGDA is NP-hard, does there exist a polynomial-time algorithm that solves it optimally? Question 4.5: Can we find an optimal algorithm to solve MGDA when G is a complete graph, i.e., there exists exactly one edge between any pair of vertices? Question 4.6: This is a bonus question (it is not mandatory, but can bring extra points). The text file next to the graph represents this graph. It gives the number of vertices, and the square binary matrix is the adjacency matrix of this graph. Write a Python program that can read such a text file, and that returns a Global Defensive Alliance with the smallest possible cardinality. Run your program on all the graphs given in the zip archive and display the best solution objective values in a table. Your algorithm should also be described in pseudo-code, and your strategy should also be explained in text.

28 0

Get full Expert solution in seconds

$1.97 ONLY

Unlock Answer

EXPERT ANSWER