__
Revision #1 to TR98-001 | 19th January 1998 00:00
__
#### The Nonapproximability of OBDD Minimization Revision of: TR98-001

**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

NP-complete. We strengthen this result by showing that for each

constant c>1 there is no polynomial time approximation algorithm

with the performance ratio c for the variable ordering problem

unless P=NP. This result justifies, also from a theoretical point

of view, to use heuristics for the variable ordering problem.

__
TR98-001 | 17th December 1997 00:00
__

#### On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization

**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

NP-complete. We strengthen this result by showing that there in no

polynomial time approximation scheme for the variable ordering problem

unless P=NP. We also prove a small lower bound on the performance

ratio of a polynomial time approximation algorithm under the

assumption P\neq NP.