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 $\mid S\mid \ge k$ . D2IS is identical to the original IS. Thus D2IS is $\mathrm{𝒩𝒫}$ ‐complete even for planar graphs, but it is in $𝒫$ 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\ge 3$ , it is $\mathrm{𝒩𝒫}$ ‐hard to approximate MaxD $d$ IS to within a factor of $n^{1/2‐\epsilon }$ for bipartite graphs of $n$ vertices, and for any fixed integer $d\ge 3$ , ParaD $d$ IS( $k$ ) is $𝒲[1]$ ‐hard for bipartite graphs. Then, (2) we prove that for every fixed integer $d\ge 3$ , D $d$ IS remains $\mathrm{𝒩𝒫}$ ‐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 $\mathrm{𝒩𝒫}$ ‐complete for any odd $d\ge 3$ . Also, we show the hardness of approximation of MaxD $d$ IS and the $𝒲[1]$ ‐hardness of ParaD $d$ IS( $k$ ) on chordal graphs for any odd $d\ge 3$ .