Distance-$d$ independent set problems for bipartite and chordal graphs

Abstract

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$.

1 Introduction

One of the most important and most investigated computational problems in theoretical computer science and combinatorial optimization is the Independent Set problem (IS for short) because of its many applications in scheduling, computer vision, pattern recognition, coding theory, map labeling, computational biology, and some other fields. The input of IS is an unweighted graph $G = (V, E)$ and a positive integer $k \le |V|$. An independent set of $G$ is a subset $S\subseteq V$ of vertices such that, for all $u, v\in S$, the edge $\{u, v\}$ is not in $E$. IS asks whether $G$ contains an independent set $S$ having $|S| \ge k$. IS is among the first problems ever to be shown to be $\mathcal{NP}$-complete, and has been used as a starting point for proving the $\mathcal{NP}$-completeness of other problems (Garey and Johnson 1979). Moreover, it is well known that IS remains $\mathcal{NP}$-complete even for substantially restricted graph classes such as cubic planar graphs (Garey et al. 1976), triangle-free graphs (Poljak 1974), and graphs with large girth (Murphy 1992).

In this paper, we consider a generalization of IS, named the Distance- $d$ Independent Set problem (D $d$ 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$. For a fixed constant $d\ge 2$, D $d$ IS considered in this paper is formulated as the following class of problems (Agnarsson et al. 2004):

The maximization version of D $d$ IS can be also defined:

The problem parameterized by the solution size $k$ is as follows:

It is important to note that D2IS is identical to the original IS, and D $d$ IS is equivalent to IS on the $(d-1)$th power graph $G^{d-1}$ of the input graph $G$ as pointed out in (Agnarsson et al. 2004).

Even when $d = 2$, D $d$ IS (i.e., D2IS) is $\mathcal{NP}$-complete, and thus it would be easy to show that D $d$ IS is $\mathcal{NP}$-complete in general. Fortunately, however, it is known that if the input graph is restricted to, for example, bipartite graphs (Harary 1969), chordal graphs (Gavril 1972), circular-arc graphs (Gavril 1974), comparability graphs (Golumbic 1977), and many other classes (Minty 1980; Lozin and Milanič 2008; Brandstädt and Giakoumakis 2012), then D2IS admits polynomial-time algorithms. Furthermore, Agnarsson et al.  (2004) show the following tractability of D $d$ IS by using the closure property under taking power (Flotow 1995, 1996; Raychaudhuri 1987):

Fact 1

[Agnarsson et al. 2004] Let $n$ denote the number of vertices in the input graph $G$. Then, for every integer $d\ge 2$, D $d$ IS is solvable in $O(n)$ time for interval graphs, in $O(n(\log \log n + \log d))$ time for trapezoid graphs, and in $O(n)$ time for circular-arc graphs.

This tractability suggests that if we restrict the set of instances to, for example, subclasses of bipartite graphs and chordal graphs, then D $d$ IS for a fixed $d\ge 3$ might be also solvable efficiently. On the other hand, however, we have a “negative” fact that if $G$ is planar/bipartite, then the $(d-1)$th power graph $G^{d-1}$ is not necessarily planar/bipartite. From those points of view, this paper investigates D $d$ IS, namely, our work focuses on the computational complexity of D $d$ IS and/or the inapproximability of MaxD $d$ IS on (subclasses of) bipartite graphs and chordal graphs.

Our main results are summarized in the following list:

• (i) For every fixed integer $d\ge 3$, D $d$ IS is $\mathcal{NP}$-complete even for bipartite graphs.

• (ii) For any $\varepsilon > 0$ and 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.

• (iii) For every fixed integer $d\ge 3$, ParaD $d$ IS( k ) is $\mathcal{W}[1]$-hard for bipartite graphs.

• (iv) For every fixed integer $d\ge 3$, D $d$ IS remains $\mathcal{NP}$-complete even for planar bipartite graphs of maximum degree three.

• (v) For every fixed even integer $d\ge 2$, D $d$ IS is in $\mathcal{P}$ for chordal graphs.

• (vi) For every fixed odd integer $d\ge 3$, D $d$ IS is $\mathcal{NP}$-complete for chordal graphs.

• (vii) For any $\varepsilon > 0$ and fixed odd integer $d\ge 3$, it is $\mathcal{NP}$-hard to approximate MaxD $d$ IS to within a factor of $n^{1/2-\varepsilon }$ for chordal graphs of $n$ vertices.

• (viii) For every fixed odd integer $d\ge 3$, ParaD $d$ IS( k ) is $\mathcal{W}[1]$-hard for chordal graphs.

One can see that the complexity of D $d$ IS depends on the parity of $d$ if the set of input graphs is restricted to chordal graphs.

The organization of the paper is as follows: Section. 2 is devoted to our notation and terminology. In Sect. 3 we prove the $\mathcal{NP}$-hardness, the hardness of approximation, and the $\mathcal{W}[1]$-hardness of the problem for bipartite graphs. In Sect. 4, we provide tractable and intractable cases for chordal graphs.

2 Preliminaries

Let $G=(V,E)$ be an unweighted graph, where $V$ and $E$ denote the set of vertices and the set of edges, respectively. $V(G)$ and $E(G)$ also denote the vertex set and the edge set of $G$, respectively. We denote an edge with endpoints $u$ and $v$ by $\{u,v\}$. For a pair of vertices $u$ and $v$, the length of a shortest path from $u$ to $v$, i.e., the distance between $u$ and $v$ is denoted by $dist_{G}(u,v)$, and the diameter $G$ is defined as $diam(G) = \max _{u, v\in V}dist_{G}(u,v)$.

A graph $G_{S}$ is a subgraph of a graph $G$ if $V(G_{S}) \subseteq V(G)$ and $E(G_{S})\subseteq E(G)$. For a subset of vertices $U\subseteq V$, let $G[U]$ be the subgraph induced by $U$. For a subgraph $G_{S} = (V_{S}, E_{S})$ of $G$, if $E_{S} = V_{S}\times V_{S}$, then $G_{S}$ (or $G[V_{S}]$) and $V_{S}$ are called a clique and a clique set, respectively.

For a positive integer $d\ge 1$ and a graph $G$, the $d$th power of $G$, denoted by $G^{d} = (V(G), E^{d})$, is the graph formed from $V(G)$, where all pairs of vertices $u, v\in G$ such that $dist_{G}(u, v)\le d$ are connected by an edge $\{u, v\}$. Note that $E(G) \subseteq E^{d}$, i.e., the original edges in $E(G)$ are retained.

A path of length $\ell$, denoted by $P_{\ell }$, from a vertex $v_0$ to a vertex $v_{\ell }$ is represented as a sequence of vertices such that $P_{\ell } = \langle v_0, v_1, \ldots , v_{\ell }\rangle$. A cycle of length $\ell$, denoted by $C_{\ell }$, is similarly written as $C_{\ell } = \langle v_{0}, v_{1}, \ldots , v_{\ell -1}, v_{0}\rangle$. A chord of a path (cycle) is an edge between two vertices of the path (cycle) that is not an edge of the path (cycle).

A graph $G = (V, E)$ is bipartite if there is a partition of $V$ into two disjoint independent sets $V_{1}$ and $V_{2}$ such that $V_{1}\cup V_{2} = V$. A planar bipartite graph is a bipartite graph that can be drawn in the plane without edge crossings. A graph $G$ is chordal if each cycle in $G$ of length at least four has at least one chord. A graph $G = (V, E)$ is split if there is a partition of $V$ into a clique set $V_{1}$ and an independent set $V_{2}$ such that $V_{1}\cap V_{2} = \emptyset$ and $V_{1}\cup V_{2} = V$. Note that the split graphs are a subclass of the chordal graphs. A graph is star if it is a rooted tree of height one. See, e.g., (Brandstädt et al. 1999), for the definitions of interval, trapezoid, circular-arc, and comparability graphs, and inclusion relations among the graph classes.

For the maximization problems, an algorithm ALG is called a $\sigma$-approximation algorithm and the approximation ratio of ALG is $\sigma$ if $OPT(G) / ALG(G) \le \sigma$ holds for every input $G$, where $ALG(G)$ and $OPT(G)$ are the number of vertices of obtained subsets by ALG and the number of vertices of an optimal solution, respectively.

A parameterized problem is a pair $(Q, k)$ where $Q\subseteq \Sigma ^*$ is a decision problem over some alphabet $\Sigma$, and $k: \Sigma ^*\rightarrow \mathbf N$ is a parameterization of the problem, assigning a parameter to each instance of $Q$. An algorithm is fixed-parameter tractable or fpt if it has a running time at most $f(k)\cdot n^c$ for some computable function $f$ and a constant $c$, where $n$ is the input length and $k$ is the parameter assigned to the input. Given two parameterized problems $(Q_1, k_1)$ and $(Q_2, k_2)$ over the alphabet $\Sigma$, an fpt-reduction from $(Q_1, k_1)$ to $(Q_2, k_2)$ is a function $g: \Sigma ^*\rightarrow \Sigma ^*$, computable by an fpt-algorithm, such that $I\in Q_1$ if and only if $g(I)\in Q_2$ and $k_2(g(I)) \le f(k_1(I))$ for some computable function $f$, for every $I\in \Sigma ^*$.

3 Bipartite graphs

In this section we consider the class of bipartite graphs and its subclasses. As mentioned in Sect. 1, D2IS is solvable in polynomial time by using a polynomial time algorithm which finds the maximum matching in a given bipartite graph (Harary 1969). Unfortunately, however, we can show the $\mathcal{NP}$-hardness of D $d$ IS, the hardness of approximation of MaxD $d$ IS, and the $\mathcal{W}[1]$-hardness of ParaD $d$ IS( k ) on bipartite graphs when $d\ge 3$.

Theorem 1

For every fixed integer $d\ge 3$, D $d$ IS is $\mathcal{NP}$-complete even for bipartite graphs.

Proof

We first show the $\mathcal{NP}$-completeness of D3IS and then one of the general D $d$ IS for $d\ge 4$ in order to make the basic ideas of this proof clear. It is obvious that D $d$ IS is in $\mathcal{NP}$ for every $d\ge 3$. To show that D3IS is $\mathcal{NP}$-hard, we reduce the $\mathcal{NP}$-hard problem D2IS on any general graphs to D3IS on bipartite graphs. That is, given a graph $G_{2} = (V_{2}, E_{2})$ of D2IS with $n$ vertices, $V_{2} = \{v_{1}, v_{2}, \ldots , v_{n}\}$, and $m$ edges, $E_{2} = \{e_{1}, e_{2}, \ldots , e_{m}\}$, we construct a new bipartite graph $G_3$ in the following way. The constructed graph $G_3$ consists of (i) $n$ vertices, $u_1$ through $u_{n}$, each $u_{i}$ of which is corresponding to $v_{i} \in V_{2}$, (ii) $m$ vertices, $w_1$ through $w_{m}$, each $w_{i}$ of which is corresponding to $e_{i} \in E_{2}$, and (iii) two special vertices $\alpha$ and $\beta$. (iv) The vertex $\alpha$ is connected to each vertex in $\{\beta \}\cup \{w_1, \ldots , w_{m}\}$, i.e., the induced graph $G[\{\alpha , \beta \}\cup \{w_1, \ldots , w_{m}\}]$ is star. (v) If $e_{i} = \{v_{j}, v_{k}\}\in E_{2}$, then we add two edges $\{w_{i}, u_{j}\}$ and $\{w_{i}, u_{k}\}$. Since there is a partition of $V_{3}$ into two disjoint independent sets $\{\beta , w_{1}, \ldots , w_{m}\}$ and $\{\alpha , u_{1}, \ldots , u_{n}\}$, the reduced graph $G_{3}$ must be bipartite. See Fig. 1. For example, if the instance $G_2$ is the left graph, then the reduced graph $G_3$ is illustrated in the right graph. It is clear that this reduction can be done in polynomial time.

Fig. 1

(Left) graph $G_{2}$ of D2IS and (Right) reduced graph $G_3$ of D3IS from $G_2$.

For the above construction of $G_{3}$, we show that $G_{3}$ has a distance-$3$ independent set $S_{3}$ such that $|S_{3}| \ge k + 1$ if and only if $G_{2}$ has a distance-$2$ independent set $S_{2}$ such that $|S_{2}| \ge k$.

(If part) Suppose that the graph $G_{2}$ of D2IS has the distance-$2$ independent set $S_{2} = \{ v_{1^*}, v_{2^*}, \ldots v_{k^*}\}$ in $G_{2}$, where $\{1^*, 2^*, \ldots , k^*\}\subseteq \{1, 2, \ldots , n\}$. Then, we select a subset of vertices $S_{3} = \{u_{1^*}, u_{2^*}, \ldots , u_{k^*}\} \cup \{\beta \}$ of size $k + 1$. Note that the distance $dist_{G_{3}}(\beta , u_i)$ for every $i$ is at least three. Since the distance $dist_{G_2}(v_{i^*}, v_{j^*})$ for any pair of vertices $v_{i^*}, v_{j^*}\in S_{2}$ ($i^*\ne j^*$) is at least two, the shortest path from $u_{i^*}$ to $u_{j^*}$ contains at least two vertices in $\{w_1, w_2, \ldots , w_m\}$. This means that the distance $dist_{G_{3}}(u_{i^*}, u_{j^*})$ for any $i^*\ne j^*$ is at least four. Thus, the selected vertex set $S_{3}$ of size $k+1$ is a distance-$3$ independent set in $G_{3}$.

(Only-if part) Conversely, suppose that the constructed graph $G_{3}$ has the distance-$3$ independent set $S_{3}$ such that $|S_{3}| \ge k + 1$. First, take a look at the induced subgraph $G[\{\alpha , \beta \}\cup \{w_1, \ldots , w_{m}\}]$. Since its diameter $diam_{G_{3}}(G[\{\alpha , \beta \}\cup \{w_1, \ldots , w_{m}\}])$ is two, $|S_{3} \cap V(G[\{\alpha , \beta \}\cup \{w_1, \ldots , w_{m}\}])| \le 1$ holds, i.e., $|S_{3} \cap \{u_1, u_2, \ldots , u_n\}| \ge k$ must be satisfied. Let $\{u_{1^*}, u_{2^{*}}, \ldots , u_{k^*}\}$ be a subset of $k$ vertices in $S_{3}\cap \{u_1, u_2, \ldots , u_n\}$. Then, the pairwise distance of vertices in $\{v_{1^*}, v_{2^{*}}, \ldots , v_{k^*}\}$ of $G_{2}$ corresponding to $\{u_{1^*}, u_{2^{*}}, \ldots , u_{k^*}\}$ in $G_{3}$ is surely at least $2$, i.e., $G_{2}$ has a distance-$2$ independent set $S_{2}$ such that $|S_{2}| \ge k$. This completes the proof of the $\mathcal{NP}$-hardness of D3IS.

To prove the $\mathcal{NP}$-hardness of D $d$ IS for $d\ge 4$, we add the following two small modifications to the constructed graph $G_{3}$ in the above reduction, and construct a new bipartite graph $G_{d}$. Let $L = (d-3) - \lceil \frac{d-1}{4} \rceil$ and let $\overline{L} = \lceil \frac{d-1}{4} \rceil$. Note that $L + \overline{L} = d-3$. (1) The top vertex $\beta$ in Fig. 1 is replace with a simple path of length $L$ say, $\langle \beta , \beta _1, \ldots , \beta _{L}\rangle$, and (2) every bottom vertex $u_j$ is replaced with a simple path of length $\overline{L}$, say, $\langle u_{j}, u_{j,1}, \ldots , u_{j, \overline{L}}\rangle$ for $1\le j\le n$. Then, we can again show that $G_{d}$ has a distance-$d$ independent set $S_{d}$ such that $|S_{d}| \ge k + 1$ if and only if $G_{2}$ has a distance-$2$ independent set $S_{2}$ such that $|S_{2}| \ge k$.

(If part for $d\ge 4$) If $G_{2}$ of D2IS has a distance-$2$ independent set $S_{2} = \{ v_{1^*}, v_{2^*}, \ldots v_{k^*}\}$ in $G_{2}$ as before, then $G_{d}$ has a subset of vertices $S_{d} = \{u_{1^*, \overline{L}}, u_{2^*, \overline{L}}, \ldots , u_{k^*, \overline{L}}\} \cup \{\beta _{L}\}$ of size $k + 1$, which must be a distance-$d$ independent set since $dist_{G_d}(\beta _{L}, u_{i^*, \overline{L}}) = L + \overline{L} + 3 = (d-3) + 3 = d$ and $dist_{G_d}(u_{i^*, \overline{L}}, u_{j^*, \overline{L}}) = 4(\overline{L} + 1) = 4\lceil \frac{d-1}{4} \rceil + 4 \ge d$ for any $i^{*}\ne j^{*}$.

(Only-if part for $d\ge 4$) Conversely, suppose that the constructed graph $G_{d}$ has the distance-$d$ independent set $S_{d}$ such that $|S_{d}| \ge k + 1$. Similarly to the case of $d = 3$, since $diam_{G_{d}}(G[\{\alpha , \beta , \beta _1, \ldots , \beta _L\}\cup \{w_1, \ldots , w_{m}\}])\le d$, which means that $|S_{d}\cap (\{\alpha , \beta , \beta _1, \ldots , \beta _L\}\cup \{w_1, \ldots , w_{m}\})| \le 1$ holds, $|S_{d}\cap \{u_1, u_{1,1}, \ldots , u_{1, \overline{L}}, u_2, u_{2, 1}, \ldots , u_{2, \overline{L}}, \ldots , u_{n}, \ldots , u_{n, \overline{L}}\}| \ge k$ must be satisfied. Now we can assume that (at least) those $k$ vertices in $S_{d}$ are in the set of bottom vertices $\{u_{1, \overline{L}}, u_{2, \overline{L}}, \ldots , u_{n, \overline{L}}\}$, because $|S_{d}\cup \{u_{j,\overline{L}}\}\setminus \{u_{j, L^{\prime }}\}| \ge |S_{d}|$ even if $u_{j, L^{\prime }}\in S_{d}$ for $L^{\prime } < L$. Let $\{u_{1^*, \overline{L}}, u_{2^{*}, \overline{L}}, \ldots , u_{k^*, \overline{L}}\}$ be a subset of $k$ vertices in $S_{d}\cap \{u_{1, \overline{L}}, \ldots , u_{n, \overline{L}}\}$. Then, the pairwise distance of vertices in $\{v_{1^*}, v_{2^{*}}, \ldots , v_{k^*}\}$ of $G_{2}$ corresponding to $\{u_{1^*, \overline{L}}, \ldots , u_{k^*, \overline{L}}\}$ in $G_{d}$ is surely at least two, i.e., $G_{2}$ has a distance-$d$ independent set $S_{2}$ such that $|S_{2}| \ge k$. This completes the proof of the theorem. $\square$

Next, we consider the maximization version MaxD $d$ IS of D $d$ IS, which asks for a distance-$d$ independent set of the maximum size in an input graph $G$. Since MaxD2IS is equivalent to Maximum Independent Set, it cannot be approximated within a factor of $n^{1-\varepsilon }$ (Zuckerman 2007). In the following, we will show that the above reduction can preserve the approximation-gap and thus gives us the following inapproximability of MaxD $d$ IS for $d\ge 3$.

Corollary 1

For any $\varepsilon > 0$ and a 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.

Proof

Let $OPT(G_{2})$ denote the number of vertices of an optimal solution for an $n$-vertex input graph $G_{2}$ of MaxD2IS. Let $OPT^{\prime }(G_{d})$ denote the number of vertices of an optimal solution for a $\nu$-vertex input bipartite graph $G_d$ of MaxD $d$ IS for a fixed $d\ge 3$. Let $g(n)$ be a parameter function of the instance $G_2$ of D2IS. Note that the reduction described in the proof of Theorem 1 is the following gap-preserving reduction: (1) If $OPT(G_{2}) \ge g(n)$, then $OPT^{\prime }(G_{d}) \ge g(n) + 1$, and (2) if $OPT(G_{2}) < \frac{g(n)}{n^{1-\varepsilon }}$ for a positive constant $\varepsilon$, then $OPT^{\prime }(G_{d}) < \frac{g(n)}{n^{1-\varepsilon }} + 1$.

The constructed graph $G_d$ has at most $n\times \frac{n}{4}$ vertices labeled “$u$”, $m \le \frac{n^2}{2}$ vertices labeled “$w$”, at most $n$ vertices labeled “$\beta$”, and one vertex $\alpha$, i.e., $|V(G_d)| = \nu = O(n^2)$. Hence the approximation-gap is $n^{1-\varepsilon } = \Theta (\nu ^{1/2 - \varepsilon })$ for any $\varepsilon > 0$. By renaming $\nu$ to $n$, we obtain the $n^{1/2-\varepsilon }$-inapproximability of MaxD $d$ IS on bipartite graphs of $n$ vertices. $\square$

Also, the reduction in the proof of Theorem 1 shows the following fixed-parameter intractability of ParaD d IS( k ):

Corollary 2

For every fixed integer $d\ge 3$, ParaD $d$ IS( k ) is $\mathcal{W}[1]$-hard for bipartite graphs.

Proof

It is known (Downey and Fellows 1995) that ParaD $2$ IS( k ) on general graphs is $\mathcal{W}[1]$-hard. Let $(G_2, k)$ and $(G_d, k^{\prime })$ be the instances of ParaD $2$ IS( k ) and ParaD $d$ IS( k ’) on bipartite graphs, respectively. Then, the reduction in the proof of Theorem 1 is the fpt-reduction such that (i) $k^{\prime }\le k+1$, and (ii) $(G_{2}, k)$ is a yes-instance of ParaD $2$ IS( k ) if and only if $(G_d, k^{\prime })$ is a yes-instance of ParaD $d$ IS( k ’) on bipartite graphs. $\square$

Even if the input graph is restricted to planar bipartite graphs of maximum degree three, D $d$ IS remains intractable for $d\ge 3$. Note that a planar bipartite graph is of course bipartite, and therefore D2IS on planar bipartite graphs is tractable.

Theorem 2

For every fixed integer $d\ge 3$, D $d$ IS is $\mathcal{NP}$-complete even for planar bipartite graphs of maximum degree three.

Proof

We first show the $\mathcal{NP}$-completeness of D3IS and then one of the general D $d$ IS for $d\ge 4$. Obviously, D $d$ IS is in $\mathcal{NP}$ for every $d\ge 3$. To show that D3IS is $\mathcal{NP}$-complete, we reduce the $\mathcal{NP}$-complete problem D2IS on any cubic planar graph $G_{2} = (V_{2}, E_{2})$ to D3IS on a new planar bipartite graph $G_{3} = (V_{3}, E_{3})$ of maximum degree three.

Let $V_{2} = \{v_{1}, v_{2}, \ldots , v_{n}\}$ and $E_{2} = \{e_{1}, e_{2}, \ldots , e_{m}\}$ be vertex and edge sets of the planar graph $G_{2}$. We construct the planar bipartite graph $G_{3}$ which consists of (i) $n$ vertices, $u_1$ through $u_{n}$, which are associated with $n$ vertices in $V_{2}$, $v_1$ through $v_{n}$, respectively, and (ii) $m$ subgraphs, $SG_{3,1}$ through $SG_{3,m}$, which are associated with $m$ edges in $E_{2}$, $e_1$ through $e_{m}$, respectively. For every $i$ ($1\le i\le m$), the $i$th subgraph $SG_{3,i}$ contains three vertices, $w_{i, 0}$, $w_{i, 1}$, and $w_{i, 2}$ and two edges, $\{w_{i, 0}, w_{i, 1}\}$ and $\{w_{i, 1}, w_{i, 2}\}$ such that $SG_{3,i}$ forms a path $P_{2}$ of length $2$. (iii) If $e_{i} = \{v_{j}, v_{k}\}\in E_{2}$, then we introduce two edges $\{w_{i, 0}, u_{j}\}$ and $\{w_{i, 0}, u_{k}\}$. Note that every simple path $SG_{3,i}$ of length two becomes a single vertex by applying the edge-contraction twice, and also every path $\langle u_{j}, w_{i,0}, u_{k}\rangle$ becomes back an edge $\{u_j, u_k\}$ by applying one edge-contraction for $1\le i\le m$ and $1\le j, k\le n$. Namely, the constructed graph $G_3$ is a minor of the planar graph $G_2$ and thus it must be planar. The maximum degree is clearly three. The construction can be accomplished in polynomial time. For example, if the cubic planar graph $G_{2}$ is the left graph in Fig. 1, then the reduced graph $G_{3}$ is illustrated in Fig. 2.

Fig. 2

An illustration of the construction when $d = 3$.

For the above construction of $G_{3}$, we will show that $G_{3}$ has a distance-$3$ independent set $S_{3}$ such that $|S_{3}| \ge k + m$ if and only if $G_{2}$ has a distance-$2$ independent set $S_{2}$ such that $|S_{2}| \ge k$.

(If part) Suppose that the graph $G_{2}$ of D2IS has a distance-$2$ independent set $S_{2} = \{ v_{1^*}, v_{2^*}, \ldots v_{k^*}\}$ in $G_{2}$, where $\{1^*, 2^*, \ldots , k^*\}\subseteq \{1, 2, \ldots , n\}$. Then, we select two subsets of vertices $S_{3}^{\prime } = \{u_{1^*}, u_{2^*}, \ldots , u_{k^*}\}$ and $S_{3}^{\prime \prime } = \{w_{1, 2}, w_{2, 2}, w_{3, 2}, \ldots , w_{m, 2}\}$ such that $|S_{3}^{\prime }| = k$ and $|S_{3}^{\prime \prime }| = m$. One can verify that $S_{3} = S_{3}^{\prime }\cup S_{3}^{\prime \prime }$ is a distance-$3$ independent set in $G_{3}$ since the pairwise distance in $S_{3}^{\prime }$ is at least four, the pairwise distance in $S_{3}^{\prime \prime }$ is at least six, and the distance between $w_{i, 2}$ in $S_{3}^{\prime \prime }$ and every vertex in $S_{3}^{\prime }$ is at least three for each $i$.

(Only-if part) Conversely, suppose that the graph $G_{3}$ has the distance-$3$ independent set $S_{3}$ such that $|S_{3}| \ge k + m$. First, from each subgraph $SG_{3,i}$ which is the path of length $2$, we can select at most one vertex as the distance-$3$ independent set since its diameter is two. Thus, the maximum size of the distance-$3$ independent set in $V(SG_{3,1})\cup V(SG_{3,2})\cup \ldots \cup V(SG_{3,m})$ is at most $m$, which means that $|S_{3}\cap \{u_1, u_2, \ldots , u_n\}| \ge k$ holds. Let $\{u_{1^*}, u_{2^{*}}, \ldots , u_{k^*}\}$ be a subset of $k$ vertices in $S_{3}\cap \{u_1, u_2, \ldots , u_n\}$. Then, the pairwise distance in the corresponding subset of vertices $\{v_{1^*}, v_{2^{*}}, \ldots , v_{k^*}\}$ of $G_{2}$ is surely at least two, i.e., $G_{2}$ has a distance-$2$ independent set $S_{2}$ such that $|S_{2}| \ge k$. This completes the proof of the $\mathcal{NP}$-hardness of D $3$ IS.

In the following, we give a brief sketch of the ideas to prove the $\mathcal{NP}$-hardness of D $d$ IS for $d\ge 4$. In the case of D $4$ IS, all we have to do is replace the $2$-length path $SG_{3,i}$ corresponding to the edge $e_{i}$ with a $3$-length path $SG_{4,i} = (\{w_{i, 0}, w_{i, 1}, w_{i, 2}, w_{i, 3}\}, \{ (w_{i, 0}, w_{i, 1}), (w_{i, 1}, w_{i, 2}), (w_{i, 2}, w_{i, 3}) \})$ for each $i$. See the left graph in Fig. 3. In the case of D $5$ IS, $SG_{3,i}$ is replaced with $SG_{5,i} = (V(SG_{5,i}), E(SG_{5,i}))$:

$$\begin{aligned} V(SG_{5,i})&= \{w^{0}_{i, 0}, w^{1}_{i, 0}, w^{2}_{i, 0}, w_{i, 1}, w_{i, 2}, w_{i, 3}\} \\ E(SG_{5,i})&= \{ \{w^{0}_{i, 0}, w^{1}_{i, 0}\}, \{w^{1}_{i, 0}, w^{2}_{i, 0}\}, \{w^{1}_{i, 0}, w_{i, 1}\}, \{w_{i, 1}, w_{i, 2}\}, \{w_{i, 2}, w_{i, 3}\} \}. \end{aligned}$$

Then, $u_{j}$ ($u_{k}$) corresponding to the vertex $v_j$ ($v_{k}$) is connected to $w^{0}_{i, 0}$ ($w^{2}_{i, 0}$) if $e_i = \{v_j, v_k\}\in E_{2}$ (see the center graph in Fig. 3). For $d=6$, we connect one vertex $w_{i,4}$ to the top vertex $w_{i,3}$ of $SG_{5,i}$ (see the right graph in Fig. 3). Similarly, for a general $d\ge 7$, such a $\bot$-shape subgraph consists of one horizontal path of length $2\lceil \frac{d}{4}\rceil - 2$ and one vertical path of $d - \lceil \frac{d}{4}\rceil$. Since the diameter of $SG_{d,i}$ is less than $d$, we can select at most one vertex as the distance-$d$ independent set from each subgraph $SG_{d,i}$ as before. Also, if $\{v_i, v_j\} \in E_{2}$, then $dist_{G_d}(u_i, u_j) < d$; on the other hand if $dist_{G_2}(v_i, v_j) \ge 2$, then $dist_{G_d}(u_i, u_j) = 2\times 2\lceil \frac{d}{4}\rceil \ge d$. $\square$

Fig. 3

($Left$) subgraphs $SG_{4,i}$ for $d=4$, ($Center$) $SG_{5,i}$ for $d=5$, and ($Right$) $SG_{6,i}$ for $d=6$.

4 Chordal graphs

In this section we restrict the instances to chordal graphs. In 1972, Gavril showed that D2IS admits an efficient algorithm for chordal graphs:

Lemma 1

[Gavril 1972] D2IS is in $\mathcal{P}$ for chordal graphs.

Recall that if the $d$th power graph $G^{d}$ is interval trapezoid, or circular-arc, resp.), then the $(d+1)$th power $G^{d+1}$ is also interval (Raychaudhuri 1987) [trapezoid (Flotow 1995), or circular-arc (Flotow 1996), resp.] for any integer $d\ge 1$. The class of chordal graphs does not satisfy the closure property under the graph power operation, i.e., the square $G^2$ of a chordal graph $G$ is not necessarily chordal, but it does satisfy the closure property under the graph odd power operation:

