<h3>Background</h3>
<p>Given two rooted, vertex-colored trees <span class="math-container">$T_1, T_2$</span>, <span class="math-container">$T_1$</span> is color-preserving inf-embeddle in <span class="math-container">$T_2$</span>, which we'll denote <span class="math-container">$T_1 \leq T_2$</span>, if there is an injective <span class="math-container">$f \colon V(T_1) \to V(T_2)$</span> such that for all <span class="math-container">$v,w,w' \in V(T_1)$</span>:</p>
<ul>
<li><span class="math-container">$v$</span> and <span class="math-container">$f(v)$</span> have the same color</li>
<li>If <span class="math-container">$w$</span> is a successor of <span class="math-container">$v$</span> (not necessarily immediate successor), then <span class="math-container">$f(w)$</span> is a successor of <span class="math-container">$f(v)$</span></li>
<li>If <span class="math-container">$w,w'$</span> are both immediate successors of <span class="math-container">$v$</span>, then the unique path in <span class="math-container">$T_2$</span> from <span class="math-container">$f(w)$</span> to <span class="math-container">$f(w')$</span> contains <span class="math-container">$f(v)$</span></li>
</ul>
<p>Friedman defined the very-fast-growing function <a href="https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE(3)" rel="nofollow noreferrer">TREE(k)</a> to be the length of the longest sequence of rooted vertex-colored trees with at most <span class="math-container">$k$</span> colors <span class="math-container">$T_1, T_2, T_3, \dotsc$</span> such that <span class="math-container">$|V(T_i)| \leq i$</span> for all <span class="math-container">$i$</span>, 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 <a href="https://www.youtube.com/watch?v=3P6DWAwwViU" rel="nofollow noreferrer">this Numberphile video</a>, which is where I learned about this).</p>
<h3>The Question</h3>
<p>What is the complexity of the following decision problem?</p>
<blockquote>
<p>Tree Sequence [is there a better name for this?]</p>
<p>Input: An integer <span class="math-container">$k$</span>, and a sequence of <span class="math-container">$k$</span>-vertex-colored rooted trees <span class="math-container">$T_1, \dotsc, T_n$</span> with <span class="math-container">$|V(T_i)| \leq i$</span> for all <span class="math-container">$i$</span></p>
<p>Decide: Is there another <span class="math-container">$k$</span>-vertex-colored rooted tree <span class="math-container">$T_{n+1}$</span> on at most <span class="math-container">$n+1$</span> vertices such that <span class="math-container">$T_i \not\leq T_j$</span> for all <span class="math-container">$i,j \in \{1,\dotsc,n+1\}$</span>?</p>
</blockquote>
<p>Some observations:</p>
<ul>
<li>For fixed <span class="math-container">$k$</span>, Kruskal's Tree Theorem implies there are only finitely many instances with a yes answer (albeit a <em>very</em> large number!), so technically it would be solvable by a huge lookup table in <span class="math-container">$O(1)$</span> time. (Might be interesting to consider what happens if one restricts the size of the program to be small as a function of <span class="math-container">$k$</span>, but that seems like a separate question) But when <span class="math-container">$k$</span> is part of the input, there are infinitely many yes and infinitely many no instances.</li>
<li>Let INFEMB denote the problem: given two vertex-colored trees <span class="math-container">$T_1, T_2$</span>, decide whether <span class="math-container">$T_1 \leq T_2$</span>. <strong>Updated 2023-09-01:</strong> 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. <s>INFEMB is in <span class="math-container">$\mathsf{NP}$</span> (the witness is the embedding function <span class="math-container">$f$</span>). This is kind of like deciding whether one graph is a minor of another, which is <span class="math-container">$\mathsf{NP}$</span>-complete, but I had trouble figuring out (and searching for) whether INFEMB is <span class="math-container">$\mathsf{NP}$</span>-complete. Regardless, Tree Sequence is in <span class="math-container">$\mathsf{NP}_{||}^{INFEMB} \subseteq \mathsf{\Sigma_2 P}$</span>. Is it even in <span class="math-container">$\mathsf{NP}$</span>? Is it in <span class="math-container">$\mathsf{P}$</span>, <span class="math-container">$\mathsf{NP}$</span>-hard, <span class="math-container">$\mathsf{\Sigma_2 P}$</span>-complete?</li>
<li>Even verifying among the given trees <span class="math-container">$T_1, \dotsc, T_n$</span> that we don't have <span class="math-container">$T_i \leq T_j$</span> requires INFEMB. If INFEMB is <span class="math-container">$\mathsf{NP}$</span>-complete, does the complexity of the problem change under the promise that <span class="math-container">$T_i \not\leq T_j$</span> for <span class="math-container">$i=1,\dotsc,n$</span>?</s></li>
</ul>

CC BY-SA 4.0
2022-11-14T10:41:03.793Z
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)$.
Wei Zhan
CC BY-SA 4.0
2023-01-10T18:54:34.293Z
I suppose one could also ask about fixed parameter tractability with parameter k.
Joshua Grochow
<cc.complexity-theory><tree><graph-minor>
Complexity of a problem related to Friedman's TREE(k) function?
Joshua Grochow
# Complexity of a problem related to Friedman's TREE(k) function?

(Asked by: username_0 on 2022-11-11)

### 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)](https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE(3)) 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](https://www.youtube.com/watch?v=3P6DWAwwViU), 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 username_1 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$?

**Tags:** cc.complexity-theory, tree, graph-minor

> **Comments:**
> **username_1**: 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)$.  
> **username_0**: I suppose one could also ask about fixed parameter tractability with parameter k.  

---

## 0 answers

