Filtering for a Tree and Path Partitioning Constraint
(joint work with Xavier Lorca and Pierre Flener)

Within the context of directed graphs we present a tree partitioning
constraint which also considers additional side constraints such as
precedence, incomparability and degree constraints. Degree constraints
allow for instance to state that we want to obtain binary trees or
paths. Precedence and incomparability constraints have some practical
utilisation both in the context of trees and paths (e.g., phylogeny,
pick up delivery).

Within this context, we describe several type of filtering:

1. The first type of filtering is based on bounds on the number of
   trees/path needed for covering the graph.  
2. The second type of filtering is based on the structure of the graph
   to partition (i.e., the reduced graph, the strong articulation
   points of a given strongly connected component, the way two
   strongly connected components are inter-connected). 
3. The third type combines the graph to partition with the precedence
   and/or the incomparability graphs in order to deduce new
   constraints (e.g., new precedence constraints, new incomparability
   constraints, ...). Finally we discuss the implementation challenges
   behind such a constraint.