## On a graph partition problem with application to VLSI layout.(English)Zbl 0764.68132

Summary: We discuss a graph partition problem with application to VLSI layout. It is not difficult to show that the general partition problem is NP- complete, so we restrict our attention to some special classes of graphs. A graph is called a circle graph if the nodes of the graph represent the chords of a circle and there is an edge between the two nodes if the corresponding chords intersects. K. J. Supowit [IEEE Trans. Computer Aided Design 6, 93-94 (1987)] had posed the partition problem of circle graphs as an open problem. However, it is also not too difficult to show that the partition problem on circle graphs remains NP-complete. We give an integer linear programming formulation for the general graph partition problem. The problem can then be solved using one of the several techniques for solving integer linear programming problems. We show that the partition problem can be solved in polynomial time if the graph is a tree. A graph is called perfect if the graph and each of its induced subgraphs have chromatic numbers equal to the maximum cardinality of its cliques. When the partition problem is restricted to perfect graphs we observe an interesting phenomenon. In the integer linear programming formulation of the partition problem we always obtain an integral solution when the graph is perfect. This phenomenon is unusual because the constraint matrix does not belong to the class of totally unimodular, balanced, or perfect matrices [M. W. Padberg, Math. Program. 6, 180-196 (1974; Zbl 0284.90061)], for which such a phenomenon is guaranteed. In our extensive experimentation we always found an optimal integral solution when the graph is perfect. We conjecture that an optimal integral solution for the perfect graph always exists. If the conjecture is true then it is likely to lead to the development of a polynomial time algorithm for some subclasses of perfect graphs, such as the interval graphs. We show that for some other subclasses of perfect graphs, such as the permutation graphs, the number of maximal cliques may be exponentially large and as such, even if the conjecture is true, may not lead to a polynomial time algorithm for the partition problem. The partition problem is the generalization of the chromatic sum problem introduced by E. Kubicka and A. Schwenk in [Introduction to chromatic sums, Proc. ACM Computer Science Conf. (1989)]. The problem was referred to as weighted coloring problem by K. J. Supowit. However, L. Lovasz in [M. Groetschel, L. Lovasz and A. Schrijver, Geometric algorithms and combinatorial optimization (1988; Zbl 0634.05001)] uses weighted coloring problem to describe a different problem. To avoid confusion we refer to it as optimum cost chromatic partition (OCCP) problem. The problem is the following: Given a graph $$G=(V,E)$$ and a cost vector $$C=\langle C_ 1,C_ 2,\dots,C_ n\rangle (| V|=n)$$, partition the vertex set $$V$$ into independent sets $$V_ 1,V_ 2,\dots,V_ k$$, $$1\leq k\leq n$$, such that $$\sum^ k_{i=1}C_ i| V_ i|$$ is minimum. If we set cost $$C_ i=i$$, then this problem reduces to the chromatic sum problem of E. Kubicka and A. Schwenk [Introduction to chromatic sums, Proc. ACM Computer Science Conf. (1989)].

### MSC:

 68R10 Graph theory (including graph drawing) in computer science 05C15 Coloring of graphs and hypergraphs 94C15 Applications of graph theory to circuits and networks 90C10 Integer programming 94C99 Circuits, networks 68R05 Combinatorics in computer science

### Citations:

Zbl 0284.90061; Zbl 0634.05001
Full Text:

### References:

  Buckingham, M.A., Circle graphs, Courant computer science rept. no. 21, (1980)  Chvatal, V., On certain polytopes associated with graphs, J. combin. theory ser. B, 18, 138-154, (1975) · Zbl 0277.05139  Even, S.; Pnueli, A.; Lempel, A., Permutation graphs and transitive graphs, J. ACM., 19, 400-410, (1972) · Zbl 0251.05113  Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman New York · Zbl 0411.68039  Gavril, F., Algorithms for a maximum clique and a maximum independent set of a circle graph, Networks, 3, 261-273, (1973) · Zbl 0259.05125  Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054  Grotschel, M.; Lovasz, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1988), Springer Berlin · Zbl 0634.05001  Harary, F., Graph theory, (1972), Addison-Wesley Reading, MA · Zbl 0797.05064  Hsu, C.P., Signal routing in integrated circuit layout, (1986), UMI Research Press  Johnson, D.S., The NP-completeness column: an going guide, J. algorithms, 6, 434-451, (1985) · Zbl 0608.68032  Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065  Khachiyan, L.G., A polynomial algorithm in linear programming, Soviet math. dokl., 20, 191-194, (1979) · Zbl 0414.90086  Kim, H., Finding a maximum independent set in a permutation graph, Inform. process. lett., 36, 19-23, (1990) · Zbl 0703.68062  Kubicka, E.; Schwenk, A., Introduction to chromatic sums, Proc. ACM computer science conf., (1989)  Padberg, M.W., Perfect zero-one matrices, Math. programming, 6, 180-196, (1974) · Zbl 0284.90061  Pinter, R.Y., River routing: methodology and analysis, ()  Supowit, K.J., Finding a maximum planar subset of a set of nets in a channel, IEEE trans. computer aided design, 6, 93-94, (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.