Chordal Graph Clique Count

Problem

For a chordal graph, a perfect elimination order lists vertices so that each vertex's later neighbors form a clique. The maximal cliques are exactly the maximal sets of the form {v} union its later neighbors, so build those candidate sets, keep the ones not contained in another, and return how many remain. The adjacency matrix is a symmetric 0/1 matrix; return 0 for an invalid order or a non-square matrix.

Hint

With a perfect elimination order, each maximal clique appears as a vertex plus its later neighbors, minus the sets contained in bigger ones.

Test cases

case 1

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

expected: 3

case 2

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

expected: 1

case 3

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

expected: 3

case 4

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

expected: 2

case 5

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

expected: 0

Starter codePython

def chordal_graph_clique_count(adjacency, order):
    # Your code here
    pass

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