Maximum Star Sum Of A Graph - Leetcode Solution

Problem statement:

Given an undirected graph consisting of n vertices and m edges, and an array of integers, nums, of length n. Find the maximum sum of stars in the graph where a star is defined as a vertex and all the edges connected to it. Note that each vertex can be a part of at most one star.

Example:

nums = [3,4,5,1,2] edges = [[0,1],[0,2],[0,3],[1,4]]

Output: 16 Explanation:

• Vertex 0 is connected to vertices 1, 2 and 3. Therefore, a star can be formed with vertex 0 as the center and edges (0,1), (0,2), (0,3) as its edges. This star has a sum of 3 + 4 + 5 = 12.
• Vertex 1 is connected to vertex 0 only. Therefore, a star can be formed with vertex 1 as the center and edge (0,1) as its edge. This star has a sum of 3 + 4 = 7.
• Vertex 2 is connected to vertex 0 only. Therefore, a star can be formed with vertex 2 as the center and edge (0,2) as its edge. This star has a sum of 3 + 5 = 8.
• Vertex 3 is connected to vertex 0 only. Therefore, a star can be formed with vertex 3 as the center and edge (0,3) as its edge. This star has a sum of 3 + 1 = 4.
• Vertex 4 is connected to vertex 1 only. Therefore, a star can be formed with vertex 4 as the center and edge (1,4) as its edge. This star has a sum of 4 + 2 = 6.

Therefore, the maximum sum of stars in the graph is 12 + 7 + 8 + 4 + 6 = 37.

Solution:

The problem can be solved in O(n+m) time complexity using a few observations.

Observation 1: For any vertex, if its degree is less than 2, it cannot form a star. Therefore, we can ignore all such vertices.

Observation 2: For any vertex with degree k (k >= 2), we can form k stars by considering this vertex as the center and any one of its edges as one of the edges of the star. Therefore, we should consider all possible k stars and select the one with the maximum sum.

Based on these observations, we can follow the steps given below:

Step 1: Traverse the graph and find all vertices with degree 2 or more. Store these vertices in a set.

Step 2: For each vertex in the set, find all possible stars that can be formed with this vertex as the center and any one of its edges as one of the edges of the star. Compute the sum of each such star.

Step 3: Return the sum of the star with the maximum sum over all vertices in the set.

The implementation of the above algorithm is given below:

def max_sum_of_stars(n: int, edges: List[List[int]], nums: List[int]) -> int: # Form a set of vertices with degree 2 or more graph = collections.defaultdict(set) for u, v in edges: graph[u].add(v) graph[v].add(u) vertices_set = set() for u in range(n): if len(graph[u]) >= 2: vertices_set.add(u)

# Compute the sum of stars centered at each vertex in the set
max_sum = 0
for u in vertices_set:
    for v in graph[u]:
        # u-v edge is selected as the edge of the star
        star_sum = nums[u] + nums[v]
        for w in graph[u] - set([v]):
            star_sum += nums[w]
        max_sum = max(max_sum, star_sum)

return max_sum

The time complexity of the above algorithm is O(n+m) because we traverse the graph only once.

1