Complexity of K-Tree Structured Constraint Satisfaction Problems

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.

Authors

• Eugene C. Freuder Insight Centre for Data Analytics, University College Cork, Cork, Ireland

Keywords

No keywords are indexed for this paper.