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.

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.