Lemma 2

[Agnarsson et al. 2000; Balakrishnan and Paulraja 1983] Let $d_{o}\ge 1$ be an odd integer. If $G$ is a chordal graph, then $G^{d_{o}}$ is also chordal.

Together with Lemma 1, this yields:

Theorem 3

For every fixed even integer $d_{e}\ge 2$, D $d_{e}$ IS is in $\mathcal{P}$ for chordal graphs.

Proof

Given a chordal graph $G$, we first construct the odd power graph $G^{d_{e}-1}$ from $G$ in polynomial time, which must be chordal by Lemma 2. Then, by using a polynomial-time algorithm for D2IS in Lemma 1, we can obtain a solution of D $d_{e}$ IS in polynomial time. $\square$

For an odd $d_{o}$, D $d_{o}$ IS is hard:

Theorem 4

For every fixed odd $d_{o}\ge 3$, D $d_{o}$ IS is $\mathcal{NP}$-complete for chordal graphs.

Proof

Obviously, D $d_{o}$ IS on chordal graphs is in $\mathcal{NP}$ for every odd $d_{o}\ge 3$. To show that D $d_{o}$ IS on chordal graphs is $\mathcal{NP}$-complete, we reduce D2IS on any graph $G_{2} = (V_{2}, E_{2})$ to D $d_{o}$ IS on a new chordal graph $G_{d_{o}} = (V_{d_{o}}, E_{d_{o}})$.

