Two disjoint trees

Question

Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ independent if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which cover the two sets in the sense that $A_1 \subseteq V(T_1)$, $A_2 \subseteq V(T_2)$.

(I) The problem I would like to pose is to characterise the independent pairs of sets of vertices. I am not aware of any existing literature on this problem and would be grateful for suitable pointers.

In the case where $|A_1| = |A_2| = 2$, a complete characterisation was given by Seymour ("Disjoint paths in graphs") and, independently, by Thomassen ("2-Linked Graphs"). Essentially, up to a reduction step, the pair $(\{x_1, y_1 \}, \{x_2, y_2\})$ is independent unless $G$ has a drawing in the plane with one face containing these four specified vertices in order $(x_1, x_2, y_1, y_2)$, which is an obvious obstruction to the existence of two disjoint trees covering the sets.

A complete characterisation of the general case might be out of reach, but I'm having a hard time even coming up with "new" obstructions which do not come from the consideration of just pairs of vertices.

What are some good examples where $(A_1, A_2)$ is not independent, although for any $B_1 \subseteq A_1, B_2 \subseteq A_2$ with $|B_1| = |B_2|$, the pair $(B_1, B_2)$ is independent?

(II) I am also interested in the following notion derived from the above. Call a set $A \subseteq V(G)$ agile if for every bipartition $A = A_1 \cup A_2$ of $A$, the pair $(A_1, A_2)$ is independent. It is easy to see that $V(G)$ is agile if and only if $G$ is a complete graph. As a somewhat different example, take a complete bipartite graph $K_{2,t}$. Then the set of all degree-2 vertices is agile.

The containment of a large agile set may be regarded as a measure of the complexity of a graph. If $H$ is a minor of $G$ and $H$ has an agile set $A$, then $G$ contains an agile set $A'$ with $|A'| \geq |A|$. Based on this, it is not hard to show that $G$ contains an agile set of order 4 if and only if $G$ is not outerplanar.

Is there, for every integer $t$, an integer $m(t)$ such that every graph which contains an agile set of size at least $m(t)$ contains $K_{2,t}$ as a minor?

I'd be happy about any sort of insights you can contribute to these questions as well as to pointers to relevant literature. Thank you very much in advance!

Answer 1

Here is a small example

where $(A_1, A_2)$ is not independent, although for any $B_1 \subseteq A_1, B_2 \subseteq A_2$ with $|B_1| = |B_2|$, the pair $(B_1, B_2)$ is independent?

$A_1$ consists of the two vertices labelled $1$.

$A_2$ consists of the three vertices labelled $2$.

$(A_1, A_2)$ is not independent because all the vertices labelled $3$ are required to connect $A_2$ and none would be left to connect $A_1$.

$(A_1, B_2)$ is independent for any $B_2 \subset A_2$ with $|B_2|=2$ because only two vertices labelled $3$ are required to connect any $B_2$, leaving the other free to connect $A_1$.

The graph is planar -- move one $1$ to the outer face.

I have no idea whether some simple kind of obstruction can be derived from such an example.

Answer 2

This problem was considered by Robertson and Seymour as part of their Graph Minors Project. In fact, they present a polynomial-time algorithm for the following generalization of your problem.

Let $k \in \mathbb{N}$ be fixed, $G$ be a graph, and $A_1, \dots, A_t$ be pairwise disjoint subsets of vertices such that $\sum_{i \in [t]} |A_i| \leq k$. Then there is a polynomial-time algorithm that decides if $G$ contains $t$ vertex-disjoint trees $T_1, \dots, T_k$, such that $A_i \subseteq V(T_i)$ for all $i \in [t]$.

Note that the condition that $k$ is fixed is necessary; otherwise the problem becomes NP-complete if $k$ is part of the input. The algorithm is presented in Graph Minors XIII, where the problem is referred to as Disjoint Connected Subgraphs.

Answer 3

Regarding your question (II): Consider the graph obtained from two long paths $v_1\dots v_n$, $w_1\dots w_n$ by adding, for any $i$, an edge between $v_i$ and $w_{i-1}$ and between $v_i$ and $w_{i+1}$.

In this graph the set of all the $w_i$ forms an agile set, however this type of graph, independent from the size of $n$, does not contain $K_{2,5}$ as a minor.

Let us call this type of graph a regular strip of length n.

This led to a research paper by us: Using Ding's characterisation of graphs not containing a $K_{2,n}$-minor (http://arxiv.org/abs/1702.01355) we are able to show that these regular strips are the `only' other obstruction, namely one can show that there exists a function $f : \mathbb{N}\to \mathbb{N}$ such that every graph with an agile set of size $f(n)$ either contains $K_{2,n}$ or a regular strip of length $n$ as a minor. For more details see http://arxiv.org/abs/2109.04768, Theorem 1.3.