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 open medium confidence

The source paper (arXiv:1407.5833, published SIAM Journal on Discrete Mathematics 29(4):2047–2064, 2015) proves both halves of the size dichotomy: infinite VC-dimension forces a logarithmic lower bound and log-APX-hardness, while finite VC-dimension forces a polynomial lower bound. The conjectured complementary algorithmic half — that finite VC-dimension also entails constant-factor approximability of Min Identifying Code — remains open; four targeted web searches found no follow-up paper proving or disproving this claim as of May 2026.

Reviewer notes. No follow-up paper was found that resolves the conjectured constant-factor approximability of Min Identifying Code in finite VC-dimension hereditary classes. The paper itself (confirmed via WebFetch of the arXiv abstract page) notes that C₄-free bipartite graphs (finite VC-dimension) exhibit non-trivial intermediate behavior, illustrating the difficulty of the algorithmic half of the dichotomy. The conjecture is at least 9 years old; absence of a resolution in indexed literature suggests it is a hard open problem. Confidence is medium rather than high because the paper is old enough that a resolution in a journal paper not prominently indexed on arXiv could have been missed.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

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