Subgraph Isomorphism Count

Problem

Count the (not necessarily induced) subgraphs of a graph that are isomorphic to a small pattern with m nodes.

The pattern is given by pattern_edges with nodes 0 to m-1, where m is one plus the largest endpoint. Backtrack over injective mappings of pattern nodes to graph nodes, requiring every pattern edge to map to an edge. Return the number of mappings; mappings that differ only by node labels count separately.

Hint

Ordered mappings mean each pattern automorphism multiplies the count.

Test cases

case 1

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

expected: 8

case 2

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

expected: 6

case 3

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

expected: 6

case 4

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

expected: 6

Starter codePython

def subgraph_isomorphism_count(n, edges, pattern_edges):
    # Your code here
    pass

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