Changes
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''?
</onlyinclude>
[[File:solved_b.jpg]]
It was shown by {{ColourA|Olivier Durand de Gevigney}} <ref name="Du"/> 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 <ref>D. Pálvölgyi, ''Partitionability to two trees is NP-complete'', [http:name="Pa"//www.cs.elte.hu/egres/qp/egresqp-06-06.pdf EGRES Quick Proof No. 2006-06].</ref> 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.
==References==
<references><ref name="Pa">D. Pálvölgyi, ''Partitionability to two trees is NP-complete'', [http://www.cs.elte.hu/egres/qp/egresqp-06-06.pdf EGRES Quick Proof No. 2006-06].</ref> <ref name="Du"> O. Durand de Gevigney, ''Decomposition into two trees with orientation constraints'', [http://arxiv.org/abs/1304.3613 arXiv link].</ref> </references>
[[Category:Orientations]]
[[Category:Trees and branchings]]
[[Category:Open Problems]]
