A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis

A recently introduced graph-theoretic notion of signed hypergraph is studied. In particular, a structural characterization of balanced signed hypergraphs is given, and two optimization problems related to the balance property – the maximum balance and the minimum covering problems – are introduced and characterized. It is shown that both problems are NP-complete in general. Applications of the theory of signed hypergraphs to two VLSI optimization problems, namely via minimization and constrained logic encoding, are described.