5
$\begingroup$

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$?
Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Wei Zhan
    Nov 14, 2022 at 10:41
  • 1
    $\begingroup$ I suppose one could also ask about fixed parameter tractability with parameter k. $\endgroup$
    – Joshua Grochow
    Jan 10 at 18:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy