Finding small OBDDs for incompletely specified truth tables is hard

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

  • Department of Computer Science
  • Teoretisk naturvidenskab
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
Original languageEnglish
JournalElectronic Colloquium on Computational Complexity
IssueTR06-004
Pages (from-to)1-6
ISSN1433-8092
Publication statusPublished - 2006

See relations at Aarhus University Citationformats

ID: 689284