  We introduce a new type of fully computable problems, for DSS dedicated to
maximal spanning tree problems, based on deduction and choice: preferential
consistency problems. To show its interest, we describe a new compact
representation of preferences specific to spanning trees, identifying an
efficient maximal spanning tree sub-problem. Next, we compare this problem with
the Pareto-based multiobjective one. And at last, we propose an efficient
algorithm solving the associated preferential consistency problem.
