11
$\begingroup$

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!

$\endgroup$

3 Answers 3

2
$\begingroup$

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 tetraed-like graph

$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.

$\endgroup$
3
  • 1
    $\begingroup$ Thank you very much for your example! It seems that you might as well remove the leaves and relabel $3 \to 2$ for the other three. (General reduction rule: if there is a cutvertex $v$ for which distinct components of $G - v$ meet $A_i$, then we may as well add $v$ to $A_i$ without changing dependency. If $v$ already lies in $A_j$, $j \neq i$, then the pair is necessarily dependent.) The resulting triple $(G', A_1', A_2')$ is a 'trivially dependent' example, since one of the two sets separates the other (the vertices of $A_1$ lie in distinct components of $G - A_2$). $\endgroup$ Aug 16, 2018 at 13:51
  • $\begingroup$ Thank you for you kind words while I have been close to trivial! What about adding edges from all $1$'s to all $2$'s in my initial example? Then the $3$'s are not cutvertices anymore. Or is it an elementary reduction rule as well to remove any edge between $A_1$ and $A_2$? I'll look for yet another modification so as to exhaust all simple reduction rules. $\endgroup$ Aug 16, 2018 at 15:26
  • 1
    $\begingroup$ Well, yes, edges between $A_1$ and $A_2$ are of no use when trying to find those trees, so this seems like a straightforward reduction rule. But finding a 'right' set of reduction rules which really gets you anywhere is part of the (wide open, at least to me) problem. $\endgroup$ Aug 16, 2018 at 19:59
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.