Document Zbl 1521.68256

Nadara, Wojciech; Pilipczuk, Marcin; Rabinovich, Roman; Reidl, Felix; Siebertz, Sebastian

Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness. (English) Zbl 1521.68256

ACM J. Exp. Algorithm. 24, No. 2, Article No. 2.6, 34 p. (2019).

MSC:

68W25	Approximation algorithms
05C15	Coloring of graphs and hypergraphs
05C42	Density (toughness, etc.)
68R10	Graph theory (including graph drawing) in computer science

Keywords:

nowhere dense graph classes; approximation; generalized coloring numbers; uniform quasi-wideness

Cite Review PDF

Full Text: DOI Link

References:

[1]	. Gephi Datasets. Retrieved from https://github.com/gephi/gephi/wiki/Datasets.
[2]	. LEDA. Retrieved from http://www.algorithmic-solutions.com/leda/index.htm.
[3]	2018. Recent trends in kernelization: Theory and experimental evaluation—project website. Retrieved from http://kernelization-experiments.mimuw.edu.pl.
[4]	Lada A. Adamic and Natalie Glance. 2005. The political blogosphere and the 2004 US election: Divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery. ACM, 36-43.
[5]	Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz. 2018. Distributed domination on graph classes of bounded expansion. In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA’18). 143-151.
[6]	Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. 2004. Polynomial-time data reduction for dominating set. J. ACM 51, 3 (2004), 363-384. · Zbl 1192.68337
[7]	Vladimir Batagelj and Andrej Mrvar. 2006. Pajek datasets. Retrieved from http://vlado.fmf.uni-lj.si/pub/networks/data/.
[8]	Anne Berry, Jean-Paul Bordat, and Olivier Cogis. 2000. Generating all the minimal separators of a graph. Int. J. Found. Comput. Sci. 11, 3 (2000), 397-403. · Zbl 1320.05120
[9]	Hans L. Bodlaender. 1996. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 6 (1996), 1305-1317. · Zbl 0864.68074
[10]	Hans L. Bodlaender. 1997. Treewidth: Algorithmic techniques and results. In Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science (MFCS’97), Vol. 1295. 19-36. · Zbl 0941.05057
[11]	Hans L. Bodlaender and Arie M. C. A. Koster. 2010. Treewidth computations I. Upper bounds. Inform. Computat. 208, 3 (2010), 259-275. · Zbl 1186.68328
[12]	Dongbo Bu, Yi Zhao, Lun Cai, Hong Xue, Xiaopeng Zhu, Hongchao Lu, Jingfen Zhang, Shiwei Sun, Lunjiang Ling, Nan Zhang, et al. 2003. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucl. Acids Res. 31, 9 (2003), 2443-2450.
[13]	Eunjoon Cho, Seth A. Myers, and Jure Leskovec. 2011. Friendship and mobility: User movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1082-1090.
[14]	Fan Chung and Linyuan Lu. 2002. The average distances in random graphs with given expected degrees. Proc. Nat. Acad. Sci. 99, 25 (2002), 15879-15882. · Zbl 1064.05137
[15]	Fan Chung and Linyuan Lu. 2002. Connected components in random graphs with given expected degree sequences. Ann. Combinat. 6, 2 (2002), 125-145. · Zbl 1009.05124
[16]	Fan R. K. Chung and Linyuan Lu. 2003. The average distance in a random graph with given expected degrees. Internet Math. 1, 1 (2003), 91-113. · Zbl 1065.05084
[17]	Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. · Zbl 1334.90001
[18]	Kedar Nath Das and Biplab Chaudhuri. 2012. Heuristics to find maximum independent set: An overview. In Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS’11). 881-892.
[19]	Anuj Dawar. 2010. Homomorphism preservation on quasi-wide classes. J. Comput. Syst. Sci. 76, 5 (2010), 324-332. · Zbl 1206.68140
[20]	Anuj Dawar and Stephan Kreutzer. 2009. Domination problems in nowhere-dense classes. In Proceedings of the IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’09). 157-168. · Zbl 1248.68241
[21]	Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. 2017. The first parameterized algorithms and computational experiments challenge. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC’16), Vol. 63. 30:1-30:9.
[22]	Erik D. Demaine and MohammadTaghi Hajiaghayi. 2007. The bidimensionality theory and its algorithmic applications. Comput. J. 51, 3 (2007), 292-302. · Zbl 1283.68053
[23]	Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. 2009. Algorithmic graph minor theory: Improved grid minor bounds and Wagner’s contraction. Algorithmica 54, 2 (2009), 142-180. · Zbl 1184.05121
[24]	Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. 2005. Algorithmic graph minor theory: Decomposition, approximation, and coloring. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, (FOCS’05). 637-646.
[25]	Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. 2011. Contraction decomposition in H-minor-free graphs and algorithmic applications. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC’11). ACM, 441-450. · Zbl 1288.05256
[26]	Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar. 2010. Approximation algorithms via contraction decomposition. Combinatorica 30, 5 (2010), 533-552. · Zbl 1274.05445
[27]	Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, and Blair D. Sullivan. 2014. Structural sparsity of complex networks: Random graph models and linear algorithms. Retrieved from CoRR abs/1406.2587 (2014). arxiv:1406.2587 · Zbl 1425.05149
[28]	Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour, and Dirk Vertigan. 2004. Excluding any graph as a minor allows a low tree-width 2-coloring. J. Comb. Theory, Ser. B 91, 1 (2004), 25-41. · Zbl 1042.05036
[29]	Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. 2016. Kernelization and sparseness: The case of dominating set. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS’16). 31:1-31:14. · Zbl 1388.68110
[30]	Zdeněk Dvořák. 2013. Constant-factor approximation of the domination number in sparse graphs. Eur. J. Combin. 34, 5 (2013), 833-840. · Zbl 1260.05111
[31]	Zdeněk Dvořák. 2019. On distance r-dominating and 2r-independent sets in sparse graphs. Journal of Graph Theory 91, 2 (2019), 162-173. https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22426. · Zbl 1418.05100
[32]	Zdeněk Dvořák, Daniel Král’, and Robin Thomas. 2013. Testing first-order properties for subclasses of sparse graphs. J. ACM 60, 5 (2013), 36:1-36:24. · Zbl 1281.05114
[33]	Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. 2018. Lossy kernels for connected dominating set on sparse graphs. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS’18). LIPIcs, Vol. 96. 29:1-29:15. · Zbl 1487.68176
[34]	Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. 2017. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP’17). 63:1-63:14. · Zbl 1441.68176
[35]	Michelle Girvan and Mark E. J. Newman. 2002. Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99, 12 (2002), 7821-7826. · Zbl 1032.91716
[36]	Kwang-Il Goh, Michael E. Cusick, David Valle, Barton Childs, Marc Vidal, and Albert-László Barabási. 2007. The human disease network. Proc. Nat. Acad. Sci. 104, 21 (2007), 8685-8690.
[37]	Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. 2015. Colouring and covering nowhere dense graphs. In Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG’15), Vol. 9224. 325-338. · Zbl 1417.05067
[38]	Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. 2017. Deciding first-order properties of nowhere dense graphs. J. ACM 64, 3 (2017), 17:1-17:32. · Zbl 1426.68172
[39]	Paul W. Holland, Kathryn B. Laskey, and Samuel Leinhardt. 1983. Stochastic blockmodels: First steps. Soc. Netw. 5, 2 (1983), 109-137.
[40]	Wojciech Kazana and Luc Segoufin. 2013. Enumeration of first-order queries on classes of structures with bounded expansion. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’13). 297-308. · Zbl 1353.68068
[41]	Henry A. Kierstead and Daqing Yang. 2003. Orderings on graphs and game coloring number. Order 20 (2003), 255-264. · Zbl 1041.05029
[42]	Bryan Klimt and Yiming Yang. 2004. Introducing the Enron corpus. In Proceedings of the 1st Conference on Email and Anti-Spam (CEAS’04). · Zbl 1132.68562
[43]	Donald Ervin Knuth. 1993. The Stanford GraphBase: A Platform for Combinatorial Computing. Vol. 37. Addison-Wesley Reading. · Zbl 0806.68121
[44]	Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. 2016. The generalised colouring numbers on classes of bounded expansion. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS’16). · Zbl 1398.05089
[45]	Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. 2017. Polynomial kernels and wideness properties of nowhere dense graph classes. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA’17). 1533-1545. · Zbl 1410.05112
[46]	Jeremy Kun, Michael P. O’Brien, and Blair D. Sullivan. 2018. Treedepth bounds in linear colorings. In Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’18). 331-343. · Zbl 1519.05082
[47]	Jérôme Kunegis. 2013. KONECT—The Koblenz network collection. In Proceedings of the International Web Observatory Workshop. 1343-1350. Retrieved from http://konect.uni-koblenz.de.
[48]	Sebastian Lamm, Christian Schulz, Darren Strash, Robert Williger, and Huashuo Zhang. 2019. Exactly solving the maximum weight independent set problem on large real-world graphs. In Proceedings of the 21st Workshop on Algorithm Engineering and Experiments (ALENEX’19). 144-158. · Zbl 1430.68226
[49]	Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Signed networks in social media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 1361-1370.
[50]	Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: Densification laws, shrinking diameters and possible explanations. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. 177-187.
[51]	Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http://snap.stanford.edu/data.
[52]	Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. 2018. Reconfiguration on sparse graphs. J. Comput. Syst. Sci. 95 (2018), 122-131. · Zbl 1390.68351
[53]	David Lusseau, Karsten Schneider, Oliver J. Boisseau, Patti Haase, Elisabeth Slooten, and Steve M. Dawson. 2003. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54, 4 (2003), 396-405.
[54]	Wojciech Nadara. 2018. Experimental evaluation of kernelization algorithms to dominating set. Retrieved from CoRR abs/1811.07831 (2018). arxiv:1811.07831
[55]	Wojciech Nadara, Marcin Pilipczuk, Felix Reidl, Roman Rabinovich, and Sebastian Siebertz. 2018. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. Code repository. Retrieved from https://bitbucket.org/marcin_pilipczuk/wcol-uqw-experiments. · Zbl 1493.68398
[56]	Jaroslav Nešetřil and Patrice Ossona de Mendez. 2006. Tree-depth, subgraph coloring, and homomorphism bounds. Euro. J. Combin. 27 (2006), 1022-1041. · Zbl 1089.05025
[57]	Jaroslav Nešetřil and Patrice Ossona de Mendez. 2008. Grad and classes with bounded expansion I. Decompositions. Euro. J. Combin. 29, 3 (2008), 760-776. · Zbl 1156.05056
[58]	Jaroslav Nešetřil and Patrice Ossona de Mendez. 2008. Grad and classes with bounded expansion II. Algorithmic aspects. Euro. J. Combin. 29, 3 (2008), 777-791. · Zbl 1185.05131
[59]	Jaroslav Nešetřil and Patrice Ossona de Mendez. 2008. Grad and classes with bounded expansion III. Restricted graph homomorphism dualities. Euro. J. Combin. 29, 4 (2008), 1012-1024. · Zbl 1213.05240
[60]	Jaroslav Nešetřil and Patrice Ossona de Mendez. 2010. First order properties on nowhere dense structures. J. Symbol. Log. 75, 3 (2010), 868-887. · Zbl 1206.03033
[61]	Jaroslav Nešetřil and Patrice Ossona de Mendez. 2011. On nowhere dense graphs. Euro. J. Combin. 32, 4 (2011), 600-617. · Zbl 1226.05102
[62]	Jaroslav Nešetřil and Patrice Ossona de Mendez. 2012. Sparsity—Graphs, Structures, and Algorithms. Algorithms and Combinatorics, Vol. 28. Springer. · Zbl 1268.05002
[63]	Mark E. J. Newman. 2001. The structure of scientific collaboration networks. Proc. Nat. Acad. Sci. 98, 2 (2001), 404-409. · Zbl 1065.00518
[64]	Mark E. J. Newman. 2006. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 3 (2006), 036104.
[65]	Sampo Niskanen and Patric R. J. Östergård. 2003. Cliquer User’s Guide, Version 1.0. Communications Laboratory, Helsinki University of Technology, Espoo, Finland, Technical Report T48. Retrieved from https://users.aalto.fi/∼pat/cliquer.html.
[66]	Michael P. O’Brien and Blair D. Sullivan. 2017. Experimental evaluation of counting subgraph isomorphisms in classes of bounded expansion. Retrieved from CoRR abs/1712.06690 (2017). arxiv:1712.06690.
[67]	Tobias Oelschlägel. 2014. Treewidth from Treedepth. Bachelor’s thesis. RWTH Aachen University, Germany.
[68]	Michał Pilipczuk and Sebastian Siebertz. 2018. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. Retrieved from CoRR abs/1809.05675 (2018). arxiv:1809.05675. · Zbl 1506.05162
[69]	Michał Pilipczuk and Sebastian Siebertz. 2019. Polynomial bounds for centered colorings on proper minor-closed graph classes. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA’19). 1501-1520. · Zbl 1434.05056
[70]	Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. 2018. On the number of types in sparse graphs. In Proceedings of the 33rd ACM/IEEE Symposium on Logic in Computer Science (LICS 20’18). 799-808. · Zbl 1453.03031
[71]	Klaus-Peter Podewski and Martin Ziegler. 1978. Stable graphs. Fund. Math 100, 2 (1978), 101-107. · Zbl 0407.05072
[72]	Felix Reidl. 2016. Structural Sparseness and Complex Networks. Ph.D. Dissertation. RWTH Aachen University, Germany. Retrieved from http://publications.rwth-aachen.de/record/565064.
[73]	Felix Reidl, Fernando Sánchez Villaamil, and Konstantinos Stavropoulos. 2016. Characterising bounded expansion by neighbourhood complexity. Retrieved from CoRR abs/1603.09532 (2016). · Zbl 1400.05248
[74]	Matthew Richardson, Rakesh Agrawal, and Pedro Domingos. 2003. Trust management for the semantic web. In Proceedings of the International Semantic Web Conference. Springer, 351-368.
[75]	Matei Ripeanu, Ian Foster, and Adriana Iamnitchi. 2002. Mapping the Gnutella network. IEEE Internet Comput. 6, 1 (2002), 50-57. · Zbl 1014.68937
[76]	Neil Robertson and Paul D. Seymour. 1982-2010. Graph minors I-XXII. · Zbl 1239.05173
[77]	Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI’15). 4292-4293.
[78]	Fernando Sánchez Villaamil. 2017. About Treedepth and Related Notions. Dissertation. RWTH Aachen University, Aachen. Retrieved from http://publications.rwth-aachen.de/record/709271.
[79]	Sebastian Siebertz. 2018. Reconfiguration on nowhere dense graph classes. Electr. J. Comb. 25, 3 (2018), P3.24. · Zbl 1393.05171
[80]	Juliette Stehlé, N. Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, C. Régis, B. Lina, and P. Vanhems. 2011. High-resolution measurements of face-to-face contact patterns in a primary school. PLOS One 6, 8 (8 2011), e23176. · Zbl 1405.92255
[81]	Hisao Tamaki. 2017. Positive-instance driven dynamic programming for treewidth. In Proceedings of the 25th European Symposium on Algorithms (ESA’17), Vol. 87. 68:1-68:13. · Zbl 1442.90198
[82]	Jan van den Heuvel, Patrice Ossona de Mendez, Daniel A. Quiroz, Roman Rabinovich, and Sebastian Siebertz. 2017. On the generalised colouring numbers of graphs that exclude a fixed minor. Euro. J. Combin. 66 (2017), 129-144. · Zbl 1369.05089
[83]	Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of “small-world” networks. Nature 393, 6684 (1998), 440. · Zbl 1368.05139
[84]	John G. White, Eileen Southgate, J. Nichol Thomson, and Sydney Brenner. 1986. The structure of the nervous system of the nematode Caenorhabditis elegans: The mind of a worm. Phil. Trans. R. Soc. Lond 314 (1986), 1-340.
[85]	Wayne W. Zachary. 1977. An information flow model for conflict and fission in small groups. J. Anthrop. Res. 33, 4 (1977), 452-473.
[86]	Xuding Zhu. 2009. Colouring graphs with bounded generalized colouring number. Discrete Math. 309 (2009), 5562-5568. · Zbl 1216.05043

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.