TY - GEN

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

AU - Eto, Hiroshi

AU - Guo, Fengrui

AU - Miyano, Eiji

PY - 2012/8/20

Y1 - 2012/8/20

N2 - 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 for bipartite graphs and chordal graphs. In this paper, we show that for every fixed integer d ≥ 3, D d IS is -complete even for planar bipartite graphs of maximum degree three, and also -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 -complete for any odd d ≥ 3.

AB - 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 for bipartite graphs and chordal graphs. In this paper, we show that for every fixed integer d ≥ 3, D d IS is -complete even for planar bipartite graphs of maximum degree three, and also -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 -complete for any odd d ≥ 3.

UR - http://www.scopus.com/inward/record.url?scp=84865023969&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865023969&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31770-5_21

DO - 10.1007/978-3-642-31770-5_21

M3 - Conference contribution

AN - SCOPUS:84865023969

SN - 9783642317699

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 234

EP - 244

BT - Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Proceedings

T2 - 6th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2012

Y2 - 5 August 2012 through 9 August 2012

ER -