Search algorithms for exact treewidth.

摘要

Treewidth is a fundamental property of a graph that has implications for many hard graph theoretic problems. NP-hard problems such as graph coloring and Hamiltonian circuit can be solved in polynomial time if the treewidth of the input graph is bounded by a constant. Given a graph, we can find its treewidth, or an approximation of its treewidth, by examining one of a number of compilations of the graph including vertex elimination orders, tree decompositions, and graph triangulations. Each of these compilations has a parameter referred to as its width, and they are optimal if their width is minimal. This minimal width is what we call the treewidth of a graph. Areas of artificial intelligence research, including Bayesian networks, constraint programming, and knowledge representation and reasoning, are based on queries and operations that are frequently infeasible without optimal or near-optimal vertex elimination orders, tree-decompositions, or other similar compilations. This dissertation deals with techniques for constructing these compilations optimally and finding the exact treewidth of a graph.Finding exact treewidth and optimal elimination orders are NP-complete problems. This dissertation describes techniques that use a heuristic search approach to prune large parts of the treewidth solution space and find exact treewidth quickly on hard benchmark instances. The final result is a state-of-the-art algorithm for finding optimal elimination orders and exact treewidth. The algorithm uses a depth-first search with a variety of pruning techniques. The performance of previous depth-first algorithms suffered due to a large number of duplicate node expansions. Common methods for detecting and eliminating duplicate nodes rely on a large amount of memory. The techniques introduced here eliminate all duplicate nodes while only requiring a small amount of memory in practice.Furthermore, the search space used to find exact treewidth is unusual in that the cost of a solution path is the maximum edge cost on the path. There has been little previous research on problems such as this in the heuristic search literature. This dissertation includes several novel results related to heuristic search with a maximum edge cost function.