# Decomposition into two trees with orientation constraints

Let *G=(V,E)* be a connected graph with [math]|V|=n[/math] and [math]|E|=2n-2[/math]. For each [math]v\in V[/math] two non-negative integers *a(v)* and *b(v)* are given so that [math]\sum_{v\in V} a(v)=\sum_{v\in V} b(v)=n-1.[/math] Can we decide in polynomial time whether *E* can be partitioned into two trees [math]T_1[/math] and [math]T_2[/math] such that [math]T_1[/math] and [math]T_2[/math] 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 [math]\sum_{v\in V} a(v)=n-1,[/math] 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 [math]u: V \to {\mathbb Z_+}[/math]. 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

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