Trees and branchings

Problems in this category

• Capacitated packing of k-arborescences
• Decomposing rooted (k,l)-connected graphs into rooted k-connected parts
• Decomposition into forests and a bounded-degree subgraph
• Decomposition into two trees with orientation constraints
• Decomposition of oriented k-partition-connected digraphs
• Disjoint spanning in- and out-arborescences
• Disjoint strongly connected spanning subgraphs
• Edge-disjoint spanning trees and paths
• Edge-disjoint T-connectors
• Edge-independent spanning trees
• Goddyn's conjecture on thin spanning trees
• In-degree bounded directed forests
• Independent arborescences in acyclic digraphs
• Independent trees
• Kriesell's conjecture
• Making the union of two directed spanning trees strongly connected
• Partitionability to a tree and a spanning tree
• Strongly edge-disjoint arborescences
• Union of a spanning arborescence and a directed spanning tree

Introduction

A seminal result of Edmonds is his disjoint arborescences theorem:

Theorem (Edmonds) Let D=(V,A) be a digraph with a designated root node r. D contains k edge-disjoint spanning arborescences rooted at r if and only if [math]\varrho(X)\geq k[/math] for each nonempty [math]X\subseteq V-r[/math].

This theorem gave rise to several applications on packing and covering (see e.g. ). Its undirected counterpart is Tutte's theorem:

Theorem (Tutte). An undirected graph G=(V,E) contains k edge-disjoint spanning trees if and only if if it is k-partition-connected.

In this survey we try to point out that there are still several possible directions for generalizing these classical results.

Capacitated and in-degree constrained versions

A natural generalization of Edmonds' theorem could possibly be obtained by replacing spanning arborescences by k-arborescences:

Let D=(V,A) be a digraph with arc-capacities [math] c : A \to \mathbb{N}[/math] and a root node [math]r_0\in V[/math]. A k-arborescence is the arc-disjoint union of k spanning arborescences rooted at [math]r_0[/math]. Is it true that if [math]c(a)\leq l[/math] for every [math]a \in A[/math] and there is a capacity-obeying packing of kl spanning arborescences, then there is a capacity-obeying packing of l k-arborescences?

This can also be seen as a common bases packing problem, or as the integer decomposition property of the polyhedron of k-arborescences.

Another conjecture that would extend Edmonds' result concerns the decomposition of oriented k-partition-connected digraphs. We are given a digraph so that the underlying graph satisfies the condition in Tutte's theorem. We are interested in a decomposition to spanning subgraphs with an additional constraint.

Let D=(V,A) be a digraph whose underlying graph is k-partition-connected, and let [math]r_0 \in V[/math] be a node of in-degree 0. Suppose that the in-degree of every other node is at least k. Is it true that D can be decomposed into k weakly connected spanning subgraphs, so that every node [math]v \in V-r_0[/math] has positive in-degree in each subgraph?

Independent trees and arc-disjoint arborescences

Spanning trees and arborescences correspond to edge-connectivity. Natural analogues of these concepts for node connectivity are independent and strongly independent trees.

In a graph G=(V,E) with a root node r, two spanning trees [math]T_1[/math] and [math]T_2[/math] are called r-independent if for any node x in V-r, the unique paths between r and x in [math]T_1[/math] and [math]T_2[/math] are internally node disjoint. Is it true that if G is k-connected then there exist k r-independent trees for arbitrary r?

The directed version of this conjecture is not true in general, however, it might be still interesting to find classes of graph where it holds.

A somewhat similar question is obtained if we do not require internally node disjoint paths, but forbid only oppositely directed pairs of edges. The conjecture that the condition of Edmonds' theorem is sufficient in this case has been disproved.

Steiner trees

A natural question is replacing spanning trees/arborescences by Steiner-trees/arborescences: each tree should contain a subset [math]T\subseteq V[/math] of nodes, or in the directed case, arborescence should contain directed paths from the root r to each node in a given set [math]T\subseteq V[/math]. Both in the directed and undirected cases, the question whether k disjoint Steiner-trees/arborescences exist is NP-complete already for k=2. Still, an interesting question is to find nice sufficient conditions.

Kriesell proposed the following conjecture concerning the existence of disjoint Steiner trees:

Let G=(V,E) be a graph, and [math]T \subseteq V[/math]. Is it true that if T is 2k-edge-connected in G (i.e. there are 2k edge-disjoint paths between any two nodes of T), then G contains k edge-disjoint Steiner trees for T?

Convex node sets

Returning to digraphs, one may be interested in special cases of Steiner arborescences where the problem is polynomially solvable. The first such interesting result - several decades after the theorem of Edmonds - was found by Kamiyama, Katoh and Takizawa. This was followed by an extension due to Fujishige , with a simpler proof by Cs. Király .

Theorem (Fujishige) In the digraph D=(V,A), assume we are given k roots [math]r_1,\ldots,r_k[/math] and convex node sets [math]T_1,\ldots,T_k[/math] so that [math]r_i \in T_i[/math]. Then there are edge-disjoint arborescences [math]F_i[/math] so that [math]F_i[/math] is rooted at [math]r_i[/math] and spans [math]T_i[/math] for i=1,...,k if and only if [math]\rho_D(Z)\ge p_1(Z)[/math] for every subset [math]Z\subseteq V[/math], where [math]p_1(Z)[/math] denotes the number of sets [math]T_i[/math] intersecting Z with [math]r_i\notin Z[/math].

For acyclic graphs, it is known that if the graph is rooted k-connected then it contains k independent spanning trees. A strengthening of this would be the following:

Let D=(V,A) be an acyclic digraph with designated root-nodes [math]r_1,...,r_k\in V[/math]. Let [math]U_1,...,U_k[/math] be convex node sets with [math]r_i\in U_i[/math]. Is it true that there exist independent [math]r_i[/math]-arborescences [math]F_i[/math] with [math]V(F_i)=U_i[/math] if and only if there exist openly node-disjoint [math]r_i-v[/math] paths [math]P_i[/math] ([math]v\in U_i[/math]) for each [math]v\in V[/math]? (We call the [math]r_i-v[/math] and [math]r_j-v[/math] paths [math]P_i[/math] and [math]P_j[/math] openly node-disjoint if they are edge-disjoint and [math]V(P_i)\cap V(P_j)=\{v\}\cup(\{r_i\}\cap\{r_j\})[/math].)

A survey on further results in this direction can be found in .

Further simple decompositions

Based on Tutte's theorem it is easy to decide whether an undirected graph is the union of k spanning trees. Somewhat surprisingly, it is NP-complete to decide whether it is the union of two (not necessarly spanning) trees . Recently, two other related problems turned out to be hard: the partitionability to a tree and a spanning tree was proven to be NP-complete by Bernáth and Király , while Bang-Jensen and Yeo showed that it is NP-complete to decide if a digraph is the union of a spanning arborescence and a directed spanning tree.

One remaining open problem is the following question question of Thomassen:

Does there exist a value k so that in every k-arc-connected directed graph D=(V,A) and for every node [math]v\in V[/math], there is a spanning in-arborescence and a disjoint spanning out-arborescence rooted in v?

It is NP-complete to decide whether a graph satisfies the above property. However, it is surprising that no sufficient condition is known in terms of connectivity.