A Novel Variable Ordering Heuristic for BDD-based K-Terminal Reliability

Modern exact methods solving the NP-hard k-terminal reliability problem are based on Binary Decision Diagrams (BDDs). The system redundancy structure represented by the input graph is converted into a BDD whose size highly depends on the predetermined variable ordering. As finding the optimal available ordering has exponential complexity, a heuristic must be used. Currently, the breadth-first-search is considered to be state-of-the-art. Based on Hardy´s decomposition approach, we derive a novel static heuristic which yields significantly smaller BDD sizes for a wide variety of network structures, especially irregular ones. As a result, runtime and memory requirements can be drastically reduced for BDD-based reliability methods. Applying the decomposition method with the new heuristic to three medium-sized irregular networks from the literature, an average speedup of around 9,400 is gained and the memory consumption drops to less than 0.1 percent.