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∈V two non-negative integers a(v) and b(v) are given so that ∑v∈Va(v)=∑v∈Vb(v)=n−1. Can we decide in polynomial time whether E can be partitioned into two trees T1 and T2 such that T1 and T2 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 ∑v∈Va(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→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
- ↑ 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.