ECCC-Report TR06-004https://eccc.weizmann.ac.il/report/2006/004Comments and Revisions published for TR06-004en-usTue, 10 Jan 2006 09:05:52 +0200
Paper TR06-004
| Finding small OBDDs for incompletely specified truth tables is hard |
Jesper Torp Kristensen,
Peter Bro Miltersen
https://eccc.weizmann.ac.il/report/2006/004We 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.
Tue, 10 Jan 2006 09:05:52 +0200https://eccc.weizmann.ac.il/report/2006/004