Experimental Evaluation of Approximation and Heuristic Algorithms for Maximum Distance-Bounded Subgraph Problems

In this paper, we consider two distance-based relaxed variants of the maximum clique problem (Max Clique), named Maxd-Clique and Maxd-Club for positive integers d. Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of \(n^{1-\varepsilon }\) for any real \(\varepsilon > 0\) unless \({{{\mathcal {P}}}} = {{\mathcal {NP}}}\), since they are identical to Max Clique (Håstad in Acta Math 182(1):105–142, 1999; Zuckerman in Theory Comput 3:103–128, 2007). In addition, it is \({{\mathcal {NP}}}\)-hard to approximate Maxd-Clique and Maxd-Club to within a factor of \(n^{1/2 - \varepsilon }\) for any fixed integer \(d\ge 2\) and any real \(\varepsilon > 0\) (Asahiro et al. in Approximating maximum diameter-bounded subgraphs. In: Proc of LATIN 2010, Springer, pp 615–626, 2010; Asahiro et al. in Optimal approximation algorithms for maximum distance-bounded subgraph problems. In: Proc of COCOA, Springer, pp 586–600, 2015). As for approximability of Maxd-Clique and Maxd-Club, a polynomial-time algorithm, called ReFindStar\(_d\), that achieves an optimal approximation ratio of \(O(n^{1/2})\) for Maxd-Clique and Maxd-Club was designed for any integer \(d\ge 2\) in Asahiro et al. (2015, Algorithmica 80(6):1834–1856, 2018). Moreover, a simpler algorithm, called ByFindStar\(_d\), was proposed and it was shown in Asahiro et al. (2010, 2018) that although the approximation ratio of ByFindStar\(_d\) is much worse for any odd\(d\ge 3\), its time complexity is better than ReFindStar\(_d\). In this paper, we implement those approximation algorithms and evaluate their quality empirically for random graphs. The experimental results show that (1) ReFindStar\(_d\) can find larger d-clubs (d-cliques) than ByFindStar\(_d\) for odd d, (2) the size of d-clubs (d-cliques) output by ByFindStar\(_d\) is the same as ones by ReFindStar\(_d\) for even d, and (3) ByFindStar\(_d\) can find the same size of d-clubs (d-cliques) much faster than ReFindStar\(_d\). Furthermore, we propose and implement two new heuristics, Hclub\(_d\) for Maxd-Club and Hclique\(_d\) for Maxd-Clique. Then, we present the experimental evaluation of the solution size of ReFindStar\(_d\), Hclub\(_d\), Hclique\(_d\) and previously known heuristic algorithms for random graphs and Erdős collaboration graphs.