A note on the maximum clique LP relaxation

Operations Research Letters 2026 Open access

Read full text
Authors: Pavel Aleksandrovich Zakharov
DOI: 10.1016/j.orl.2026.107425
Cited by: 0
References: 3

Abstract

We study the well-known linear programming relaxation of the maximum clique problem, whose optimal value is known as the fractional clique number . We show that this relaxation exhibits a large integrality gap: there exist graphs on n vertices for which the fractional clique number exceeds the actual clique number by a factor of Θ( n /log 2 n ).

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Advanced Optimization Algorithms Research

Publication details

Journal / source
Operations Research Letters
Volume
66
Pages
107425–107425
Publication date
13 February 2026
Language
EN