Group GPUs by node and partition by links

Problem Statement

You are managing a cluster of GPUs. Each GPU is identified by a unique integer ID and belongs to exactly one physical host node. You are given a list of direct high-speed interconnects (links) between specific pairs of GPUs.

Your task is to partition the GPUs into two distinct groups, Group A and Group B, such that:

1. No two GPUs in the same group are connected by a link if they reside on the same host node.
2. You maximize the number of links that exist between Group A and Group B.

Implement the function partition_gpus(gpu_to_node, links):

• gpu_to_node: A dictionary mapping gpu_id (int) to node_id (int).
• links: A list of tuples (gpu_id1, gpu_id2) representing a connection.

Return a list containing two lists: the first list represents the IDs in Group A, and the second represents the IDs in Group B. If no such partition exists that satisfies constraint #1, return an empty list.

Constraints

• Number of GPUs <= 1,000.
• Number of links <= 10,000.
• Nodes are arbitrary integers.

Example

Input: gpu_to_node = {1: 10, 2: 10, 3: 20, 4: 20} links = [(1, 2), (3, 4), (1, 3), (2, 4)]

Output: [[1, 4], [2, 3]] Explanation: Linking GPUs 1 and 2 on node 10 is forbidden in the same group. Splitting them into different groups satisfies the constraints while maintaining cross-node connections.

Edge Cases

• Disconnected graph components.
• A node containing only one GPU.
• Impossible constraints leading to an invalid partition.