Spanning $k$-trees

Question

##k-trees

A $k$-tree is a graph defined as follows: (They were defined by Harary and Palmer.)

a) A complete graph with $k$ vertices is a $k$-tree.

b) A $k$-tree on $n$ vertices $T$ is obtained by a $k$-tree on $n-1$ vertices $S$ by adding a new vertex and connecting it to all the $k$ vertices of a complete subgraph of $S$ with $k$ vertices.

We can also regard a $k$-tree instead of a graph, as a $k$-dimensional simplicial complex, or as a $k+1$-uniform hypergraph. (We can also regard it as a $r$-uniform hypergraph for $2 \le r \le k+1$.)

#The questions

The decision problem

1a) Is there an efficient algorithm to tell if a graph contains a spanning $k$-tree.

1b) Is there an efficient algorithm to tell if a $k$-dimensional simplicial complex contains a $k$-tree. (Regarded, this time, as a $k$-dimensional simplicial complex.)

Of course, for $k=1$ a graph contains a tree iff it is connected.

The counting problem

2a) Given a graph $G$ is there a matrix-tree type theorem for the number of spanning $k$-trees of $G$?

2b) More generally, given a $k$-dimensional simplicial complex $K$ is there a matrix-type formula for the number of spanning $k$-trees. (Regarded as $k$-dimensional simplicial complexes.)

The sampling problem

3. Is there a simple way to sample a uniformly-random spanning $k$-tree of a given graph $G$?

For $k=1$ there are various miraculous important ways to sample uniform spanning trees.

Minimal spanning $k$-trees

For $k=1$ the famous greedy algorithm efficiently find the minimum-weight spanning tree.

4. Given weights on edges is there an algorithm for finding minimum spanning $k$-tree?

Bach's threshold problem.

(Added in a comment, Nov. 2020)

What is the threshold for the appearance of a spanning k-tree in the binomial random graph?

The general theme

In general, to what extent results about trees extend or fail to extend to $k$-trees.

##Some more background

Cayley's formula for the number of trees with $n$ labelled vertices was extended to $k$-trees by Beineke and Pippert. A Prufer type correspondence by C. Renyi and A. Renyi allows efficient sampling (uniformly) all $k$-trees with $n$ labelled vertices.

Answer 1

Regarding the question 1a, Bern showed that checking existence of a spanning $k$-tree in a graph is NP-complete for any fixed $k \geq 2$ (also see another, more accessible relevant paper by Cai and Maffray). This implies that questions 3 and 4 are at least as hard (indeed, each of these problems contains checking existence as a special case), and question 2a is unlikely to have a formula computable within reasonable time (unlike the polynomial-computable Laplacian cofactor for the number of trees).

The answers to questions regarding simplicial complexes may depend on the way we represent $k$-trees as complexes. Probably the most natural way to do that is to define a $k$-tree complex as a set of $k$-simplices obtained sequentially (from an initial set of a single $k$-simplex) by choosing a simplex $K$ and adding new simplex $K'$ to the set, so that $K'$ is different from $K$ in a single vertex not present in any previous simplex. However, we can notice that this problem is not easier than the problem of a spanning $k$-tree existence in a graph. Indeed, for any $k$ we can reduce from the graph problem to the simplicial problem simply by listing all $(k + 1)$-cliques (notice that since $k$ is fixed, the reduction is proper polynomial); the answer for that instance of the simplicial problem could be converted to a spanning $k$-tree of the original graph, and vice versa. This implies that the problem 1b is NP-complete whenever $k \geq 2$, and the problem 2b is not easier.

As for the general question about extending results from trees to $k$-trees, the intuition is probably that spanning $k$-trees of $K_n$ can be tamed (in light of results mentioned in OP), while spanning $k$-trees of a general graph may possess a much more complex structure not exhibited by spanning trees.