Duplicate Avoidance in Depth-First Search with Applications to Treewidth

Depth-first search is effective at solving hard combinatorial problems, but if the problem space has a graph structure the same nodes may be searched many times. This can increase the size of the search exponentially. We explore two techniques that prevent this: duplicate detection and duplicate avoidance. We illustrate these techniques on the treewidth problem, a combinatorial optimization problem with applications to a variety of research areas. The bottleneck for previous treewidth algorithms is a large memory requirement. We develop a duplicate avoidance technique for treewidth and demonstrate that it significantly outperforms other algorithms when memory is limited. Additionally, we are able to find, for the first time, the treewidth of several hard benchmark graphs.

P. Alex Dow, Richard E. Korf