# Decomposition into two trees with orientation constraints

Let G=(V,E) be a connected graph with $|V|=n$ and $|E|=2n-2$. For each $v\in V$ two non-negative integers a(v) and b(v) are given so that $\sum_{v\in V} a(v)=\sum_{v\in V} b(v)=n-1.$ Can we decide in polynomial time whether E can be partitioned into two trees $T_1$ and $T_2$ such that $T_1$ and $T_2$ have orientations with in-degrees a(v) and b(v) respectively for each node v?

It was shown by Olivier Durand de Gevigney [1] that the problem is NP-complete.

## Remarks

The problem was proposed by András Recski. Notice that if G=(V,E) is a connected graph and non-negative integers a(v) are given so that $\sum_{v\in V} a(v)=n-1,$ then we can decide whether there is a tree T in G that has an orientation with in-degree a(v) for each node v by using Edmonds' matroid intersection theorem.

On a slightly related note, Pálvölgyi [2] proved that it is NP-complete to decide whether a graph can be decomposed into two (not necessarily spanning) trees.

Prescribing only upper bounds on the in-degrees, one may ask the following general question.

Let D=(V,A) be a digraph, and $u: V \to {\mathbb Z_+}$. When does D contain k edge-disjoint directed spanning trees so that in each directed spanning tree the in-degree of v is at most u(v)?

In the special case in-degree bounded directed forests the simple conjecture turned out to be false.

## References

1. O. Durand de Gevigney, Decomposition into two trees with orientation constraints, arXiv link.
2. D. Pálvölgyi, Partitionability to two trees is NP-complete, EGRES Quick Proof No. 2006-06.