Clique Expansion

Problem

Convert a hypergraph into a graph with clique expansion: every pair of nodes inside a hyperedge becomes an edge.

Duplicate edges are removed and each hyperedge is treated as a set, so repeated members do not create parallel edges. Return the resulting edges as a sorted list of [u, v] pairs. hyperedges is a list of vertex lists.

Hint

Clique expansion loses higher-order structure but enables standard graph algorithms.

Test cases

case 1

in: [[[0,1,2],[1,2,3]]]

expected: [[0,1],[0,2],[1,2],[1,3],[2,3]]

case 2

in: [[[0,1],[1,2]]]

expected: [[0,1],[1,2]]

case 3

in: [[[0,0,1]]]

expected: [[0,1]]

Starter codePython

def clique_expansion(hyperedges):
    # Your code here
    pass

3 test cases · run your code against them in the editor