TR06-004 Authors: Jesper Torp Kristensen, Peter Bro Miltersen

Publication: 10th January 2006 09:05

Downloads: 1200

Keywords:

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.