Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems.

In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max<italic>d</italic>-Clique and Max<italic>d</italic>-Club: A <italic>d</italic>-<italic>clique</italic> in a graph G=(V,E)<inline-graphic></inline-graphic> is a subset S⊆V<inline-graphic></inline-graphic> of vertices such that for every pair of vertices u,v∈S<inline-graphic></inline-graphic>, the distance between <italic>u</italic> and <italic>v</italic> is at most <italic>d</italic> in <italic>G</italic>. A <italic>d-club</italic> in a graph G=(V,E)<inline-graphic></inline-graphic> is a subset S′⊆V<inline-graphic></inline-graphic> of vertices that induces a subgraph of <italic>G</italic> of diameter at most <italic>d</italic>. Given a graph <italic>G</italic> with <italic>n</italic> vertices, the goal of Max<italic>d</italic>-Clique (Max<italic>d</italic>-Club, resp.) is to find a <italic>d</italic>-clique (<italic>d</italic>-club, resp.) of maximum cardinality in <italic>G</italic>. Since Max 1-Clique and Max 1-Club are identical to Max Clique, the inapproximabilty for Max Clique shown by Zuckerman in 2007 is transferred to them. Namely, Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n1-ε<inline-graphic></inline-graphic> for any ε>0<inline-graphic></inline-graphic> unless P=NP<inline-graphic></inline-graphic>. Also, in 2002, Marinc˘<inline-graphic></inline-graphic>ek and Mohar showed that it is NP<inline-graphic></inline-graphic>-hard to approximate Max<italic>d</italic>-Club to within a factor of n1/3-ε<inline-graphic></inline-graphic> for any ε>0<inline-graphic></inline-graphic> and any fixed d≥2<inline-graphic></inline-graphic>. In this paper, we strengthen the hardness result; we prove that, for any ε>0<inline-graphic></inline-graphic> and any fixed d≥2<inline-graphic></inline-graphic>, it is NP<inline-graphic></inline-graphic>-hard to approximate Max<italic>d</italic>-Club to within a factor of n1/2-ε<inline-graphic></inline-graphic>. Then, we design a polynomial-time algorithm which achieves an <italic>optimal</italic> approximation ratio of O(n1/2)<inline-graphic></inline-graphic> for any integer d≥2<inline-graphic></inline-graphic>. By using the similar ideas, we show the O(n1/2)<inline-graphic></inline-graphic>-approximation algorithm for Max<italic>d</italic>-Clique for any d≥2<inline-graphic></inline-graphic>. This is the best possible in polynomial time unless P=NP<inline-graphic></inline-graphic>, as we can prove the Ω(n1/2-ε)<inline-graphic></inline-graphic>-inapproximability. [ABSTRACT FROM AUTHOR]