9
$\begingroup$

##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

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

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

$\endgroup$
2
  • 1
    $\begingroup$ I'll add a question: the threshold problem. What is the threshold for the appearance of a spanning k-tree in the binomial random graph? $\endgroup$
    – Bach
    Nov 30, 2020 at 7:18
  • 1
    $\begingroup$ OK, it seems like there's an answer to the question I've added, at least for k=2: according to Riordan's theorem, if p>>n^{-1/2}, every (given) 2-tree appears with high probability, and if p=n^{-1/2} then by the union bound none of these will appear whp. Didn't check for k>2. $\endgroup$
    – Bach
    Dec 6, 2020 at 12:46

1 Answer 1

8
+100
$\begingroup$

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.

$\endgroup$
0

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.