TY - JOUR
T1 - Finding small OBDDs for incompletely specified truth tables is hard
AU - Kristensen, Jesper Torp
AU - Miltersen, Peter Bro
PY - 2006
Y1 - 2006
N2 - 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
AB - 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
M3 - Journal article
SN - 1433-8092
SP - 1
EP - 6
JO - Electronic Colloquium on Computational Complexity
JF - Electronic Colloquium on Computational Complexity
IS - TR06-004
ER -