Title: Distance-d Independent Set Problems for Bipartite and Chordal Graphs
Abstract: The paper studies a generalization of the Independent Set (IS) problem. A distance-d independent set for a positive integer d ≥ 2 in an unweighted graph G = (V, E) is a set 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 (D d IS) problem is to decide whether G contains a distance-d independent set S such that |S| ≥ k. D2IS is identical to the original IS and thus D2IS is in ${\cal P}$ for bipartite graphs and chordal graphs. In this paper, we show that for every fixed integer d ≥ 3, D d IS is ${\cal NP}$ -complete even for planar bipartite graphs of maximum degree three, and also ${\cal NP}$ -complete even for chordal bipartite graphs. Furthermore, 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 ≥ 2, whereas D d IS is ${\cal NP}$ -complete for any odd d ≥ 3.
Publication Year: 2012
Publication Date: 2012-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot