Exact Exponential Algorithm for Distance-3 Independent Set Problem

Katsuhisa YAMANAKA  Shogo KAWARAGI  Takashi HIRAYAMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.499-501
Publication Date: 2019/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCL0002
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)
>>Buy this Article

Let G=(V,E) be an unweighted simple graph. A distance-d independent set is a subset IV 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.