A Criterion of Optimality of Some Parallelization Scheme for Backtrack Search Problem in Binary Trees

The backtracking is a basic combinatorial search algorithm. As many other deterministic methods it suffers from the high complexity. Fortunately the high performance computing can efficiently cope with this issue. It was observed that the structure of the search tree can dramatically affect the efficiency of a parallel search. We study the complexity of a frontal autonomous scheme for the backtrack search parallelization. In this approach several independent cores perform a number of first steps of the backtrack search. After that each core takes one sub-problem and solves it completely. Then the results are merged to select the best solution. To study the impact of the tree structure on the performance of the frontal autonomous scheme we formalize the notion of a perfectly scalable problem and prove a criterion for a search tree to fit to this class.