Distance- independent set problems for bipartite and chordal graphs
The paper studies a generalization of the Independent Set problem (IS for short). A distance- independent set for an integer in an unweighted graph is a subset of vertices such that for any pair of vertices , the distance between and is at least in . Given an unweighted graph and a positive integer , the Distance- Independent Set problem (D IS for short) is to decide whether contains a distance- independent set such that . D2IS is identical to the original IS. Thus D2IS is -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 IS, its maximization version MaxD IS, and its parameterized version ParaD IS(), where the parameter is the size of the distance- independent set: (1) We first prove that for any and any fixed integer , it is -hard to approximate MaxD IS to within a factor of for bipartite graphs of vertices, and for any fixed integer , ParaD IS() is -hard for bipartite graphs. Then, (2) we prove that for every fixed integer , D IS remains -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 IS can be solved in polynomial time for any even , whereas D IS is -complete for any odd . Also, we show the hardness of approximation of MaxD IS and the -hardness of ParaD IS() on chordal graphs for any odd .
chordal graphs bipartite graphs computational complexity distance-d independent set