Circuit Verification via Hypergraph Realization
One of the most challenging and time consuming tasks in VLSI design automation is Layout Versus Schematic (LVS). The problem is to test the consistency between the actual circuit, represented by the layout, and the nominal circuit upon which the design was based. From mathematical point of view the core problem is the Hypergraph Isomorphism Problem (HIP).
Unfortunately, it is known as NP-hard, so (as for most of CAD problems) it is extremely important to investigate the frequently encountered particular cases. It is well-known fact that particular case of HIP - Graph Isomorphism Problem - becomes easy solvable when input graphs are planar or have bounded parameters . Following this association, the series of investigations were done for estimation of complexity of the HIP in case of planar hypergraphs. Despite of this problem was proven as NP-hard even for very restricted input parameters, some polynomial-time algorithms were invented for cases when most of hyperedges (they correspond to particular VLSI subcircuits) have the bounded capacity. Fortunately, the classified polynomially-solvable for planarity test hypergraphs are in the same time (being planar) easy checkable on isomorphism. This provides the real breakthrough in efficiency of LVS tools used in Celebrity (Silvaco suite for VLSI Design Automation) for wide class of integrated circuits.
The presented approach is based on investigations presented in [1-5]. First of all, we need to present some formal mathematical definitions.
Let H=(X, R) is hypergraph with set of
vertices X={x(i)},i = 1,..,n and
set of edges R={R(j)}, j = 1,..,h, where every
edge is arbitrary subset of vertices.
The realization of hypergraph H is such a graph G=(X, E) for which:
1) every induced subgraph <R(j)> in graph G is connected,
2) for each edge xy of graph G there exists the edge R(j) of hypergraph H which contains both x and y.
The degree d(x) of vertex x is the number of edges from H containing x. Hypergraph H is called linear if every two edges have no more than one common vertex.
The Hypergraph Planarity Problem (HPP) is formulated as follows: Given a hypergraph H=(X, R), to determine, is there exists its planar realization.
Hypergraph H is called planar, if such (planar) realization exists for H.
NP-completeness of HPP is established independently in [1] and [2]. More over, there was proven [3] that problem remains NP-complete even in cases when the following hypergraph parameters are bounded: cardinality of every edge (|R(j)|<= 8) or maximal degree of vertex (d(x)<=2 ). Besides, it is not difficult to show NP-completeness of HPP even for linear hypergraphs. Obviously, if |R(j)| <= 2 then HPP becomes polynomially solvable because it is reduced to the simple graph planarity test. From other side, beginning from |R(j)|<= 8 this problem becomes NP-complete. In the cases when upper bound on edge size takes values from the set {3,4,5,6,7}, the question of problem complexity remains open.
The main goal of this article is to present additional conditions, providing polynomial complexity for Hypergraph Planarity Problem solution.
Hypergraphs of Bounded Degree
Let |R(j)| <= 3 for all j=1,..,h . As it was mentioned, namely from this moment the HPP becomes non trivial. Besides, for wide class of VLSI circuits about 90% of signal subcircuits (corresponding to edges of hypergraph) contain not more than three vertices. More than half from these subcircuits are, as rule 2-contact, i.e. contain exactly 2 vertices. These give us the background to introduce in consideration the set of 2-edges P - all edges consisting of 2 vertices, and graph of 2-edges G=(Y, P) , (Y is subset of X) induced from H by set of 2 edges P. This graph is subgraph of any realization of hypergraph H. Note, the analysis of graph of 2-edges has a key importance while creating of restricted exhaustion algorithms for detecting of hypergraph planarity.
It is clear, that if G is non-planar, then H is non planar. So, we can consider graph G planar without loss of generality.
Now suppose, that hypergraph H does satisfy the following:
Condition A. Every edge consists of three or less vertices, graph of 2-edges is 3-connected and set of its vertices consists of all vertices of hypergraph (Y=X).
Now we will show how this condition provides polynomial feasibility of HPP.
Let us RR=R-P. Without loss of generality, consider, that RR={R(i)}, i=1,..,t and R(i)={x(i),y(i),z(i)}. For each R(i), put in correspondence the triple of edges T(i) ={x(i)y(i), x(i)z(i), y(i)z(i)}. Then, graph A=(X, Union(E,P)) will be realization of hypergraph H = (X, R), if it contains minimum two edges from each triple T(i).
Assign now to each edge e(j) from set T = Union{T(i)} , i=1,..,t the Boolean variable a(j).
It takes the value 1 , if e(j) belongs to E, and value 0 otherwise. Then, for every triple T(i)={e(k),e(l),e(m)} build the set of disjunctions S(i)={a(k) V a(m), a(l) V a(m), a(k) V a(l)}. All true-implying sets for S(i) directly correspond namely to those subsets from T(i) which consist pf more than one element. This is why graph A will be realization of H if and only if when E consists of precisely from those e(j), which correspond to some true implying set from set of disjunctions S=Union{S(i)}.
Because of graph G is 3-connected, the addition of edge from E to G does not violate the planarity only if vertices jointed by this edge belong to the common graph face. Assume a,b,c,d are vertices of bounding cycle for some face C of graph A (written in original cycle-resided succession). Then, a pair of edges (ac, bd) of graph A will be called conflict pair in relation to face C. Obviously, graph, obtained from A by adding of edge set {ac,bd}, is non planar.
To take into account the planarity of A, it is necessary to extract the set K={(e(l),e(m))} consisting the all conflict pairs of edges from T in relation to faces of graph G. The condition of planarity is equivalent to the presence in E not more than one edge from each pair belonging to K. This, in turn, corresponds to satisfying the disjunction set B={Union{a(l) V a(m)}}.
So, HPP is reduced to the problem of construction of satisfiable set on the set {a(j)} for set of disjunctions Union(S, B).
Note, each disjunction consists of not more than two literals. Therefore, we have the well-known task 2- Satisfying of for which the polynomial-time algorithm exists [7]. The time, required for this algorithm is estimated in our case as O(|T| * |UNION(S, B)|). The construction of K (set of conflict edges) requires, obviously, not more than O(|CC| * |R| ^2), where CC is the set faces of graph G. Taking in account, that |CC|=O(|X|) and |Union(S, B)|=O(|R|), we will obtain the worst-case estimation for testing of planarity of graph satisfying the Condition A as low as O(|X| * |R| ^2+|R|^3).
Linear Hypergraphs
Consider now linear hypergraphs. Obviously, graphs are linear hypergraphs and (in certain sense) it is possible to consider linear hypergraphs as closest extension of graphs. Besides, namely linear hypergraphs are appeared most frequently while designing, for example, layouts of circuits with one layer of commutation. These circumstances explain the interest to investigation of conditions providing the polynomial feasibility of HPP for planar hypergraphs.
Note, that similar to previous point, the central role here plays the condition of 3-connectivity of 2-edge graph G=(X, P) of hypergraph H=(X, R). Considering the graph G planar , we introduce the set U(G), assembling all such pairs of vertices xy which belong simultaneously both to common edge of hypergraph H and common face of graph G. Note, this set includes the edges of any planar realization of H (if such realization exists). As for previous point, assume K as set of conflict pairs of edges in relation to graph G.
Condition B. , H=(X,R) - hypergraph with 3-connected graph of 2-edges and no one edge from U(G) participates in more than one pair from conflict set K.
Now we will show that Planarity Problem for linear hypergraphs satisfying the above condition is reduced to known polynomially-feasible task [8] of construction the set of edge-disjoint bases for special graphical matroids.
Consider the following sets:
I = {(i,j)} is the set of pairs of indices, corresponding to pairs of conlict edges (e(i), e(j));
I_m is the subset of I including pairs of indices of such conflict edges, one of which connects vertices of hyperedge R(m).
Now each pair of edges (e(i), e(j)) from set K is exchanged by set from 5 edges:
e_1i = x(i)a(i,j), e_1j = x(j)a(i,j), e_2i = y(i)b(i,j), e_2j = y(j)b(i,j), e_ij = a(i,j)b(i,j).
As result of this transformation, we will obtain the graph G1=(X1,E1) with set of vertices
X1=Union(X,{a(i,j)},{b(i,j)})
and set of edges
E1=U(G)-Union({e(i),e(j),e_1i,e_1j,e_2i,e_2j,e_ij}),
where (i,j) are all pairs from I.
Then, put in correspondence to each hyperedge R(i) from set R- P the subgraph G1_i=(X_i, E_i) of graph G1, induced by the set of vertices X_i= Union(R(i),Union({a(p,q),b(p,q)})), where (p,q) are taken from I_i.
Now it is easy to see, that planar realization of hypergraph H exists if and only if there exists the set of edge-disjoined trees {T(i)}, where each T(i) is spanning tree for corresponding graphs G1_i (i.e. {T(i)} are disjoined bases of respective graphical matroid).
Really, the condition of non-intersection for edge sets of mentioned trees means that edge (a(i,j) b(i,j)) taken from intersection of E_k and E_l, belongs only to one of trees T(k) and T(l) (spanning for G1_k and G1_l correspondingly).
Suppose, that for conflict pair (e(i)=x(i)y(i), e(j)=x(j)y(j)) vertices x(i),y(i) belong to hyperedge R(k), while vertices x(j),y(j) belong to hyperedge R(l). Then inclusion of edge a(i,j)b(i,j) to tree T(k) means the choice of edge e(i) from conflict pair (e(i),e(j)) for inclusion to the set of edges of planar realization for hypergraph H.
Note, to construct the target matroid for hypergraphs fitted with Condition B we need as low as O(|E(G)| * |K|) operations.
References
[1] Johnson D.S., Pollak H.O. Hypergraph Planarity and the Complexity of Drawing Venn Diagrams. J. of Graph Theory. 1987.- Vol.11, No. 3., pp. 309-325. [2] Azarenok A., Sarvanov V. The Complexity of Hypergraph planar realization. Notices of the National Academy of Science, Minsk, Ser. Phys. And Math. Sciences.-1987.-No.4., pp. 10-12. [3] Azarenok A. Computational Complexity of Graph Problems in VLSI Layout Design. Preprint (5(405)) of the Mathematical Institute, Belarussian Academy of Science, 1990. [4] Volochina A., Feinberg V. About Hypergraph Planarity. Proceedings of the National Academy of Science, Minsk. - 1984.- Vol.28, No.4, pp. 309-311. [5] Feinberg V., Levin A., Rabinovich E. VLSI Planarization: Methods, Models, Implementation. Kluwer Academic Publishers (Dardrecht/Boston/London). - 1997. [6] Zemlyachenko V., Karneyenka M., Tyshkevich R. Graph Isomorphism Problem. J.Soviet Mathematics.- 1985.- pp. 1426-1481. [7] Cook S.A. The Complexity of theorem-proving procedures. Proc. 3rd Ann. Symp. On Theory of Computing.-1971.-pp.151- 158. [8] Roskind J., Tarjan R. A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees. Math. Of Oper. Research.- 1985.-Vol.10, No. 4, pp.701-708.