Abstract
We present two constraints that partition the vertices of an undirected n</i>-vertex, m</i>-edge graph $\mathcal {G}=( \mathcal {V}, \mathcal {E})$</equationsource> into a set of vertex-disjoint trees. The first is the resource-forest</i> constraint, where we assume that a subset $\mathcal {R}\subseteq \mathcal {V}$</equationsource> of the vertices are resource</i> vertices. The constraint specifies that each tree in the forest must contain at least one resource vertex. This is the natural undirected counterpart of the tree</i> constraint (Beldiceanu et al., CP-AI-OR’05, Springer, Berlin, 2005), which partitions a directed graph into a forest of directed trees where only certain vertices can be tree roots. We describe a hybrid-consistency algorithm that runs in $\mathop {\mathcal {O}}(m+n)$</equationsource> time for the resource-forest</i> constraint, a sharp improvement over the $\mathop {\mathcal {O}}(mn)$</equationsource> bound that is known for the directed case. The second constraint is proper-forest</i>. In this variant, we do not have the requirement that each tree contains a resource, but the forest must contain only proper</i> trees, i.e., trees that have at least two vertices each. We develop a hybrid-consistency algorithm for this case whose running time is $\mathop {\mathcal {O}}(mn)$</equationsource> in the worst case, and $\mathop {\mathcal {O}}(m\sqrt{n})$</equationsource> in many (typical) cases.