{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:52Z","timestamp":1740109312128,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2020,6,19]],"date-time":"2020-06-19T00:00:00Z","timestamp":1592524800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,19]],"date-time":"2020-06-19T00:00:00Z","timestamp":1592524800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach et al.\u00a0(27th symposium on discrete algorithms (SODA), pp 1306\u20131325, 2016) introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks satisfy both properties and exploit them to design faster algorithms for a number of classical graph problems. We complement their work by showing that some well-studied random graph models exhibit both of the mentioned PLB properties. PLB-U and PLB-N hold with high probability for Chung\u2013Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability or almost surely for those random graph classes. In the second part we study three classical <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mi>NP<\/mml:mi>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard optimization problems on PLB networks. It is known that on general graphs with maximum degree\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mi>\u0394<\/mml:mi>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>, a greedy algorithm, which chooses nodes in the order of their degree, only achieves a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega (\\ln \\Delta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mrow>\n<mml:mi>\u03a9<\/mml:mi>\n<mml:mo>(<\/mml:mo>\n<mml:mo>ln<\/mml:mo>\n<mml:mi>\u0394<\/mml:mi>\n<mml:mo>)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for <jats:sc>Minimum Vertex Cover<\/jats:sc> and <jats:sc>Minimum Dominating Set<\/jats:sc>, and a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega (\\Delta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mrow>\n<mml:mi>\u03a9<\/mml:mi>\n<mml:mo>(<\/mml:mo>\n<mml:mi>\u0394<\/mml:mi>\n<mml:mo>)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for <jats:sc>Maximum Independent Set<\/jats:sc>. We prove that the PLB-U property with <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\beta &gt;2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mrow>\n<mml:mi>\u03b2<\/mml:mi>\n<mml:mo>&gt;<\/mml:mo>\n<mml:mn>2<\/mml:mn>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> suffices for the greedy approach to achieve a constant-factor approximation for all three problems. We also show that these problems are -hard even if PLB-U, PLB-N, and an additional power-law lower bound on the degree distribution hold. Hence, a PTAS cannot be expected unless  = . Furthermore, we prove that all three problems are in  if the PLB-U property holds.<\/jats:p>","DOI":"10.1007\/s00453-020-00729-z","type":"journal-article","created":{"date-parts":[[2020,6,19]],"date-time":"2020-06-19T03:57:31Z","timestamp":1592539051000},"page":"3338-3389","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Greed is Good for Deterministic Scale-Free Networks"],"prefix":"10.1007","volume":"82","author":[{"given":"Ankit","family":"Chauhan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4133-2437","authenticated-orcid":false,"given":"Ralf","family":"Rothenberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,19]]},"reference":[{"key":"729_CR1","doi-asserted-by":"crossref","unstructured":"Adamic, L.A., Buyukkokten, O., Adar, E.: A social network caught in the web. First Monday 8(6), (2003)","DOI":"10.5210\/fm.v8i6.1057"},{"key":"729_CR2","doi-asserted-by":"crossref","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for massive graphs. In: 32nd Symposium on Theory of Computing (STOC), pp. 171\u2013180 (2000)","DOI":"10.1145\/335305.335326"},{"issue":"1","key":"729_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","volume":"10","author":"W Aiello","year":"2001","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for power law graphs. Exp. Math. 10(1), 53\u201366 (2001)","journal-title":"Exp. Math."},{"issue":"1","key":"729_CR4","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., Barab\u00e1si, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47 (2002)","journal-title":"Rev. Mod. Phys."},{"key":"729_CR5","doi-asserted-by":"crossref","unstructured":"Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: 3rd Italian Conference on Algorithms and Complexity (CIAC), pp. 288\u2013298 (1997)","DOI":"10.1007\/3-540-62592-5_80"},{"issue":"1","key":"729_CR6","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01277956","volume":"5","author":"N Alon","year":"1995","unstructured":"Alon, N., Feige, U., Wigderson, A., Zuckerman, D.: Derandomized graph products. Comput. Complex. 5(1), 60\u201375 (1995)","journal-title":"Comput. Complex."},{"key":"729_CR7","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509\u2013512 (1999)","journal-title":"Science"},{"key":"729_CR8","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results. In: 26th International Colloquium on Automata, Languages and Programming (ICALP), pp. 200\u2013209 (1999)","DOI":"10.1007\/3-540-48523-6_17"},{"key":"729_CR9","doi-asserted-by":"crossref","unstructured":"Borassi, M., Crescenzi, P., Trevisan, L.: An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. In: 28th Symposium Discrete Algorithms (SODA), pp. 920\u2013939 (2017)","DOI":"10.1137\/1.9781611974782.58"},{"key":"729_CR10","first-page":"406","volume-title":"The Power of Local Information in Social Networks","author":"C Borgs","year":"2012","unstructured":"Borgs, C., Brautbar, M., Chayes, J., Khanna, S., Lucier, B.: The Power of Local Information in Social Networks, pp. 406\u2013419. Springer, Berlin (2012)"},{"key":"729_CR11","doi-asserted-by":"crossref","unstructured":"Brach, P., Cygan, M., Lacki, J., Sankowski, P.: Algorithmic complexity of power law networks. In: 27th Symposium on Discrete Algorithms (SODA), pp. 1306\u20131325 (2016)","DOI":"10.1137\/1.9781611974331.ch91"},{"key":"729_CR12","unstructured":"Bringmann, K., Keusch, R., Lengler, J.: Geometric inhomogeneous random graphs. CoRR arXiv:abs\/1511.00576 (2015)"},{"key":"729_CR13","unstructured":"Bringmann, K., Keusch, R., Lengler, J.: Average distance in a general class of scale-free networks with underlying geometry. CoRR arXiv:abs\/1602.05712 (2016)"},{"key":"729_CR14","unstructured":"Bringmann, K., Keusch, R., Lengler, J.: Sampling geometric inhomogeneous random graphs in linear time. In: 25th European Symposium on Algorithms (ESA), vol.\u00a087, pp. 20:1\u201320:15 (2017)"},{"issue":"3","key":"729_CR15","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"M Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320\u2013338 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"11","key":"729_CR16","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206(11), 1264\u20131275 (2008)","journal-title":"Inf. Comput."},{"issue":"25","key":"729_CR17","doi-asserted-by":"publisher","first-page":"15879","DOI":"10.1073\/pnas.252631999","volume":"99","author":"F Chung","year":"2002","unstructured":"Chung, F., Lu, L.: The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. 99(25), 15879\u201315882 (2002)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"2","key":"729_CR18","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/PL00012580","volume":"6","author":"F Chung","year":"2002","unstructured":"Chung, F., Lu, L.: Connected components in random graphs with given expected degree sequences. Ann. Comb. 6(2), 125\u2013145 (2002)","journal-title":"Ann. Comb."},{"key":"729_CR19","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Kann, V.: Approximation on the web: a compendium of NP optimization problems. In: Rolim, J.D.P. (ed.) International Workshop Randomization and Approximation Techniques in Computer Science (RANDOM\u201997), Lecture Notes in Computer Science, vol. 1269, pp. 111\u2013118 (1997)","DOI":"10.1007\/3-540-63248-4_10"},{"key":"729_CR20","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439\u2013485 (2005)","journal-title":"Ann. Math."},{"key":"729_CR21","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (2012)"},{"key":"729_CR22","volume-title":"Design and Analysis of Approximation Algorithms","author":"DZ Du","year":"2011","unstructured":"Du, D.Z., Ko, K.I., Hu, X.: Design and Analysis of Approximation Algorithms. Springer, Berli (2011)"},{"key":"729_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"729_CR24","doi-asserted-by":"crossref","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: Symposium Communications Architectures and Protocols (SIGCOMM), pp. 251\u2013262 (1999)","DOI":"10.1145\/316194.316229"},{"issue":"4","key":"729_CR25","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"729_CR26","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.tcs.2007.12.007","volume":"393","author":"A Ferrante","year":"2008","unstructured":"Ferrante, A., Pandurangan, G., Park, K.: On the hardness of optimization in power-law graphs. Theor. Comput. Sci. 393(1\u20133), 220\u2013230 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"729_CR27","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"issue":"3","key":"729_CR28","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"Supplement C","key":"729_CR29","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1016\/j.tcs.2014.10.021","volume":"562","author":"M Gast","year":"2015","unstructured":"Gast, M., Hauptmann, M., Karpinski, M.: Inapproximability of dominating set on power law graphs. Theor. Comput. Sci. 562(Supplement C), 436\u2013452 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"729_CR30","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. In: 26th Symposium Theory of Computing (STOC), pp. 439\u2013448 (1994)","DOI":"10.1145\/195058.195221"},{"key":"729_CR31","unstructured":"Hauptmann, M., Karpinski, M.: On the approximability of independent set problem on power law graphs. CoRR arXiv:abs\/1503.02880 (2015)"},{"key":"729_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27848-8","volume-title":"Encyclopedia of Algorithms","author":"M Kao","year":"2008","unstructured":"Kao, M.: Encyclopedia of Algorithms. Springer, Berlin (2008)"},{"key":"729_CR33","unstructured":"Koch, C., Lengler, J.: Bootstrap percolation on geometric inhomogeneous random graphs. In: 43rd International Colloquium on Automata, Languages and Programming (ICALP) (2016)"},{"issue":"3","key":"729_CR34","doi-asserted-by":"publisher","first-page":"036106","DOI":"10.1103\/PhysRevE.82.036106","volume":"82","author":"D Krioukov","year":"2010","unstructured":"Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., Bogun\u00e1, M.: Hyperbolic geometry of complex networks. Phys. Rev. E 82(3), 036106 (2010)","journal-title":"Phys. Rev. E"},{"issue":"11\u201316","key":"729_CR35","doi-asserted-by":"publisher","first-page":"1481","DOI":"10.1016\/S1389-1286(99)00040-7","volume":"31","author":"R Kumar","year":"1999","unstructured":"Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Trawling the web for emerging cyber-communities. Comput. Netw. 31(11\u201316), 1481\u20131493 (1999)","journal-title":"Comput. Netw."},{"key":"729_CR36","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Minimum dominating set approximation in graphs of bounded arboricity. In: 24th International Symposium Distributed Computing (DISC), pp. 510\u2013524 (2010)","DOI":"10.1007\/978-3-642-15763-9_48"},{"key":"729_CR37","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection (2014). http:\/\/snap.stanford.edu\/data"},{"issue":"2","key":"729_CR38","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137\u2013153 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"729_CR39","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"MEJ Newman","year":"2003","unstructured":"Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167\u2013256 (2003)","journal-title":"SIAM Rev."},{"key":"729_CR40","first-page":"35","volume-title":"Random Graphs as Models of Networks, Handbook of Graphs and Networks","author":"MEJ Newman","year":"2005","unstructured":"Newman, M.E.J.: Random Graphs as Models of Networks, Handbook of Graphs and Networks, pp. 35\u201368. Wiley, New York (2005)"},{"key":"729_CR41","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, London (1982)"},{"issue":"3","key":"729_CR42","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"729_CR43","doi-asserted-by":"publisher","DOI":"10.1002\/9780470749722","volume-title":"Computer Relaying for Power Systems","author":"AG Phadke","year":"2009","unstructured":"Phadke, A.G., Thorp, J.S.: Computer Relaying for Power Systems. Wiley, New York (2009)"},{"issue":"1\u20133","key":"729_CR44","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.tcs.2004.08.013","volume":"329","author":"L Ruan","year":"2004","unstructured":"Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.I.: A greedy approximation for minimum connected dominating sets. Theor. Comput. Sci. 329(1\u20133), 325\u2013330 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"729_CR45","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0166-218X(02)00205-6","volume":"126","author":"S Sakai","year":"2003","unstructured":"Sakai, S.: A note on greedy algorithms for the maximum weighted independent set problem. Discrete Appl. Math. 126, 313\u2013322 (2003)","journal-title":"Discrete Appl. Math."},{"key":"729_CR46","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.tcs.2011.10.023","volume":"447","author":"Y Shen","year":"2012","unstructured":"Shen, Y., Nguyen, D.T., Xuan, Y., Thai, M.T.: New techniques for approximating optimal substructure problems in power-law graphs. Theor. Comput. Sci. 447, 107\u2013119 (2012)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00729-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00729-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00729-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T23:39:14Z","timestamp":1624059554000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00729-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,19]]},"references-count":46,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["729"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00729-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,6,19]]},"assertion":[{"value":"13 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}