A Fast Parallel Branch and Bound Algorithm for Treewidth

In this paper, we propose a Fast Parallel Branch and Bound algorithm (FPBB) for computing tree width. FPBB searches the elimination ordering space using depth-first search approach, and employs multithreading techniques to search smaller divided spaces simultaneously. In order to protect the shared hash table without increasing the running time, we have designed a special algorithm for the readers-writers problem. We also present a new heuristic called similar group for refining search space. With other carefully chosen heuristics, FPBB performs well in computing both lower bound and upper bound on tree width, and has solved 17 benchmark graphs whose exact tree widths were previously unknown. Additionally, FPBB is an anytime algorithm, which is insensitive to initial upper bound, and is able to find exact answer quickly. Computational results show that FPBB is significantly faster than the state-of-the-art algorithm proposed by Zhou and Hansen.