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\ge 2\) in an unweighted graph \(G = (V, E)\) is a subset \(S\subseteq V\) of vertices such that for any pair of vertices \(u, v \in 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| \ge 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 \(\varepsilon >0\) and any fixed integer \(d\ge 3\), it is \(\mathcal{NP}\)-hard to approximate MaxD \(d\) IS to within a factor of \(n^{1/2-\varepsilon }\) for bipartite graphs of \(n\) vertices, and for any fixed integer \(d\ge 3\), ParaD \(d\) IS(\(k\)) is \(\mathcal{W}[1]\)-hard for bipartite graphs. Then, (2) we prove that for every fixed integer \(d\ge 3\), D \(d\) IS remains \(\mathcal{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\ge 2\), whereas D \(d\) IS is \(\mathcal{NP}\)-complete for any odd \(d\ge 3\). Also, we show the hardness of approximation of MaxD \(d\) IS and the \(\mathcal{W}[1]\)-hardness of ParaD \(d\) IS(\(k\)) on chordal graphs for any odd \(d\ge 3\).