Generating irreducible copositive matrices using the stable set problem

Peter J.C. Dickinson; Reinier de Zeeuw

doi:10.1016/j.dam.2020.04.013

Generating irreducible copositive matrices using the stable set problem

Peter J.C. Dickinson^*, Reinier de Zeeuw

^*Corresponding author for this work

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

4 Citations (Scopus)

101 Downloads (Pure)

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 language	English
Pages (from-to)	103-117
Number of pages	15
Journal	Discrete applied mathematics
Volume	296
Early online date	5 May 2020
DOIs	https://doi.org/10.1016/j.dam.2020.04.013
Publication status	Published - 15 Jun 2021

Keywords

α-Critical
Copositive
Extreme
Irreducible
Stability number

Access to Document

10.1016/j.dam.2020.04.013

Dickinson2020generatingProof, 1.03 MBLicence: CC BY-NC-ND

Cite this

@article{94d3d29e1658427182fa3c3ab0edf10d,

title = "Generating irreducible copositive matrices using the stable set problem",

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.",

keywords = "α-Critical, Copositive, Extreme, Irreducible, Stability number",

author = "Dickinson, {Peter J.C.} and {de Zeeuw}, Reinier",

note = "Funding Information: The authors wish to thank the anonymous referees for their valuable comments on this paper. The authors also wish to thank Ben Small for providing a file of all -critical graphs with up to 13 vertices, without which the results of Section 6 would not have been possible. The first author would like to gratefully acknowledge support from the Netherlands Organisation for Scientific Research (NWO) through Grant No. 613.009.021 . The first author would also like to thank the organisers of the Oberwolfach workshop on Copositivity and Complete Positivity, as conversations during this workshop provided some of the initial inspiration for this paper. Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2021",

month = jun,

day = "15",

doi = "10.1016/j.dam.2020.04.013",

language = "English",

volume = "296",

pages = "103--117",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Generating irreducible copositive matrices using the stable set problem

AU - Dickinson, Peter J.C.

AU - de Zeeuw, Reinier

N1 - Funding Information: The authors wish to thank the anonymous referees for their valuable comments on this paper. The authors also wish to thank Ben Small for providing a file of all -critical graphs with up to 13 vertices, without which the results of Section 6 would not have been possible. The first author would like to gratefully acknowledge support from the Netherlands Organisation for Scientific Research (NWO) through Grant No. 613.009.021 . The first author would also like to thank the organisers of the Oberwolfach workshop on Copositivity and Complete Positivity, as conversations during this workshop provided some of the initial inspiration for this paper. Publisher Copyright: © 2020 Elsevier B.V.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - 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.

AB - 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.

KW - α-Critical

KW - Copositive

KW - Extreme

KW - Irreducible

KW - Stability number

UR - http://www.scopus.com/inward/record.url?scp=85089136372&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.04.013

DO - 10.1016/j.dam.2020.04.013

M3 - Article

SN - 0166-218X

VL - 296

SP - 103

EP - 117

JO - Discrete applied mathematics

JF - Discrete applied mathematics

ER -

Generating irreducible copositive matrices using the stable set problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this