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 }$$ n 1 - ε for any real $$\varepsilon > 0$$ ε > 0 unless $${{{\mathcal {P}}}} = {{\mathcal {NP}}}$$ P = 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}}}$$ NP -hard to approximate Maxd-Clique and Maxd-Club to within a factor of $$n^{1/2 - \varepsilon }$$ n 1 / 2 - ε for any fixed integer $$d\ge 2$$ d ≥ 2 and any real $$\varepsilon > 0$$ ε > 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$$ d , that achieves an optimal approximation ratio of $$O(n^{1/2})$$ O ( n 1 / 2 ) for Maxd-Clique and Maxd-Club was designed for any integer $$d\ge 2$$ d ≥ 2 in Asahiro et al. (2015, Algorithmica 80(6):1834–1856, 2018). Moreover, a simpler algorithm, called ByFindStar $$_d$$ d , was proposed and it was shown in Asahiro et al. (2010, 2018) that although the approximation ratio of ByFindStar $$_d$$ d is much worse for any odd $$d\ge 3$$ d ≥ 3 , its time complexity is better than ReFindStar $$_d$$ 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$$ d can find larger d-clubs (d-cliques) than ByFindStar $$_d$$ d for odd d, (2) the size of d-clubs (d-cliques) output by ByFindStar $$_d$$ d is the same as ones by ReFindStar $$_d$$ d for even d, and (3) ByFindStar $$_d$$ d can find the same size of d-clubs (d-cliques) much faster than ReFindStar $$_d$$ d . Furthermore, we propose and implement two new heuristics, Hclub $$_d$$ d for Maxd-Club and Hclique $$_d$$ d for Maxd-Clique. Then, we present the experimental evaluation of the solution size of ReFindStar $$_d$$ d , Hclub $$_d$$ d , Hclique $$_d$$ d and previously known heuristic algorithms for random graphs and Erdős collaboration graphs.