Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice

摘要

A binary decision diagram (BDD) is a graph-based data structure representing Boolean functions; l-BDDs are BDDs with an additional restriction that each input bit can be tested at most l times. A d-uniform hypergraph H on N vertices is an exactly half-d-hyperclique if N/2 of its vertices form a hyperclique and the remaining vertices are isolated. Wegener [J. ACM 35(2), 461-471 (1988)] conjectured that there is no polynomial-size (d - 1)-BDD for the Exactly half-d-hyperclique problem. We refute this conjecture by constructing polynomial-size (syntactic) 2-BDDs For the Exactly half-d-hyperclique problem for every d ≥ 2.