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 (DdIS 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 NP-complete even for planar graphs, but it is in P for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of DdIS, its maximization version MaxDdIS, and its parameterized version ParaDdIS(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 NP-hard to approximate MaxDdIS to within a factor of n~(1/2?ε) for bipartite graphs of n vertices, and for any fixed integer d ≥ 3, ParaDdIS(k) is W1-hard for bipartite graphs. Then, (2) we prove that for every fixed integer d ≥ 3, DdIS 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 DdIS can be solved in polynomial time for any even d ≥ 2, whereas DdIS is NP-complete for any odd d ≥ 3. Also, we show the hardness of approximation of MaxDdIS and the W1-hardness of ParaDdIS(k) on chordal graphs for any odd d ≥ 3.