Finding small OBDDs for incompletely specified truth tables is hard
Jesper Kristensen, Peter Bro Miltersen · 2006
Abstract. We present an efficient reduction mapping undirected graphs G with n = 2 k vertices for integers k to tables of partially specified Boolean functions g: {0, 1} 4k+1 → {0, 1, ⊥} so that for any integer m, G has a vertex colouring using m colours if and only if g has a consistent ordered binary decision diagram with at most (2m + 2)n 2 + 4n decision nodes. From this it follows that the problem of finding a minimum-sized consistent OBDD for an incompletely specified truth table is NP-hard and also hard to approximate. 1