On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization
Detlef Sieling · 1998
Abstract The size of Ordered Binary Decision Diagrams (OBDDs) is determined by the chosen variable ordering. A poor choice may cause an OBDD to be too large to fit into the available memory. The decision variant of the variable ordering problem is known to be ¡£¢-complete. We strengthen this result by showing that there in no polynomial time approximation scheme for the variable ordering problem unless ¢¥¤¥¡£¢. We also prove a small lower bound on the performance ratio of a polynomial time approximation algorithm under the assumption ¢§ ¦ ¤¥¡£¢