Effect of Influential Variable Based Variable-Ordering Heuristic in Small-World Networks
Tenda Okimoto, Katsutoshi Hirayama · 2023
Constraint Satisfaction Problem (CSP) is a fundamental problem that can formalize various applications of Artificial Intelligence. CSP can be represented by using a graph, called a constraint network. In a constraint network, some nodes/variables have a significant influence on the global result such as backbone and influential variables. The backbone is a variable which takes the same value for all satisfiable solutions in a CSP. The influential variable is a variable if it enables a given CSP satisfiable and also unsatisfiable. The existence of such variables leads to the simplification of a given problem. As far as the authors are aware, there exists few works focused on identifying the existence of backbone and influential variables in different network structures such as small-world networks. In this paper, the main focus is laid on the existence of influential variables in small-world networks. The number of influential and also backbone variables in random and small-world networks is investigated on the number of benchmarks. Furthermore, a novel influential variable based variable-ordering heuristic is proposed that is specialized to small-world networks. In the experiments, the effect of the influential variable based variable-ordering heuristic is investigated on the number of benchmarks.