New results for recognizing convex-QP adverse graphs

ABSTRACT

A graph G with convex-QP stability number (or simply a convex-QP graph) is a graph for which the stability number is equal to the optimal value of a convex quadratic programme, say $P\left(G\right)$. The problem of recognizing in polynomial time whether or not a given graph is a convex-QP graph has resisted to be completely solved. In this paper, some progress recently made for trying to settle this open question is reported. Namely, if G is a graph such that the optimal solutions of $P\left(G\right)$ are critical points of the objective function, some new necessary and sufficient conditions for G to be a convex-QP graph are proved. The practical value of two of these results is also exemplified.

KEYWORDS:

• Convex quadratic programming in graphs
• maximum stable set
• combinatorial optimization
• graph theory

AMS SUBJECT CLASSIFICATIONS:

• 90C35
• 90C20
• 05C69
• 90C27
• 68R10

Acknowledgements

The author thanks the referees for their pleasant comments. In addition, he is also grateful to one of the referees for the valuable suggestions which improved the paper.

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Funding

This research was supported by the Portuguese Foundation for Science and Technology (‘FCT-Fundação para a Ciência e a Tecnologia’), through the CIDMA – Center for Research and Development in Mathematics and Applications, within project UID/MAT/04106/2013.