research-article

Improving the Variable Ordering of OBDDs Is NP-Complete

Authors:

Ingo WegenerAuthors Info & Claims

IEEE Transactions on Computers, Volume 45, Issue 9

Pages 993 - 1002

https://doi.org/10.1109/12.537122

Published: 01 September 1996 Publication History

Abstract

Ordered binary decision diagrams are a useful representation of Boolean functions, if a good variable ordering is known. Variable orderings are computed by heuristic algorithms and then improved with local search and simulated annealing algorithms. This approach is based on the conjecture that the following problem is NP-complete. Given an OBDD G representing f and a size bound s, does there exist an OBDD G* (respecting an arbitrary variable ordering) representing f with at most s nodes? This conjecture is proved.

References

[1]

B. Bollig M. Löbbing and I. Wegener, "Simulated Annealing to Improve Variable Orderings for OBDDs," Proc. Int'l Workshop Logic Synthesis, pp. 5.1-5.10, 1995.

[2]

R.E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulations," IEEE Trans. Computers, vol. 35, no. 8, pp. 677-691, Aug. 1986.

Digital Library

[3]

R.E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams," ACM Computing Surveys, vol. 24, no. 3, pp. 293-318, Sept. 1992.

Digital Library

[4]

K.M. Butler D.E. Ross R. Kapur and M.R. Mercer, "Heuristics to Compute Variable Orderings for Efficient Manipulation of Ordered Binary Decision Diagrams," Proc. 28th ACM/IEEE Design Automation Conf., pp. 417-420, 1991.

Digital Library

[5]

S. Fortune J. Hopcroft and E.M. Schmidt, "The Complexity of Equivalence and Containment for Free Single Variable Program Schemes," Proc. Int'l Colloquium Automata, Languages, and Programming, Lecture Notes in Computer Science 62, pp. 227-240, 1978.

Digital Library

[6]

S.J. Friedman and K.J. Supowit, "Finding the Optimal Variable Ordering for Binary Decision Diagrams," IEEE Trans. Computers, vol. 39, no. 5, pp. 710-713, May 1990.

Digital Library

[7]

M. Fujita H. Fujisawa and N. Kawato, "Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams," Proc. IEEE Int'l Conf. Computer Aided Design, pp. 2-5, 1988.

[8]

M. Fujita Y. Matsunaga and T. Kakuda, "On variable Ordering of Binary Decision Diagrams for the Application of Multi-Level Logic Synthesis," Proc. European Design Automation Conf., pp. 50-54, 1991.

Digital Library

[9]

M.R. Garey and D.B. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness. New York: W.H. Freeman, 1979.

Digital Library

[10]

N. Ishiura H. Sawada and S. Yajima, "Minimization of Binary Decision Diagrams Based on Exchanges of Variables," Proc. IEEE Int'l Conf. Computer Aided Design, pp. 472-475, 1991.

[11]

S. Malik A.R. Wang R.K. Brayton and A. Sangiovanni-Vincentelli, "Logic Verification Using Binary Decision Diagrams in a Logic Synthesis Environment," Proc. IEEE Int'l Conf. Computer Aided Design, pp. 6-9, 1988.

[12]

M.R. Mercer R. Kapur and D.E. Ross, "Functional Approaches to Generating Orderings for Efficient Symbolic Representation," Proc. 29th ACM/IEEE Design Automation Conf, pp. 614-619, 1992.

Digital Library

[13]

S. Minato N. Ishiura and S. Yajima, "Shared Binary Decision Diagrams with Attributed Edges for Efficient Boolean Function Manipulation," Proc. 27th ACM/IEEE Design Automation Conf., pp. 52-57, 1990.

Digital Library

[14]

D.E. Ross K. M. Butler R. Kapur and M.R. Mercer, "Fast Functional Evaluation of Candidate OBDD Variable Ordering," Proc. European Design Automation Conf., pp. 4-10, 1991.

Digital Library

[15]

R. Rudell, "Dynamic Variable Ordering for Ordered Binary Decision Diagrams," Proc. IEEE Int'l Conf. Computer Aided Design, pp. 42-47, 1993.

Digital Library

[16]

D. Sieling and I. Wegener, "Reduction of OBDDs in Linear Time," Information Processing Letters, vol. 48, pp. 139-144, 1993.

Digital Library

[17]

