Complexity of K-Tree Structured Constraint Satisfaction Problems

Eugene C. Freuder

Trees have played a key role in the study of constraint satisfaction problems because problems with tree structure can be solved efficiently. It is shown here that a family of generalized trees, k-trees, can offer increasing representational complexity for constraint satisfaction problems, while maintaining a bound on computational complexity linear in the number of variables and exponential in k. Additional results are obtained for larger classes of graphs known as partial k-trees. These methods may be helpful even when the original problem does not have k-tree or partial k-tree structure. Specific tradeoffs are suggested between representational power and computational complexity.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.