Given the graph $G_{2} = (V_{2}, E_{2})$ of D2IS with $n$ vertices, $V_{2} = \{v_{1}, v_{2}, \ldots , v_{n}\}$, and $m$ edges, $E_{2} = \{e_{1}, e_{2}, \ldots , e_{m}\}$, we construct the following chordal graph $G_{d_{o}}$: (i) We prepare $n$ paths of length $(d_{o}-3)/2$, $SG_{d_{o},1} = \langle u_{1,1}, u_{1,2}, \ldots , u_{1, (d_{o}-1)/2}\rangle$ through $SG_{d_{o}, n} = \langle u_{n,1}, u_{n,2}, \ldots , u_{n, (d_{o}-1)/2}\rangle$, each $SG_{d_{o},i}$ of which is corresponding to $v_{i} \in V_{2}$, and (ii) $m$ vertices, $w_1$ through $w_{m}$, each $w_{i}$ of which is corresponding to $e_{i} \in E_{2}$. (iii) All the vertices $w_1$ through $w_{m}$ are connected such that $G[\{w_1, \ldots , w_{m}\}]$ forms a clique of $m$ vertices. (iv) If $e_{i} = \{v_{j}, v_{k}\}\in E_{2}$, then we connect $w_{i}$ to two vertices $u_{j,1}$ and $u_{k,1}$.