D. Sieling and I. Wegener, "NC-Algorithms for Operations on Binary Decision Diagrams," Parallel Processing Letters, vol. 3, no. 1, pp. 3-12, 1993.

[18]

S. Tani K. Hamaguchi and S. Yajima, "The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram," Proc. 4th Int'l Symp. Algorithms and Computation, Lecture Notes in Computer Science 762, pp. 389-398, 1993.

Digital Library

Cited By

Dubslaff CHusung NKäfer N(2024)Configuring BDD Compilation Techniques for Feature ModelsProceedings of the 28th ACM International Systems and Software Product Line Conference10.1145/3646548.3676538(209-216)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3646548.3676538
Heß TSemmler SSundermann CTorán JThüm T(2024)Towards Deterministic Compilation of Binary Decision Diagrams From Feature ModelsProceedings of the 28th ACM International Systems and Software Product Line Conference10.1145/3646548.3672598(136-147)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3646548.3672598
Chavanon CBesson FNinet TTimany ATraytel DPientka BBlazy S(2024)PfComp: A Verified Compiler for Packet Filtering Leveraging Binary Decision DiagramsProceedings of the 13th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3636501.3636954(89-102)Online publication date: 9-Jan-2024
https://dl.acm.org/doi/10.1145/3636501.3636954
Show More Cited By

Index Terms

Improving the Variable Ordering of OBDDs Is NP-Complete
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...
Clique-Width is NP-Complete

Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in monadic second-order logic with second-order quantification on vertex sets, which includes NP-hard problems ...
Properties of NP-Complete Sets

We study several properties of sets that are complete for NP. We prove that if L is an NP-complete set and S \not\supseteq L is a p-selective sparse set, then L - S is \leq ^p_m-hard for NP. We demonstrate the existence of a sparse set S \in DTIME(2^2ⁿ) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 45, Issue 9

September 1996

98 pages

ISSN:0018-9340

Editor:
Jane W. S. Liu
Univ. of Illinois, Urbana

Issue’s Table of Contents

Copyright © Copyright © 1996 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 September 1996

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

144
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dubslaff CHusung NKäfer N(2024)Configuring BDD Compilation Techniques for Feature ModelsProceedings of the 28th ACM International Systems and Software Product Line Conference10.1145/3646548.3676538(209-216)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3646548.3676538
Heß TSemmler SSundermann CTorán JThüm T(2024)Towards Deterministic Compilation of Binary Decision Diagrams From Feature ModelsProceedings of the 28th ACM International Systems and Software Product Line Conference10.1145/3646548.3672598(136-147)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3646548.3672598
Chavanon CBesson FNinet TTimany ATraytel DPientka BBlazy S(2024)PfComp: A Verified Compiler for Packet Filtering Leveraging Binary Decision DiagramsProceedings of the 13th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3636501.3636954(89-102)Online publication date: 9-Jan-2024
https://dl.acm.org/doi/10.1145/3636501.3636954
Bhushan MGalindo Duarte JNegi ASamant P(2024)An ontological knowledge-based method for handling feature model defects due to dead featureEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.109000136:PBOnline publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1016/j.engappai.2024.109000
Abdalhaq BHawash AAwad A(2024)Diversity enforced Genetic Algorithm (GA) for Binary Decision Diagram (BDD) reorderingApplied Soft Computing10.1016/j.asoc.2024.111453155:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111453
Wangmo CWiese L(2024)An Experimental Evaluation of Summarisation-Based Frequent Subgraph Mining for Subgraph SearchingSN Computer Science10.1007/s42979-024-03006-w5:6Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/s42979-024-03006-w
Dai AYing M(2024)QReach: A Reachability Analysis Tool for Quantum Markov ChainsComputer Aided Verification10.1007/978-3-031-65633-0_23(520-532)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65633-0_23
Patel RKhalil E(2024)LEO: Learning Efficient Orderings for Multiobjective Binary Decision DiagramsIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-031-60599-4_6(83-110)Online publication date: 28-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60599-4_6
Husung NDubslaff CHermanns HKöhl M(2024)OxiDDTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-031-57256-2_13(255-275)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57256-2_13
Florio AMartins PSchiffer MSerra TVidal TWilliams BChen YNeville J(2023)Optimal decision diagrams for classificationProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i6.25920(7577-7585)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i6.25920
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents