Elsevier

Information and Computation

Volume 172, Issue 2, 29 January 2002, Pages 103-138
Information and Computation

Regular Article
The Nonapproximability of OBDD Minimization

https://doi.org/10.1006/inco.2001.3076Get rights and content
Under an Elsevier user license
open archive

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, unless P=NP, for each constant c>1 there is no polynomial time approximation algorithm with the performance ratio c for the variable ordering problem, i.e., no polynomial time algorithm that guarantees the computation of a variable ordering so that the resulting OBDD size is larger than the minimum size by a factor of at most c. This result justifies, also from a theoretical point of view, the use of heuristics for the variable ordering problem.

Cited by (0)

An extended abstract of some results of this paper appeared in the Proceedings of STACS'98 [31]. The author was supported in part by DFG Grant We 1066/8. Correspondence should be addressed to Detlef Sieling, Universität Dortmund, Lehrstuhl Informatik 2, 44221 Dortmund, Fed. Rep. of Germany.

f1

[email protected]