Computational complexity of current netlist matching algorithms

TL;DR: The OP asked if the computational complexity of matching netlists is different from matching other types of graphs. It isn't because netlists are still GI-complete graphs.

The computational complexity is still GI if you add the restriction to netlists, because netlists experience the same worst case scenarios than other types of graphs and computational complexity only looks at the worst case behavior.

The only real thing that have all kinds of netlists in common is that they are heavily labeled.

Within the set of all netlists there are of course cases that are easier and cases that are harder. In general the problem is easier if you have a graph with many different labels. I.e. a netlist of transistors where you only have n-types and p-types is harder to match than a netlist of gates where you have a larger number of cell types, which in turn is harder to match than a netlist for an FPGA architecture with N-input LUTs with \$2^{2^N}\$ different LUT configurations.

When looking at the subgraph isomorphism problem (i.e. trying to find and extract a given sub circuit), you can give a max. polynomial for each given sub circuit. This is imo pretty intuitive: If I give you a specific circuit and ask you to write code that looks for this circuit you could simply encode the pattern by iterating over all candidates for node_1, each candidate when chosen reducing the possible number of candidates for node_2, and so on. In the worst case this will create K cascaded loops for a pattern of K cells, yielding a complexity of \$O(N^K)\$ for finding the circuit in a graph of N nodes. (Each pattern-circuit may allow for different optimizations that allow for reducing the complexity.)

As a side note: Algorithms that use a neighborhood matrix usually use the following encoding for the circuit: There is a node for each cell and a node for each net. A connection between two cells is therefore encoded as as two edges in the graph: one from cell_1 to net_1 and one from the net_1 to cell_2. (I've also seen encodings that create an intermediate nodes for each cell port, but in most cases information regarding cell ports is stored in edge labels.) This will ensure that even for nets with large fan-out (such as reset signals, for example) the neighborhood matrix stays very sparse (number of non-zeros linear to the number of cells and nets, instead of the quadratic complexity for the naive encoding).

A nice algorithm that can be extended easily to the needs of a specific problem domains is the Ullmann subgraph isomorphism algorithm. It is already pretty old and not the most efficient algorithm, but I think it is a very clear algorithm and learning it helps you to better understand the problem it solves.