On the Node Searching Spanning Tree Problem

On the Node Searching Spanning Tree Problem

Spanning tree is an extensively studied topic in the field of graph theory. Graph searching, on the other hand, is a novel and modern concept that extends the notion of traditional graph traversal. This paper introduces a problem which is a combination of spanning tree and node searching, a basic variant of graph searching. Our problem is called node searching spanning tree problem. In this problem, we are interested in a spanning tree regarding its search number. Let G be a simple undirected graph and s(G) denote the search number of G, i.e., the minimum number of searchers needed to traverse the graph G. Indeed, the node searching spanning tree problem considers a spanning tree T of G such that s(T) is minimized. In this paper, we show that to decide whether there exists a spanning tree s(T) of G such that s(T) ≤ k is NPcomplete, for any fixed integer k ≥ 2. In addition, we propose an O(log n)-approximation algorithm for the node searching spanning tree problem on graphs with n vertices.