Figure 4 illustrates the reduced graph $G_{7}$ from $G_2$ which is illustrated in Fig. 1 when $d = 7$. The constructed graph $G_{d_{o}}$ is chordal since all $C_{4}$’s in the clique graph $G[\{w_1, \ldots , w_{m}\}]$ have chords and also $G[\{w_1, \ldots , w_{m}\}\cup \{v_{i,0}\}]$ contains only cycles $C_{3}$’s for every $i$. $G_{d_{o}}$ can be constructed in polynomial time from $G_{2}$.

Fig. 4

An illustration of the construction when $d = 7$.

We show that the reduction satisfies that if $G_{d_{o}}$ has a distance-$d_{o}$ independent set $S_{d_{o}}$ such that $|S_{d_{o}}| \ge k$ if and only in $G_{2}$ has a distance-$2$ independent set $S_{2}$ such that $|S_{2}| \ge k$. In the remaining of this proof, the crucial observations are: (1) The distance between any vertex $v$ in $V_{d_{o}}\setminus \{u_{1,(d_{o}-1)/2}, u_{2,(d_{o}-1)/2}, \ldots , u_{n, (d_{o}-1)/2}\}$ and another vertex $u$ in $V_{d_{o}}\setminus \{v\}$ is at most $d_{o} - 1$. On the other hand, (2) the pairwise distance of any two vertices in $\{u_{1,(d_{o}-1)/2}, u_{2,(d_{o}-1)/2}, \ldots , u_{n, (d_{o}-1)/2}\}$ is at most $d_{o}$. The two observations (1) and (2) imply that the distance-$d_{o}$ independent set $S_{d_{o}}$ in $G_{d_{o}}$ must be a subset of outside vertices $\{u_{1,(d_{o}-1)/2}, u_{2,(d_{o}-1)/2}, \ldots , u_{n, (d_{o}-1)/2}\}$. (3) If $v_{j}$ and $v_{k}$ are two endpoints of single edge $e_i$ in $G_{2}$, then there must be a path

