We prove that the problem of deciding whether the edge set of a graph can be partitioned into two spanning trees such that each tree has an orientation with specified out-degrees is NP-complete. Provided that P ≠NP, this disproves a conjecture of Recski (2011).
展开▼