# Complexity of a problem related to Friedman's TREE(k) function?

### Background

Given two rooted, vertex-colored trees $$T_1, T_2$$, $$T_1$$ is color-preserving inf-embeddle in $$T_2$$, which we'll denote $$T_1 \leq T_2$$, if there is an injective $$f \colon V(T_1) \to V(T_2)$$ such that for all $$v,w,w' \in V(T_1)$$:

• $$v$$ and $$f(v)$$ have the same color
• If $$w$$ is a successor of $$v$$ (not necessarily immediate successor), then $$f(w)$$ is a successor of $$f(v)$$
• If $$w,w'$$ are both immediate successors of $$v$$, then the unique path in $$T_2$$ from $$f(w)$$ to $$f(w')$$ contains $$f(v)$$

Friedman defined the very-fast-growing function TREE(k) to be the length of the longest sequence of rooted vertex-colored trees with at most $$k$$ colors $$T_1, T_2, T_3, \dotsc$$ such that $$|V(T_i)| \leq i$$ for all $$i$$, and such that none is color-preserving inf-embeddable in the other. That TREE(k) is finite for each k is a consequence of Kruskal's Tree Theorem. Already TREE(1)=1, TREE(2)=3, and TREE(3) is enormous (the subject of this Numberphile video, which is where I learned about this).

### The Question

What is the complexity of the following decision problem?

Tree Sequence [is there a better name for this?]

Input: An integer $$k$$, and a sequence of $$k$$-vertex-colored rooted trees $$T_1, \dotsc, T_n$$ with $$|V(T_i)| \leq i$$ for all $$i$$

Decide: Is there another $$k$$-vertex-colored rooted tree $$T_{n+1}$$ on at most $$n+1$$ vertices such that $$T_i \not\leq T_j$$ for all $$i,j \in \{1,\dotsc,n+1\}$$?

Some observations:

• For fixed $$k$$, Kruskal's Tree Theorem implies there are only finitely many instances with a yes answer (albeit a very large number!), so technically it would be solvable by a huge lookup table in $$O(1)$$ time. (Might be interesting to consider what happens if one restricts the size of the program to be small as a function of $$k$$, but that seems like a separate question) But when $$k$$ is part of the input, there are infinitely many yes and infinitely many no instances.
• Let INFEMB denote the problem: given two vertex-colored trees $$T_1, T_2$$, decide whether $$T_1 \leq T_2$$. Updated 2023-09-01: INFEMB is in P by a dynamic programming algorithm, as pointed out by Wei Zhan in the comments. So the question becomes whether Tree Sequence is in P or NP-complete. INFEMB is in $$\mathsf{NP}$$ (the witness is the embedding function $$f$$). This is kind of like deciding whether one graph is a minor of another, which is $$\mathsf{NP}$$-complete, but I had trouble figuring out (and searching for) whether INFEMB is $$\mathsf{NP}$$-complete. Regardless, Tree Sequence is in $$\mathsf{NP}_{||}^{INFEMB} \subseteq \mathsf{\Sigma_2 P}$$. Is it even in $$\mathsf{NP}$$? Is it in $$\mathsf{P}$$, $$\mathsf{NP}$$-hard, $$\mathsf{\Sigma_2 P}$$-complete?
• Even verifying among the given trees $$T_1, \dotsc, T_n$$ that we don't have $$T_i \leq T_j$$ requires INFEMB. If INFEMB is $$\mathsf{NP}$$-complete, does the complexity of the problem change under the promise that $$T_i \not\leq T_j$$ for $$i=1,\dotsc,n$$?
• It seems to me that INFEMB is in P, which puts Tree Sequence in NP. Denote by $T(v)$ the subtree of $T$ rooted at $v$, we can compute if $T_1(v)\leq T_2(w)$ for $v$ bottom-up: it is true if and only if there is $w'\in T_2(w)$ with the same color as $v$, and a $k$-matching between the intermediate successors $v_1,\ldots,v_k$ of $v$ and those $w_1,\ldots,w_m$ of $w'$, where an edge $(v_i,w_j)$ means $T_1(v_i)\leq T_2(w_j)$. Nov 14, 2022 at 10:41
• I suppose one could also ask about fixed parameter tractability with parameter k. Jan 10, 2023 at 18:54