Generating irreducible copositive matrices using the stable set problem

Peter J.C. Dickinson*, Reinier de Zeeuw

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.
Original languageEnglish
JournalDiscrete applied mathematics
Early online date5 May 2020
DOIs
Publication statusE-pub ahead of print/First online - 5 May 2020

Keywords

  • α-Critical
  • Copositive
  • Extreme
  • Irreducible
  • Stability number

Fingerprint Dive into the research topics of 'Generating irreducible copositive matrices using the stable set problem'. Together they form a unique fingerprint.

Cite this