TY - GEN
T1 - Approximability of the distance independent set problem on regular graphs and planar graphs
AU - Eto, Hiroshi
AU - Ito, Takehiro
AU - Liu, Zhilong
AU - Miyano, Eiji
N1 - Funding Information:
This work is partially supported by JSPS KAKENHI Grant Numbers JP15J05484, JP15H00849, JP16K00004, and JP26330017.
Publisher Copyright:
© Springer International Publishing AG 2016.
PY - 2016
Y1 - 2016
N2 - This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V,E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r ≥ 3) and planar graphs, as follows: (1) For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd−1)-approximation and O(rd−2/d)- approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd−2/d)-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.
AB - This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V,E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r ≥ 3) and planar graphs, as follows: (1) For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd−1)-approximation and O(rd−2/d)- approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd−2/d)-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.
UR - http://www.scopus.com/inward/record.url?scp=85007188790&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85007188790&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-48749-6_20
DO - 10.1007/978-3-319-48749-6_20
M3 - Conference contribution
AN - SCOPUS:85007188790
SN - 9783319487489
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 270
EP - 284
BT - Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings
A2 - Li, Minming
A2 - Wang, Lusheng
A2 - Chan, T-H. Hubert
PB - Springer Verlag
T2 - 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016
Y2 - 16 December 2016 through 18 December 2016
ER -