The k-minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly k vertices and forms a subgraph of a larger graph. It is also called the k-MST or edge-weighted k-cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time. The input to the problem consists of an undirected graph with weights on its edges, and a number k. The output is a tree with k vertices and k − 1 edges, with all of the edges of the output tree belonging to the input graph. The cost of the output is the sum of the weights of its edges, and the goal is to find the tree that has minimum cost. The problem was formulated by and by . Ravi et al. also considered a geometric version of the problem, which can be seen as a special case of the graph problem. In the geometric k-minimum spanning tree problem, the input is a set of points in the plane. Again, the output should be a tree with k of the points as its vertices, minimizing the total Euclidean length of its edges. That is, it is a graph k-minimum spanning tree on a complete graph with Euclidean distances as weights. When k is a fixed constant, the k-minimum spanning tree problem can be solved in polynomial time by a brute-force search algorithm that tries all k-tuples of vertices. However, for variable k, the k-minimum spanning tree problem has been shown to be NP-hard by a reduction from the Steiner tree problem. The reduction takes as input an instance of the Steiner tree problem: a weighted graph, with a subset of its vertices selected as terminals. The goal of the Steiner tree problem is to connect these terminals by a tree whose weight is as small as possible. To transform this problem into an instance of the k-minimum spanning tree problem, attach to each terminal a tree of zero-weight edges with a large number t of vertices per tree. (For a graph with n vertices and r terminals, they use t = n − r − 1 added vertices per tree.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.