Abstract
In the \(d\)-Scattered Set problem we are asked to select at least k vertices of a given graph, so that the distance between any pair is at least d. We study the problem’s (in-)approximability and offer improvements and extensions of known results for Independent Set, of which the problem is a generalization. Specifically, we show:
-
A lower bound of \(\Delta ^{\lfloor d/2\rfloor -\epsilon }\) on the approximation ratio of any polynomial-time algorithm for graphs of maximum degree \(\Delta \) and an improved upper bound of \(O(\Delta ^{\lfloor d/2\rfloor })\) on the approximation ratio of any greedy scheme for this problem.
-
A polynomial-time \(2\sqrt{n}\)-approximation for bipartite graphs and even values of d, that matches the known lower bound by considering the only remaining case.
-
A lower bound on the complexity of any \(\rho \)-approximation algorithm of (roughly) \(2^{\frac{n^{1-\epsilon }}{\rho d}}\) for even d and \(2^{\frac{n^{1-\epsilon }}{\rho (d+\rho )}}\) for odd d (under the randomized ETH), complemented by \(\rho \)-approximation algorithms of running times that (almost) match these bounds.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We note that this value of \(\epsilon _2\) is for odd values of d. For d even, the correct value is such that we have the (slightly lower) bound \(\delta ^{1+\epsilon _2}=\delta +3\delta ^{1+2\epsilon _1/d}\), but we write \(\epsilon _2\) for both cases to simplify notation.
References
Alon, N., Feige, U., Wigderson, A., Zuckerman, D.: Derandomized graph products. Comput. Complex. 5(1), 60–75 (1995)
Berman, P., Karpinski, M.: On some tighter inapproximability results (Extended Abstract). In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200–209. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48523-6_17
Bollobás, B., Chung, F.R.K.: The diameter of a cycle plus a random matching. SIAM J. Discret. Math. 1(3), 328–333 (1988)
Bonnet, E., Lampis, M., Paschos, V.Th.: Time-approximation trade-offs for inapproximable problems. In: STACS, LIPIcs, vol. 47, pp. 22:1–22:14 (2016)
Bourgeois, N., Escoffier, B., Paschos, V.Th.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159(17), 1954–1970 (2011)
Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. In: FOCS, vol. 47, pp. 370–379 (2013)
Cygan, M., Kowalik, L., Pilipczuk, M., Wykurz, M.: Exponential-time approximation of hard problems. CoRR, abs/0810.4934 (2008)
Demange, M., Paschos, V.Th.: Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett. 10(3), 105–110 (1997)
Eto, H., Guo, F., Miyano, E.: Distance- \(d\) independent set problems for bipartite and chordal graphs. J. Comb. Optim. 27(1), 88–99 (2014)
Eto, H., Ito, T., Liu, Z., Miyano, E.: Approximability of the distance independent set problem on regular graphs and planar graphs. In: Chan, T.-H.H., Li, M., Wang, L. (eds.) COCOA 2016. LNCS, vol. 10043, pp. 270–284. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48749-6_20
Eto, H., Ito, T., Liu, Z., Miyano, E.: Approximation algorithm for the distance-3 independent set problem on cubic graphs. In: Poon, S.-H., Rahman, M.S., Yen, H.-C. (eds.) WALCOM 2017. LNCS, vol. 10167, pp. 228–240. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53925-6_18
Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: SODA, pp. 748–759. SIAM (2011)
Halldórsson, M.M., Kratochvil, J., Telle, J.A.: Independent sets with domination constraints. Discret. Appl. Math. 99(1–3), 39–54 (2000)
Halldórsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18(1), 145–163 (1997)
Håstad, J.: Clique is hard to approximate within \(n^{1-\epsilon }\). Acta Mathematica 182, 105–142 (1999)
Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)
Katsikarelis, I., Lampis, M., Paschos, V.Th.: Structurally parameterized \(d\)-scattered set. In: Brandstädt, A., Köhler, E., Meer, K. (eds.) WG. LNCS, pp. 292–305, vol. 11159. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-00256-5_24
Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 865–877. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48350-3_72
Montealegre, P., Todinca, I.: On distance-d independent set and other problems in graphs with “few” minimal separators. In: Heggernes, P. (ed.) WG 2016. LNCS, vol. 9941, pp. 183–194. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53536-3_16
Pilipczuk, M., Siebertz, S.: Kernelization and approximation of distance-r independent sets on nowhere dense graphs. CoRR, abs/1809.05675 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Katsikarelis, I., Lampis, M., Paschos, V.T. (2020). Improved (In-)Approximability Bounds for d-Scattered Set. In: Bampis, E., Megow, N. (eds) Approximation and Online Algorithms. WAOA 2019. Lecture Notes in Computer Science(), vol 11926. Springer, Cham. https://doi.org/10.1007/978-3-030-39479-0_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-39479-0_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-39478-3
Online ISBN: 978-3-030-39479-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)