A new class of node-splitting problems and applications

A new class of node-splitting problems for graphs is introduced and studied. The goal of the splitting process is to minimize the number of node-splitting operations needed to transform a given input graph into a new graph that has a property (bipartite, planar, nonseparable, etc.) that the original graph does not have. It is shown that the node splitting problem is NP-complete when the property involved is bipartite or acyclic. It is also shown that the problem has efficient polynomial-time solutions when the property sought is tree, null, complete, degree-constrained, and nonseparability. It is proved that the node-splitting problem for a previously proposed formulation is also NP-complete. Applications of this problem in CAD/VLSI design and networks are also discussed