Subgraph isomorphism (or even set membership) in Z3?

Question

I'm trying to find a way to encode a sort of basic subgraph isomorphism in Z3 (preferably z3py). While I know there are papers on this in the abstract, finding any mechanism to do it has eluded me even for very trivial cases, because I'm very new to Z3 in general!

Suppose you have just about the most basic subgraph with nodes (0,1,2) and edges (0,1) with node 2 off on its own, and the supergraph has nodes (0,1,2) and edges (1,2) with node 0 off on its own. You could map the nodes of the subgraph into the supergraph with

0->1,
1->2,
2->0

...as one possible mapping that would satisfy "if these two nodes are connected in the subgraph, their mapped nodes are connected in the supergraph"

So okay :) I tried

from networkx import Graph
from networkx.linalg.graphmatrix import adjacency_matrix

subgraph = Graph()
subgraph.add_nodes_from([0,1,2])
subgraph.add_edges_from([(0,1)])

supergraph = Graph()
supergraph.add_nodes_from([0,1,2])
supergraph.add_edges_from([(1,2)])

s = Solver()
assignments = [Int(f'n{node}') for node in subgraph.nodes]

# each bit assignment in the subgraph belongs to one in the supergraph
assignment_constraint = [ And(assignments[i] >= 0, assignments[i] <= max(supergraph.nodes)) for i in subgraph.nodes ]
# subgraph bits can't be assigned to the same supergraph bits
assignment_distinct = [ Distinct([assignments[i] for i in subgraph.nodes])]

which just gets me as far as "each assignment from subgraph to supergraph should map a node in the subgraph to some node in the supergraph and no two subgraph nodes can be assigned to the same supergraph node"

...but then I get stuck because I keep thinking along the lines of

for edge in subgraph.edges:
  s.add( (assignments[edge[0]], assignments[edge[1]]) in supergraph.edges )

...but of course that doesn't work because pythonically those aren't the right sort of keys so that's always false or broken.

So how does one approach that? I can add constraints like "this_var == 1" but get very confused on things like checking membership, ie

>>> assignments[0] == 1.0
n0 == 1  # so that's OK then
>>> assignments[0] in [1.0, 2.0, 3.0]
False  # woops, that fails horribly

and I feel like I'm missing a very basic "frame of mind" thing here.

alias alias · Accepted Answer · 2021-05-11T21:00:42

It is relatively straightforward to encode subgraph isomorphism in z3, pretty much along the lines of how you described. However, this encoding is unlikely to scale to large graphs. As you no doubt know, subgraph isomorphism is NP-complete in general, and this encoding will cause z3 to simply enumerate all possibilities and thus will blow up exponentially.

Having said that, here's a straightforward encoding:

from z3 import *

# Subgraph, number of nodes and edges.
# Nodes will be named implicitly from 0 to noOfNodesA - 1
noOfNodesA = 3
edgesA = [(0, 1)]

# Supergraph:
noOfNodesB = 3
edgesB = [(1, 2)]

# Mapping of subgraph nodes to supergraph nodes:
mapping = Array('Map', IntSort(), IntSort())

s = Solver()

# Check that elt is between low and high, inclusive
def InRange(elt, low, high):
    return And(low <= elt, elt <= high)

# Check that (x, y) is in the list
def Contains(x, y, lst):
    return Or([And(x == x1, y == y1) for x1, y1 in lst])


# Make sure mapping is into the supergraph
s.add(And([InRange(Select(mapping, n1), 0, noOfNodesB-1) for n1 in range(noOfNodesA)]))

# Make sure we map nodes to distinct nodes
s.add(Distinct([Select(mapping, n1) for n1 in range(noOfNodesA)]))

# Make sure edges are preserved:
for x, y in edgesA:
    s.add(Contains(Select(mapping, x), Select(mapping, y), edgesB))

# Solve:
r = s.check()
if r == sat:
    m = s.model()
    for x in range(noOfNodesA):
        print ("%s -> %s" % (x, m.evaluate(Select(mapping, x))))
else:
    print ("Solver said: %s" % r)

I've added comments along the way, so hopefully you should be able to read the code through; feel free to ask specific questions.

When I run this, I get:

$ python a.py
0 -> 1
1 -> 2
2 -> 0

which finds exactly the mapping you alluded to in your question.

Best of luck!

Subgraph isomorphism (or even set membership) in Z3?

1 Answers