2025/11/28 by Toranosuke Kokai, Kokai, Toranosuke, Akira Suzuki +7
Computer Science · #05C85 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2511.22912
openalex publication_date 2025/11/28 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28
In the context of algorithm theory, various studies have been conducted on spanning trees with desirable properties. In this paper, we consider the Minimum Cover Spanning Tree problem (MCST for short). Given a graph G and a positive integer k, the problem determines whether G has a spanning tree with a vertex cover of size at most k. We reveal the equivalence between \mcst and the Dominating Set problem when G is of diameter at most~2 or P5-free. This provides the intractability for these graphs and the tractability for several subclasses of P5-free graphs. We also show that \mcst is NP-complete for bipartite planar graphs of maximum degree~4 and unit disk graphs. These hardness results resolve open questions posed in prior research. Finally, we present an FPT algorithm for \mcst parameterized by clique-width and a linear-time algorithm for interval graphs.