Exact Exponential Algorithm for Distance-3 Independent Set Problem
Katsuhisa Yamanaka, Shogo KAWARAGI, Takashi HIRAYAMA · IEICE Transactions on Information and Systems · 2019
Let G = (V, E) be an unweighted simple graph.A distance-d independent set is a subset I ⊆ V such that dist(u, v) ≥ d for any two vertices u, v in I, where dist(u, v) is the distance between u and v.Then, Maximum Distance-d Independent Set problem requires to compute the size of a distance-d independent set with the maximum number of vertices.Even for a fixed integer d ≥ 3, this problem is NP-hard.In this paper, we design an exact exponential algorithm that calculates the size of a maximum distance-3 independent set in O(1.4143 n ) time.key words: exact exponential algorithm, independent set, distance-d independent set, maximum distance-d independent set