Integrality Gap of the Vertex Cover Linear Programming Relaxation
Pith reviewed 2026-05-24 15:51 UTC · model grok-4.3
The pith
The integrality gap of the vertex cover LP relaxation on any graph G equals exactly 2 minus 2 over the fractional chromatic number of G.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The integrality gap of the standard linear programming relaxation for the vertex cover problem on any graph G equals (2 - 2/χ^f(G)), where χ^f(G) denotes the fractional chromatic number of G.
What carries the argument
The standard fractional vertex cover LP (minimize sum x_v subject to x_u + x_v >= 1 for every edge and 0 <= x_v <= 1) whose optimum value is related to the minimum fractional coloring measure.
If this is right
- On every bipartite graph the gap equals 1, recovering that the LP is always integral.
- On every graph the gap is strictly less than 2 and approaches 2 only in the limit as fractional chromatic number grows.
- The gap on any concrete graph can be computed exactly once its fractional chromatic number is known.
- Previous integrality-gap examples for specific graph families are recovered as special cases of the single formula.
Where Pith is reading between the lines
- Computing or approximating the vertex-cover integrality gap on a given graph is equivalent in difficulty to computing or approximating its fractional chromatic number.
- The result links the vertex-cover LP directly to the dual of the fractional coloring LP.
- Any new upper or lower bound on fractional chromatic number for a graph class immediately yields a matching bound on the vertex-cover gap for that class.
Load-bearing premise
The integrality gap is defined using the ordinary edge-covering LP and the ordinary definition of fractional chromatic number.
What would settle it
Take any graph whose fractional chromatic number is already known exactly (for example C_5) and compare the measured ratio of integer vertex cover size to LP value against the formula 2 - 2/χ^f(G).
read the original abstract
We give a characterization result for the integrality gap of the natural linear programming relaxation for the vertex cover problem. We show that integrality gap of the standard linear programming relaxation for any graph G equals $\left(2-\frac{2}{\chi^f(G)}\right)$ where $\chi^f(G)$ denotes the fractional chromatic number of G.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to characterize the integrality gap of the standard LP relaxation for vertex cover: for any graph G, the gap equals exactly 2 - 2/χ^f(G), where χ^f(G) denotes the fractional chromatic number of G.
Significance. A correct characterization linking the vertex-cover integrality gap to fractional chromatic number would be a notable structural result in approximation algorithms and graph theory. The claimed equality, however, is false.
major comments (1)
- [Abstract] Abstract (and the central claim): the asserted equality does not hold for every G. Consider the graph formed by K3 on vertices {a,b,c} with an additional pendant edge a–d. The LP optimum is 2 (e.g., x_a = x_b = x_c = x_d = 0.5 satisfies all edge constraints and the triangle inequalities force sum ≥ 2). An integer optimum is also 2 (e.g., {a,b}). Thus the gap is exactly 1. Since the graph contains a triangle, χ^f(G) = 3, so 2 − 2/3 = 4/3 ≠ 1.
Simulated Author's Rebuttal
We thank the referee for the detailed report and for identifying the flaw in our central claim. We agree that the asserted equality does not hold for every graph and will revise the manuscript to remove the incorrect characterization.
read point-by-point responses
-
Referee: [Abstract] Abstract (and the central claim): the asserted equality does not hold for every G. Consider the graph formed by K3 on vertices {a,b,c} with an additional pendant edge a–d. The LP optimum is 2 (e.g., x_a = x_b = x_c = x_d = 0.5 satisfies all edge constraints and the triangle inequalities force sum ≥ 2). An integer optimum is also 2 (e.g., {a,b}). Thus the gap is exactly 1. Since the graph contains a triangle, χ^f(G) = 3, so 2 − 2/3 = 4/3 ≠ 1.
Authors: We appreciate the referee's counterexample. Upon verification, the LP value for the described graph is 2 (as shown by the triangle lower bound of 1.5 combined with the pendant edge constraint), the integer optimum is 2, and the gap is 1. The fractional chromatic number is 3, so the formula yields 4/3, which does not match. The claimed equality therefore does not hold in general. We will revise the manuscript to withdraw this characterization. revision: yes
Circularity Check
No circularity: equality claimed to independent external parameter χ^f(G)
full rationale
The paper states that the integrality gap equals 2−2/χ^f(G) where χ^f(G) is the standard fractional chromatic number, an independently defined graph invariant with its own literature and definition outside this work. The abstract and description contain no self-definitional loops, no fitted parameters renamed as predictions, and no load-bearing self-citations that reduce the central claim to its own inputs by construction. The derivation is therefore presented as relating two separately defined quantities; any error in the claimed equality (such as the provided counterexample) would be a correctness issue rather than circularity.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The natural LP relaxation for vertex cover uses variables x_v in [0,1] for each vertex with sum x_u + x_v >=1 for every edge.
- domain assumption Fractional chromatic number χ^f(G) is defined in the usual way as the minimum total weight of a fractional coloring.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.