Finding a minimum spanning tree with a small non-terminal set

機関リポジトリ (HANDLE) オープンアクセス

説明

In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset V_<NT> of vertices as an internal vertex. This problem, called Minimum Weight Non-Terminal Spanning Tree, includes s-t Hamiltonian Path as a special case, and hence it is NP-hard. In this paper, we first observe that Non-Terminal Spanning Tree, the unweighted counterpart of Minimum Weight Non-Terminal Spanning Tree, is already NP-hard on some special graph classes. Moreover, it is W[1]-hard when parameterized by clique-width. In contrast, we give a 3k-vertex kernel and O^∗(2^k)-time algorithm, where k is the size of non-terminal set V_<NT>. The latter algorithm can be extended to Minimum Weight Non-Terminal Spanning Tree with the restriction that each edge has a polynomially bounded integral weight. We also show that Minimum Weight Non-Terminal Spanning Tree is fixed-parameter tractable parameterized by the number of edges in the subgraph induced by the non-terminal set V_<NT>, extending the fixed-parameter tractability of Minimum Weight Non-Terminal Spanning Tree to the general case. Finally, we give several results for structural parameterization.

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1050585493124291968
  • HANDLE
    2324/7347458
  • 本文言語コード
    en
  • 資料種別
    journal article
  • データソース種別
    • IRDB

問題の指摘

ページトップへ