×

Exploring the role of graph spectra in graph coloring algorithm performance. (English) Zbl 1298.05208

Summary: This paper considers the challenge of recognizing how the properties of a graph determine the performance of graph coloring algorithms. In particular, we examine how spectral properties of the graph make the graph coloring task easy or hard. We address the question of when an exact algorithm is likely to provide a solution in a reasonable computation time, when we are better off using a quick heuristic, and how the properties of the graph influence algorithm performance. A new methodology is introduced to visualize a collection of graphs in an instance space defined by their properties, with an optimal feature selection approach included to ensure that the instance space preserves the topology of an algorithm performance metric. In this instance space we can reveal how different algorithms perform across a variety of instance classes with various properties. We demonstrate the methodology using a sophisticated branch and bound exact algorithm, and the faster heuristic approaches of integer rounding of a linear programming relaxation of the graph coloring formulation, as well as a greedy degree-saturation heuristic. Our results demonstrate that spectral properties of the graph instances can provide useful descriptions of when each of these algorithms will provide the best solution for a given computational effort.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achlioptas, D.; Naor, A.; Peres, Y., Rigorous location of phase transitions in hard optimization problems, Nature, 435, 7043, 759-764 (2005)
[2] Ali, S.; Smith, K., On learning algorithm selection for classification, Appl. Soft Comput. J., 6, 2, 119-138 (2006)
[3] Angel, E.; Zissimopoulos, V., On the classification of NP-complete problems in terms of their correlation coefficient, Discrete Appl. Math., 99, 1-3, 261-277 (2000) · Zbl 0987.90092
[4] Balakrishnan, R., The energy of a graph, Linear Algebra Appl., 387, 287-295 (2004) · Zbl 1041.05046
[5] Battiti, R., Using mutual information for selecting features in supervised neural net learning, IEEE Trans. Neural Netw., 5, 4, 537-550 (1994)
[7] Bengio, Y.; Chapados, N., Extensions to metric based model selection, J. Mach. Learn. Res., 3, 1209-1227 (2003) · Zbl 1102.68529
[8] Biggs, N., Algebraic Graph Theory, Vol. 67 (1993), Cambridge Univ. Pr.
[9] Blöchliger, I.; Zufferey, N., A graph coloring heuristic using partial solutions and a reactive tabu scheme, Comput. Oper. Res., 35, 3, 960-975 (2008) · Zbl 1278.90327
[10] Brazdil, P.; Soares, C.; Da Costa, J., Ranking learning algorithms: using IBL and meta-learning on accuracy and time results, Mach. Learn., 50, 3, 251-277 (2003) · Zbl 1033.68082
[11] Brélaz, D., New methods to color the vertices of a graph, Commun. ACM, 22, 4, 251-256 (1979) · Zbl 0394.05022
[12] Brinkmann, G.; Coolsaet, K.; Goedgebeur, J.; Melot, H., House of graphs: a database of interesting graphs, Discrete Appl. Math., 161, 1-2, 311-314 (2013) · Zbl 1292.05254
[13] Burke, E.; McCollum, B.; Meisels, A.; Petrovic, S.; Qu, R., A graph-based hyper-heuristic for educational timetabling problems, European J. Oper. Res., 176, 1, 177-192 (2007) · Zbl 1137.90602
[16] Corne, D.; Reynolds, A., Optimisation and generalisation: footprints in instance space, (Parallel Problem Solving from Nature—PPSN XI. Parallel Problem Solving from Nature—PPSN XI, LNCS, vol. 6238 (2010)), 22-31
[17] Culberson, J., On the futility of blind search: an algorithmic view of ‘no free lunch’, Evol. Comput., 6, 2, 109-127 (1998)
[19] de Werra, D., An introduction to timetabling, European J. Oper. Res., 19, 2, 151-162 (1985) · Zbl 0553.90059
[20] Fleurent, C.; Ferland, J., Genetic and hybrid algorithms for graph coloring, Ann. Oper. Res., 63, 3, 437-461 (1996) · Zbl 0851.90095
[21] Galinier, P.; Hao, J., Hybrid evolutionary algorithms for graph coloring, J. Comb. Optim., 3, 4, 379-397 (1999) · Zbl 0958.90071
[22] Galinier, P.; Hertz, A., A survey of local search methods for graph coloring, Comput. Oper. Res., 33, 9, 2547-2562 (2006) · Zbl 1086.90060
[23] Gent, I.; Walsh, T., The TSP phase transition, Artif. Intell., 88, 1-2, 349-358 (1996) · Zbl 0907.68177
[24] Gualandi, S.; Malucelli, F., A simple branching scheme for vertex coloring problems, Discrete Appl. Math., 160, 1-2, 192-196 (2012) · Zbl 1237.05075
[25] Guyon, I.; Elisseeff, A., An introduction to variable and feature selection, J. Mach. Learn. Res., 3, 1157-1182 (2003) · Zbl 1102.68556
[26] Hamiez, J.; Hao, J., Scatter search for graph coloring, (Artificial Evolution (2002), Springer), 195-213
[27] Hansen, P.; Labbé, M.; Schindl, D., Set covering and packing formulations of graph coloring: algorithms and first polyhedral results, Discrete Optim., 6, 2, 135-147 (2009) · Zbl 1279.90115
[28] Hartmann, A.; Weigt, M., Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics (2005), VCH Verlagsgesellschaft mbH · Zbl 1094.82002
[29] Hertz, A.; Werra, D., Using tabu search techniques for graph coloring, Computing, 39, 4, 345-351 (1987) · Zbl 0626.68051
[30] Hill, R.; Reilly, C., The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance, Manag. Sci., 302-317 (2000) · Zbl 1231.90323
[31] Hooker, J., Needed: an empirical science of algorithms, Oper. Res., 201-212 (1994) · Zbl 0805.90119
[32] Houstis, E.; Catlin, A.; Dhanjani, N.; Rice, J.; Ramakrishnan, N.; Verykios, V., MyPYTHIA: a recommendation portal for scientific software and services, Concurr. Comput.: Pract. Exp., 14, 13-15, 1481-1505 (2002) · Zbl 1007.68617
[33] Houstis, E.; Catlin, A.; Rice, J.; Verykios, V.; Ramakrishnan, N.; Houstis, C., PYTHIA-II: a knowledge/database system for managing performance data and recommending scientific software, ACM Trans. Math. Softw. (TOMS), 26, 2, 227-253 (2000) · Zbl 1063.68664
[34] Johnson, D.; Aragon, C.; McGeoch, L.; Schevon, C., Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning, Oper. Res., 378-406 (1991) · Zbl 0739.90055
[35] Jolliffe, I., Principal Component Analysis (2002), Springer · Zbl 1011.62064
[36] Leyton-Brown, K.; Nudelman, E.; Andrew, G.; McFadden, J.; Shoham, Y., A portfolio approach to algorithm selection, (International Joint Conference on Artificial Intelligence, vol. 18 (2003)), 1542-1543
[37] Leyton-Brown, K.; Nudelman, E.; Shoham, Y., Learning the empirical hardness of optimization problems: the case of combinatorial auctions, Lecture Notes in Comput. Sci., 2470, 556-572 (2002)
[38] Macready, W.; Wolpert, D., What makes an optimization problem hard, Complexity, 5, 40-46 (1996) · Zbl 1455.90156
[39] Mehrotra, A.; Trick, M., A column generation approach for graph coloring, INFORMS J. Comput., 8, 4, 344-354 (1996) · Zbl 0884.90144
[40] Mélot, H., Facet defining inequalities among graph invariants: the system graphedron, Discrete Appl. Math., 156, 10, 1875-1891 (2008) · Zbl 1152.05380
[42] Mohar, B., The Laplacian spectrum of graphs, Graph Theory Combin. Appl., 2, 871-898 (1991) · Zbl 0840.05059
[44] Östergård, P., A fast algorithm for the maximum clique problem, Discrete Appl. Math., 120, 1, 197-207 (2002) · Zbl 1019.05054
[45] Pardalos, P.; Mavridou, T.; Xue, J., The Graph Coloring Problem: A Bibliographic Survey (1998), Kluwer Academic Publishers · Zbl 0944.05050
[46] Prudêncio, R.; Ludermir, T., Meta-learning approaches to selecting time series models, Neurocomputing, 61, 121-137 (2004)
[47] Ramakrishnan, N.; Rice, J.; Houstis, E., GAUSS: an online algorithm selection system for numerical quadrature, Adv. Eng. Softw., 33, 1, 27-36 (2002) · Zbl 1003.68581
[48] Read, R.; Wilson, R., An Atlas of Graphs (1998), Oxford University Press: Oxford University Press USA · Zbl 0908.05001
[49] Rice, J., The algorithm selection problem, Adv. Comput., 15, 65-117 (1976)
[51] Smith-Miles, K., Cross-disciplinary perspectives on meta-learning for algorithm selection, ACM Comput. Surv., 41, 1 (2008)
[52] Smith-Miles, K.; James, R.; Giffin, J.; Tu, Y., A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance, (Learning and Intelligent Optimization (2009)), 89-103
[53] Smith-Miles, K.; Lopes, L., Generalising algorithm performance in instance space: a timetabling case study, Lecture Notes in Comput. Sci., 6683, 524-539 (2011)
[54] Smith-Miles, K.; Lopes, L., Measuring instance difficulty for combinatorial optimization problems, Comput. Oper. Res., 39, 5, 875-889 (2012) · Zbl 1251.90339
[55] Smith-Miles, K.; Tan, T., Measuring algorithm footprints in instance space, (IEEE Congress on Evolutionary Computation (CEC) (2012), IEEE), 1-8
[56] Smith-Miles, K.; van Hemert, J., Discovering the suitability of optimisation algorithms by learning from evolved instances, Ann. Math. Artif. Intell., 61, 2, 87-104 (2011) · Zbl 1236.49008
[57] Smith-Miles, K.; Wreford, B.; Lopes, L.; Insani, N., Predicting metaheuristic performance on graph coloring problems using data mining, (Talbi, E. G., Hybrid Metaheuristics (2013), Springer), 417-432
[58] Soffer, S.; Vázquez, A., Network clustering coefficient without degree-correlation biases, Phys. Rev. E, 71, 5, 057101 (2005)
[59] Torkkola, K., Feature extraction by non parametric mutual information maximization, J. Mach. Learn. Res., 3, 1415-1438 (2003) · Zbl 1102.68638
[61] Verykios, V.; Houstis, E.; Rice, J., A knowledge discovery methodology for the performance evaluation of scientific software, Neural Parallel Sci. Comput. (2002)
[62] Vilalta, R.; Drissi, Y., A perspective view and survey of meta-learning, Artif. Intell. Rev., 18, 2, 77-95 (2002)
[63] Wang, X.; Smith-Miles, K.; Hyndman, R., Rule induction for forecasting method selection: meta-learning the characteristics of univariate time series, Neurocomputing, 72, 10, 2581-2594 (2009)
[64] Wolpert, D. H.; Macready, W. G., No free lunch theorems for optimization, IEEE Trans. Evol. Comput., 1, 1, 67-82 (1997)
[65] Wood, D., An algorithm for finding a maximum clique in a graph, Oper. Res. Lett., 21, 5, 211-217 (1997) · Zbl 0908.90264
[66] Xu, L.; Hutter, F.; Hoos, H.; Leyton-Brown, K., SATzilla-07: the design and analysis of an algorithm portfolio for SAT, Lecture Notes in Comput. Sci., 4741, 712 (2007)
[67] Xu, L.; Hutter, F.; Hoos, H.; Leyton-Brown, K., Satzilla: portfolio-based algorithm selection for sat, J. Artificial Intelligence Res., 32, 1, 565-606 (2008) · Zbl 1182.68272
[68] Zanakis, S.; Evans, J., Heuristic ‘optimization’: why, when, and how to use it, Interfaces, 11, 5, 84-91 (1981)
[69] Zykov, A., On Some Properties of Linear Complexes, Vol. 79 (1952), American Mathematical Society
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.