Advertisement
Published in:
2016 | OriginalPaper | Chapter
Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
Authors : Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (\(\mathsf{MaxD}d\mathsf{IS}\) for short). For an integer \(d \ge 2\), a distance-d independent set of an unweighted graph \(G = (V, E)\) is a subset \(S \subseteq V\) of vertices such that for any pair of vertices \(u, v \in 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 \(\mathsf{MaxD}d\mathsf{IS}\) 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\ge 3\)) and planar graphs, as follows: (1) For every fixed integers \(d\ge 3\) and \(r\ge 3\), \(\mathsf{MaxD}d\mathsf{IS}\) on r-regular graphs is APX-hard. (2) We design polynomial-time \(O(r^{d-1})\)-approximation and \(O(r^{d-2}/d)\)-approximation algorithms for \(\mathsf{MaxD}d\mathsf{IS}\) on r-regular graphs. (3) We sharpen the above \(O(r^{d-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 \(\mathsf{MaxD}d\mathsf{IS}\) admits a polynomial-time approximation scheme (PTAS) for planar graphs.