zbMATH — the first resource for mathematics

Generating irreducible copositive matrices using the stable set problem. (English) Zbl 1462.05218
Summary: In this paper it is considered how graphs can be used to generate copositive matrices, and necessary and sufficient conditions are given for these generated matrices to then be irreducible with respect to the set of positive semidefinite plus nonnegative matrices. This is done through combining the well known copositive formulation of the stable set problem with recent results on necessary and sufficient conditions for a copositive matrix to be irreducible. By applying this result, tens of thousands of new irreducible copositive matrices of order less than or equal to thirteen were found. These matrices were then tested for being extreme copositive matrices, and it was found that in all but three cases this was indeed the case. It is also demonstrated in this paper that these matrices provide difficult instances to test approximations of the copositive cone against.
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
15B48 Positive matrices and their generalizations; cones of matrices
Full Text: DOI
[1] Afonin, Andrey; Hildebrand, Roland; Dickinson, Peter J. C., The extreme rays of the \(6 \times 6\) copositive cone (2019), preprint
[2] Baumert, Leonard D., Extreme copositive quadratic forms, Pacific J. Math., 19, 197-204 (1966) · Zbl 0145.25501
[3] Baumert, Leonard D., Extreme copositive quadratic forms, II, Pacific J. Math., 20, 1-20 (1967) · Zbl 0189.32904
[4] Bomze, Immanuel M., On standard quadratic optimization problems, J. Global Optim., 13, 4, 369-387 (1998) · Zbl 0916.90214
[5] Bomze, Immanuel M.; Budinich, Marco; Pardalos, Panos M.; Pelillo, Marcello, The maximum clique problem, (Du, Ding-Zhu; Pardalos, Panos M., Handbook of Combinatorial Optimization: Supplement Vol. a (1999), Springer US), 1-74 · Zbl 1253.90188
[6] Bomze, Immanuel M.; Dür, Mirjam; de Klerk, Etienne; Roos, Cornelis; Quist, Arie J.; Terlaky, Tamàs, On copositive programming and standard quadratic optimization problems, J. Global Optim., 18, 301-320 (2000) · Zbl 0970.90057
[7] Bomze, Immanuel M.; Schachinger, Werner; Uchida, Gabriele, Think co(mpletely )positive! Matrix properties, examples and a clustered bibliography on copositive optimization, J. Global Optim., 52, 3, 423-445 (2012) · Zbl 1268.90051
[8] Bondy, John Adrian; Murty, U. S.R., Graph theory with applications (1976), The Macmillan Press Ltd. · Zbl 1226.05083
[9] Bull, James J.; Pease, Craig M., Combinatorics and variety of mating-type systems, Evolution, 43, 3, 667-671 (1988)
[10] Campêlo, Manoel; Corrêa, Ricardo C.; Moura, Phablo F. S.; Santos, Marcio C., On optimal k-fold colorings of webs and antiwebs, Discrete Appl. Math., 161, 1, 60-70 (2013) · Zbl 1296.05068
[11] Cheng, Eddie; de Vries, Sven, Antiweb-wheel inequalities and their separation problems over the stable set polytopes, Math. Program., 92, 1, 153-175 (2002) · Zbl 1154.90604
[12] Diananda, Palahenedi H., On nonnegative forms in real variables some or all of which are nonnegative, Math. Proc. Camb. Phil. Soc., 58, 17-25 (1962) · Zbl 0108.04803
[13] Dickinson, Peter J. C., Geometry of the copositive and completely positive cones, J. Math. Anal. Appl., 380, 377-395 (2011) · Zbl 1229.90195
[14] Dickinson, Peter J. C., The Copositive Cone, the Completely Positive Cone and their Generalisations (2013), University of Groningen, (Ph.D. thesis)
[15] Dickinson, Peter J. C.; Dür, Mirjam; Gijben, Luuk; Hildebrand, Roland, Irreducible elements of the copositive cone, Linear Algebra Appl., 439, 6, 1605-1626 (2013) · Zbl 1305.15074
[16] Dickinson, Peter J. C.; Hildebrand, Roland, Considering copositivity locally, J. Math. Anal. Appl., 437, 2, 1184-1195 (2016) · Zbl 1382.15048
[17] Dong, Hongbo; Anstreicher, Kurt, Separating doubly nonnegative and completely positive matrices, Math. Program., 137, 1-2, 131-153 (2013) · Zbl 1263.90064
[18] Dür, Mirjam, Copositive programming - a survey, (Diehl, Moritz; Glineur, Francois; Jarlebring, Elias; Michiels, Wim, Recent Advances in Optimization and Its Applications in Engineering (2010), Springer Berlin Heidelberg), 3-20
[19] Eaton, John W.; Bateman, David; Hauberg, Søren; Wehbring, Rik, GNU Octave version 4.2.2 manual: a high-level interactive language for numerical computations (2018)
[20] Erdös, Paul; Gallai, Tibor, On the minimal number of vertices representing the edges of a graph, Publ. Math. Inst. Hungar. Acad. Sci, 6, 18, 1-203 (1961) · Zbl 0101.41001
[21] Gessel, Ira M.; Li, Ji, Enumeration of point-determining graphs, J. Combin. Theory Ser. A, 118, 2, 591-612 (2011) · Zbl 1238.05136
[22] Grötschel, Martin; Lovász, László; Schrijver, Alexander, Geometric Algorithms and Combinatorial Optimization (1988), Springer-Verlag: Springer-Verlag Berlin · Zbl 0634.05001
[23] Hall, Marshall; Newman, Morris, Copositive and completely positive quadratic forms, Math. Proc. Camb. Phil. Soc., 59, 329-339 (1963) · Zbl 0124.25302
[24] Hildebrand, Roland, The extreme rays of the \(5 \times 5\) copositive cone, Linear Algebra Appl., 437, 7, 1538-1547 (2012) · Zbl 1259.15045
[25] Hildebrand, Roland, Minimal zeros of copositive matrices, Linear Algebra Appl., 459, 154-174 (2014) · Zbl 1309.15050
[26] Hiriart-Urruty, Jean-Baptiste; Seeger, Alberto, A variational approach to copositive matrices, SIAM Rev., 52, 4, 593-629 (2010) · Zbl 1207.15037
[27] Hoffman, Alan J.; Pereira, Francisco, On copositive matrices with -1,0,1 entries, J. Combin. Theory, 14, 3, 302-309 (1973) · Zbl 0273.15019
[28] Hohenwarter, Markus, GeoGebra: Ein Softwaresystem für dynamische Geometrie und Algebra der Ebene (2002), Paris Lodron University: Paris Lodron University Salzburg, Austria, (Master’s thesis)
[29] Kilibarda, Goran, Enumeration of unlabelled mating graphs, Graphs Combin., 23, 2, 183-199 (2007) · Zbl 1116.05038
[30] de Klerk, Etienne; Pasechnik, Dmitrii V., Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, 4, 875-892 (2002) · Zbl 1035.90058
[31] Lofberg, Johan, YALMIP: A Toolbox for Modeling and Optimization in MATLAB, 284-289 (2004), IEEE
[32] Lovasz, László, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021
[33] MATLAB, version 9.4 (R2018a) (2018), The MathWorks Inc.: The MathWorks Inc. Natick, Massachusetts
[34] Brendan D. McKay, Combinatorial data. http://users.cecs.anu.edu.au/ bdm/data/graphs.html. · Zbl 0663.00002
[35] McKay, Brendan D., Practical graph isomorphism, Congr. Numer., 30, 45-87 (1981) · Zbl 0521.05061
[36] Brendan D. McKay, Adolfo Piperno, Nauty traces. http://pallini.di.uniroma1.it.
[37] McKay, Brendan D.; Piperno, Adolfo, Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112 (2014) · Zbl 1394.05079
[38] Motzkin, Theodore S.; Straus, Ernst G., Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., 17, 533-540 (1965) · Zbl 0129.39902
[39] Palubeckis, Gintaras, Facet-inducing web and antiweb inequalities for the graph coloring polytope, Discrete Appl. Math., 158, 18, 2075-2080 (2010) · Zbl 1215.05073
[40] Peña, Javier F.; Vera, Juan C.; Zuluaga, Luis F., Computing the stability number of a graph via linear and semidefinite programming, SIAM J. Optim., 18, 1, 87-105 (2007) · Zbl 1176.90611
[41] Plummer, Michael D., On a family of line-critical graphs, Monatsh. Math., 71, 1, 40-48 (1967) · Zbl 0166.19903
[42] Read, Ronald Cedric, The Enumeration of Mating-Type Graphs (1989), Faculty of Mathematics, University of Waterloo
[43] Sewell, Edward C.; Trotter, Leslie E., Stability critical graphs and even subdivisions of K4, J. Combin. Theory Ser. B, 59, 1, 74-84 (1993) · Zbl 0793.05133
[44] Small, Benjamin Luke, On Alpha-Critical Graphs and Their Construction (2015), Washington State University, (Ph.D. thesis)
[45] Sumner, David P., Point determination in graphs, Discrete Math., 5, 2, 179-187 (1973) · Zbl 0265.05124
[46] The Sage Developers, Sagemath, the sage mathematics software system (version 8.2) (2018)
[47] Toh, Kim-Chuan; Todd, Michael J.; Tütüncü, Reha H., On the implementation and usage of sdpt3 - a matlab software package for semidefinite-quadratic-linear programming, version 4.0, (Anjos, Miguel F.; Lasserre, Jean B., Handbook on Semidefinite, Conic and Polynomial Optimization. Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science (2012), Springer US), 715-754 · Zbl 1334.90117
[48] Trotter, Leslie E., A class of facet producing graphs for vertex packing polyhedra, Discrete Math., 12, 4, 373-388 (1975) · Zbl 0314.05111
[49] Wessel, Walter, On the problem of determining whether a given graph is edge critical or not, (Erdös, Paul; Rényi, Alfréd; Sós, Vera T., Combinatorial Theory and Its Applications, Vol. III. Combinatorial Theory and Its Applications, Vol. III, Colloquia Mathematica Societatis János Bolyai, vol. 4 (1970)), 1123-1139
[50] Wolfram Research, Inc., Mathematica, version 11.3 (2018), Champaign, IL
[51] de Zeeuw, Reinier, Which Graphs Produce Irreducible Copositive Matrices? (2018), University of Twente, (Bachelor thesis)
[52] Zykov, Alexander Aleksandrovich, On some properties of linear complexes, Mat. Sb., 66, 2, 163-188 (1949)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.