Distance-d independent set problems for bipartite and chordal graphs

The paper studies a generalization of the Independent Set problem (IS for short). A distance- d independent set for an integer d≥2 in an unweighted graph G = (V, E) is a subset S⊂ V of vertices such that for any pair of vertices u, v εS, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the Distance- d Independent Set problem (D d IS for short) is to decide whether G contains a distance- d independent set S such that |S| ≥k. D2IS is identical to the original IS. Thus D2IS is \mathcal{NP} -complete even for planar graphs, but it is in \mathcal{P} for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D d IS, its maximization version MaxD d IS, and its parameterized version ParaD d IS(k), where the parameter is the size of the distance- d independent set: (1) We first prove that for any ε >0 and any fixed integer d≥3, it is \mathcal{NP} -hard to approximate MaxD d IS to within a factor of n^1/2- for bipartite graphs of n vertices, and for any fixed integer d≥3, ParaD d IS(k) is \mathcal{W}[1] -hard for bipartite graphs. Then, (2) we prove that for every fixed integer d≥3, D d IS remains NP -complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d≥2, whereas D d IS is NP -complete for any odd d≥3. Also, we show the hardness of approximation of MaxD d IS and the W[1] -hardness of ParaD d IS(k) on chordal graphs for any odd d≥3.