Scholarlink

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 \(P_5\) -free. This provides the intractability for these graphs and the tractability for several subclasses of \(P_5\) -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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Spanning Trees with a Small Vertex Cover: The Complexity on Specific Graph Classes

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Toranosuke Kokai,
  • Akira Suzuki,
  • Takahiro Suzuki,
  • Yuma Tamura,
  • Xiao Zhou

摘要

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 \(P_5\) -free. This provides the intractability for these graphs and the tractability for several subclasses of \(P_5\) -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.