$$\begin{aligned} \langle u_{j,(d_{o}-1)/2}, u_{j,(d_{o}-3)/2}, \ldots , u_{j,1}, w_{i}, u_{k,1}, u_{k,2}, \ldots , u_{k, (d_{o}-1)/2}\rangle \end{aligned}$$

by the above reduction rules. Thus, the distance between $u_{j,d_{o}}$ and $u_{k,d_{o}}$ in $G_{d_{o}}$ is $(d_{o}-1)/2 \times 2 = d_{o} - 1$.

(If part) Now suppose that the graph $G_2$ of D2IS has a distance-$2$ independent set $S_{2} = \{ v_{1^*}, v_{2^*}, \ldots v_{k^*}\}$ in $G_{2}$, where $\{1^*, 2^*, \ldots , k^*\}\subseteq \{1, 2, \ldots , n\}$. Then, we select a subset $S_{d_{o}} = \{u_{1^*,(d_{o}-1)/2}, u_{2^*,(d_{o}-1)/2}, \ldots , u_{k^*,(d_{o}-1)/2}\}$ of size $k$. It is easy to verify that the pairwise distance in $S_{d_{o}}$ is exactly $d_{o}$.

(Only-if part) Conversely, suppose that the reduced graph $G_{d_{o}}$ has the distance-$d_{o}$ independent set $S_{d_{o}} = \{u_{1^*,(d_{o}-1)/2}, u_{2^*,(d_{o}-1)/2}, \ldots , u_{k^*,(d_{o}-1)/2}\}$ of size $k$. Then, the pairwise distance in the corresponding subset of vertices $\{v_{1^*}, v_{2^{*}}, \ldots , v_{k^*}\}$ of $G_{2}$ is surely at least two, i.e., $G_{2}$ has a distance-$2$ independent set $S_{2}$ such that $|S_{2}| \ge k$. $\square$

