Graph-theory open problems

VC-dimension dichotomy for identifying codes approximation

VC-Dimension Dichotomy for Identifying Codes (Approximation) · arXiv:1407.5833

arXiv Informal medium confidence— first stated 2017-04-14
Authors: Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, Stéphan Thomassé

Status disproved high confidence

The intended finite-VC-dimension implication is already refuted by the hereditary class of C4-free bipartite graphs in Theorem 4.3 of the cited source.

Cited literature (1)

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The inapproximability is conditional on the theorem's standard complexity assumption, and the extracted phrase 'logarithmic lower bound' is formally imprecise.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

Informal. For any hereditary class of graphs $\mathcal{C}$, either (1) the minimum identifying code size has a logarithmic lower bound and Min Id Code is log-APX-hard in $\mathcal{C}$, or (2) the minimum identifying code size has a polynomial lower bound and Min Id Code admits a constant factor approximation algorithm in $\mathcal{C}$.

Context

Surveying known results in Table 1, the authors observe that hereditary graph classes appear to split into two regimes according to their VC-dimension: infinite VC-dimension corresponds to a logarithmic lower bound and log-APX-hardness, while finite VC-dimension corresponds to a polynomial lower bound and (conjecturally) constant-factor approximability. The paper aims to shed light on the validity of this dichotomy for all hereditary classes.

Notes. The lower-bound half of the dichotomy is fully proved as Theorem 2.2. The approximation half is shown to fail in general: C4-free bipartite graphs have finite VC-dimension but Min Id Code cannot be approximated within a factor of c log|V| for some c > 0 (Thm 4.3). The question of which finite VC-dimension classes admit constant-factor approximations remains open (Table 2 lists Girth ≥ 5, Chordal bipartite, Unit disk, and Undirected path graphs as open). PDF source — math notation may be garbled; full paper text is truncated so later explicit problem statements may be missing.

Source paper

Identifying codes in hereditary classes of graphs and VC-dimension
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, Stéphan Thomassé · 2017-04-14
https://arxiv.org/abs/1407.5833 PDF source