Abstract :
Path–distance–width of a graph G=(V,E), denoted by pdw(G), is the minimum integer k satisfying that there is a nonempty subset of S⊆V such that the number of the nodes with distance i from S is at most k for any nonnegative integer i. It is known that given a positive integer k and a graph G, the decision problem pdw(G)⩽k is NP-complete even if G is a tree (Yamazaki et al. Lecture Notes in Computer Science, vol. 1203, Springer, Berlin, 1997, pp. 276–287). In this paper, we show that it is NP-hard to approximate the path–distance–width of a graph within a ratio 43−ε for any ε>0, even for trees.
