1
$\begingroup$

A $k$-tree is a graph obtained by starting with a $k+1$-clique and repeatedly attaching a $k+1$-clique to the graph along a $k$-clique. A tree is then a $1$-tree in this definition.

Is there anything known about the problem of, given a complete graph on $n$ vertices with edge weights, finding a $k$-tree with $n$ vertices which minimizes the sum of the edge weights of this $k$-tree? For example, is this NP-hard if $k$ is fixed?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It may help readers that the wikipedia link states "The k-trees are exactly the maximal graphs with a treewidth of k ("maximal" means that no more edges can be added without increasing their treewidth). They are also exactly the chordal graphs all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k." $\endgroup$
    – Neal Young
    Commented Oct 28 at 13:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.