The computational complexity of the κ-minimum spanning tree problem in graded matrices

✍ Scribed by T. Dudás; B. Klinz; G.J. Woeginger

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 524 KB
• Volume: 36
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(98)00150-3

✦ Synopsis

Given an undirected graph G = (V, E) where each edge e = (i,j) has a length dij >_ O, the k-minimum spanning tree problem, k-MST for short, is to find a tree T in G which spans at least k vertices and has minimum length l(T) = ~'~(~,j)e T dij. We investigate the computational complexity of the k-minimum spanning tree problem in complete graphs when the distance matrix D = (d~j) is graded, i.e., has increasing, respectively, decreasing rows, or increasing, respectively, decreasing columns, or both. We exactly characterize polynomially solvable and NP-complete variants, and thus, establish a sharp borderline between easy and difficult cases of the k-MST problem on graded matrices. As a somewhat surprising result, we prove that the problem is polynomially solvable on graded matrices with decreasing rows, but NP-complete on graded matrices with increasing rows.