Applicability of Distance Computation for Graphs to LVS Discrepancy Analysis

1. Introduction

An important step in electronic circuit design is layout versus schematic verification (LVS). It consists of the comparison of a schematic circuit to its IC layout counterpart to determine whether they implement the same functionality. Typically, this comparison is performed in terms of spice netlists produced from the schematic and layout representation of the circuit. The ultimate goal of this verification is to ensure that these netlists completely match each other, possibly after some equivalence transformations of netlists, such as device filtering, merging, reduction. However at earlier iterations of the design cycle these netlists often fail to match. In some cases a single design error may lead to a long list of mismatched elements, and a common complaint is that LVS discrepancy reports are very difficult to analyze. Even with the aid of cross-probing and netlist browsing tools tracking the netlist discrepancies down to their source is often a tedious and time-consuming task.

Silvaco's Guardian LVS verification tool attempts to make this error-tracking task easier by postprocessing LVS discrepancy reports and pointing out potential matches of unmatched nodes, see Figure 1.


Figure 1. Guardian potential match report.

 

Graphs and hypergraphs are common mathematical models for netlists. Guardian used graph-theoretic techniques to process netlists. In graph-theoretical terms, netlist comparison is modeled by the well-known graph isomorphism problem. However graph isomorphism itself represents an ideal case of complete match between two circuits. When talking about discrepancies, a more adequate model is the notion of the distance between graphs.

A well-known type of distance between complex structured objects is the so-called editing distance. If S is a set of allowable editing operations on the set of all objects in question, then the editing distance between two objects A an B is the minimal number of editing operations from set S required to transform object A into object B. In the case of graphs, the natural atomic editing operations are insertion and deletion of versices and edges.

Moreover, these objects A and B are often identified with each other up to their isomorphism, so it is natural to talk about distances between isomorphic classes of objects. In the case of graphs this distinction of notions boils down to the distinction between the notion of distance for labeled graphs vs. distance between unlabeled graphs. In this article, a graph will mean an isomorphism class of labeled graphs. A number of papers discussed various types of instances between graphs, see e.g., references [M79], [MK79], [Z75]. This article considers the computational complexity for some definitions of distance between graphs. It proves that the problems of computing the distances between unlabeled graphs are NP-hard even in restricted classes of graphs. Please refer to [GJ79] for all notions related to computational complexity and NP-hardness.

Notice that the problem of computation of any kind of distance between (unlabeled) graphs is at least as computationally hard as the graph isomorphism problem [GJ79].


Figure 2: Graphs with edge-editing distance 1.

 

2. NP-Hardness of Edge-Based Graph Editing Metrics

Let G1(V1, E1) and G2(V2, E2) denote two graphs. One may consider the following natural metrics.

(a) For graphs with the same vertex count (|V1|=|V2|=n):

d1(G1, G2) =min_{t} (|E1\t(E2)|+ |t(E2)\E1|),

d2= (G1, G2) =min_{t} max {|E1\t(E2)|, |t(E2)\E1|},

where in both cases the minimum is over the set of all permutations t of the vertex set.

d3= n-k,

where k is the maximal vertex number for a graph isomorphic to generate subgraphs of G1 and G2, [Z75].

(b) Over the set of (n,m)-graphs, i.e., graphs with n vertices and m edges.

d4(G1, G2) = min_{t} |t(E2)\E1| = q - 1/2 max sum (a_ij b_{t(i)t(j)}),

where (a_ij) and (b_ij) are the adjacency matrices of G1 and G2 respectively.

THEOREM 1. The problems of computation of distances d1, d2, d3 are NP- complete.

PROOF: If it d1(G1, G2) = |E2|-|E1|, then it is easy to see that G1 is a subgraph of G2. The same statement is true for d2. But it is known that the subgraph isomorphism problem is NP-complete [GJ]. In the case of d3, the problem of finding of a maximum clique in a graph [GJ] is reduced to the computation of d3, since its size for a graph G if equal to n - d3(G, Kn), where Kn is the complete n-vertex graph.

THEOREM 2. The problem of computation of d4(G1, G2) is NP-complete even in the case when G1 and G2 are trees.

PROOF: Consider the following recognition problem:

TREE-DISTANCE:

INPUT: Trees G1(V, E1), G2(V, E2) and an integer B'.

