For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Exact Exponential Algorithm for Distance-3 Independent Set Problem
Katsuhisa YAMANAKA Shogo KAWARAGI Takashi HIRAYAMA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2019/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
exact exponential algorithm, independent set, distance-d independent set, maximum distance-d independent set,
Full Text: PDF(125.6KB)>>
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.4143n) time.