Decomposition into two trees with orientation constraints

From Egres Open
Jump to: navigation, search

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?

Solved b.jpg

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


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.


  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.