PROPERTY: There exists a permutation t such that |t(E2)\E1| is at most B'.

It is known [GJ] that the following THREE-PARTITION problem is NP-complete in strong sense:

THREE-PARTITION:

INPUT: A set A={a_i} of 3m elements, an integer B and positive integer sizes s(a_i) such that

B/4 <= s(a_i) <= B/2, i = 1,... 3m, (1)

sum s(a_i) = Bm, where sum is over all a_i in A. (2)

PROPERTY: It is possible to partition A into m disjoint subsets A_j such that

sum s(a_i) = B (3)

for all j = 1,...m, where the sum is over all elements a_i in A_j.

Notice that conditions (1)-(3) imply that all A_j are 3-element sets.

Our goal is to reduce the THREE-PARTITION problem to TREE-DISTANCE problem.

Let TP1 = {A, B, s(a_1),...,s(a_m)} be an instance of THREE-PARTITION. Consider a transformation T that maps TP1 into the following instance of TREE-DISTANCE:

TD1 = T(TP1) = {B', G1(V, E1, G2(V,E2)},

such that B'=2m, E1= E'_1 + E"_1, E2= E'_2 + E"_2, where

E'_1 = {(k,0)| k==1(mod B)},

E"_1 = {(k,k-1)| k!=1(mod B)},

E'_2 = {(k,0)| k = 1 + sum_{i=1,m'} s(a_i), for all m'=1,...,3m-1},

E"_2 = {(k,k-1)| for all remaining k)

Notice that since

min_{v in V} (deg_G2(0) - deg_G1(v)) = 2m, (4)

we have d(G12, G2) >= 2m. (5)

Suppose that THREE-PARTITION has a solution {Ai}. Without loss of generality we may assume that

Ai={a_{3i-2},a_{3i-1},a_{3i}}, i =1,...m.

If we take the identity permutation t (t(i)=i for all i), we can readily verify that

|t(E2) \ E1| = 2m. (6)

Conversely, if a permutation t satisfies (6) then (4) and (5) together imply that t(0) = 0 and the edges from t(E2)\E1 are incident to 0. Then t isomorphically injects the connected components of G2\{0} (which are chains) into graph G1\{0} which is a union of m chains of length B. Clearly, this injection delivers a solution for the corresponding instance of THREE-PARTITION.

 

Summarizing

(a) an instance I of TREE-DISTANCE is accepted if and only if the instance T(I) of THREE-PARTITION is accepted;

(b) clearly, the computation of T requires time polynomial in m and B;

(c) total number of vertices in G1 and G2 is 6mB + 2, i.e., polynomial in m and B.

(d) B'=2m as clearly bounded by a polynomial in terms of the length of the corresponding instance of THREE-PARTITION. These four claims are the sufficient prerequisites for T to be a pseudo-polynomial transformation [GJ] between the two recognition problems. Since TREE-DISTANCE is clearly in class NP, it is strongly NP-complete, and the claim of Theorem 2 follows.

COROLLARY. The computation of d1 and d2 for trees is NP hard.

We may also mention that the computation of d1(G, Pn), where G is an arbitrary graph and Pn is a chain graph, is NP-hard, since this problem is equivalent to the NP-hard Hamiltonian completion problem [GH].

 

Conclusion

It is proven that a number of natural distances introduced between unlabeled graphs in literature are NP-hard, i.e., computationally intractable. Finding an easily computable definition of distance between graphs or hypergraphs is a possible way for fast, automated discrepancy analysis in LVS systems.

 

References

  1. [GJ] Garey, R.M. and D.S. Johnson. Computers and Intractability, Freeman and Co., 1979.
  2. [GH] Goodman, S., and S. Hedetniemi. On the Hamiltonian completion problem. Lecture Notes in Math., 406(1974), 262-272.
  3. [MK79] Metelski, N.N and N.M. Korneyenko, Metrization of a class of graphs.- Doklady Akademii Nauk BSSR, 23(1979), 5-7.
  4. [M79] Mironov, A.A., Some properties of numbers realized by a graph.- Trudy Moskovskogo Instituta Inzenerov, 1979, No. 640, 115-120.
  5. [Z75] Zelinka, B., On a certain distance between isomorphism casses of graphs.- Casopis pro Pestovanej Matematiky, 100(1975), 371-373