Minimum Self-Dual Decompositions of Positive Dual-Minor Boolean Functions
Jan C. Bioch, Toshihide Ibaraki, Kazuhisa Makino · EUR Research Repository (Erasmus University Rotterdam) · 1997
Abstract In this paper we consider decompositions of a positive dual-minor Boolean function f into f = f 1 f 2 ,…, f k , where all f j are positive and self-dual. It is shown that the minimum k having such a decomposition equals the chromatic number of a graph associated with f , and the problem of deciding whether a decomposition of size k exists is co-NP-hard, for k ⩾2. We also consider the canonical decomposition of f and show that the complexity of finding a canonical decomposition is equivalent to deciding whether two positive Boolean functions are mutually dual. Finally, for the class of path functions including the class of positive read-once functions, we show that the sizes of minimum decompositions and minimum canonical decompositions are equal, and present a polynomial total time algorithm to generate all minimal canonical decompositions.