Corollary 3

D3IS is $\mathcal{NP}$-complete for split graphs.

Proof

When $d = 3$ in the proof of Theorem 4, the constructed graph $G_{3}$ is a split graph since there is a partition of $V(G_{3})$ into a clique set $\{w_{1}, w_{2}, \ldots , w_{m}\}$ and an independent set $\{u_{1,1}, u_{2,1}, \ldots , u_{n,1}\}$. $\square$

Similarly to the previous section, it can be shown that the reduction in the proof of Theorem 4 can preserve the approximation-gap, and also it is an fpt-reduction:

Corollary 4

For any $\varepsilon > 0$ and fixed odd integer $d_{o}\ge 3$, it is $\mathcal{NP}$-hard to approximate MaxD d $_{o}$ IS to within a factor of $n^{1/2-\varepsilon }$ for chordal graphs.

Proof

The proof is very similar to the proof of Corollary 1. Now, let $OPT^{\prime }(G_{d_{o}})$ denote the number of vertices of an optimal solution for a $\nu$-vertex input chordal graph $G_{d_{o}}$ of MaxD d $_{o}$ IS for a fixed $d_{o}\ge 3$. Then, we can show that (1) if $OPT(G_{2}) \ge g(n)$, then $OPT^{\prime }(G_{d_{o}}) \ge g(n)$, and (2) if $OPT(G_{2}) < \frac{g(n)}{n^{1-\varepsilon }}$ for a positive constant $\varepsilon$, then $OPT^{\prime }(G_{d_{o}}) < \frac{g(n)}{n^{1-\varepsilon }}$. Hence the corollary follows from $\nu = O(n^2)$. $\square$

Corollary 5

For every fixed odd integer $d_{o}\ge 3$, ParaD $d_{o}$ IS( k ) is $\mathcal{W}[1]$-hard for chordal graphs.

Proof

Let $(G_2, k)$ and $(G_{d_{o}}, k^{\prime })$ be the inputs of ParaD2IS( k ) and ParaD $d_{o}$ IS( k ’) on chordal graphs, respectively. Then, the reduction in the proof of Theorem 4 satisfies the condition $k^{\prime }\le k$. $\square$

5 Concluding remarks

In the conference version (Eto et al. 2012) of this paper we claimed that the reduced graph $G_{d}$ in the proof of Theorem 1 is chordal bipartite and thus D $d$ IS on chordal bipartite graphs is $\mathcal{NP}$-hard. However, $G_{d}$ is not chordal bipartite since it includes an induced cycle of length six or more (for example, actually $G_3$ in Fig. 1 contains an induced cycle $\langle u_1, w_1, u_2, w_3, u_3, w_2, u_1\rangle$ of length six). Therefore, the computational complexity of D $d$ IS on chordal bipartite graphs is still open.