Alon–Shikhelman conjecture
For every integer and every graph family such that for every , define to be the maximum number of copies of in an -free subgraph of . The conjecture asserts that computing is NP-hard. Moreover, for every fixed , it is NP-hard to approximate within additive error on -vertex input graphs.
References
- NP-Hardness of Generalized-Turán Graph Modification Problems — arXiv — Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
Source: arXiv
Progress summary
A new preprint reports the conjecture for every finite forbidden family, while the broader case of possibly infinite families remains open.
The Alon–Shikhelman conjecture predicts a computational hardness threshold for generalized Turán problems. The newly reported result extends the conjectured statement beyond the previously established special case.
Known results
- The earlier work gives additive approximation algorithms and hardness-motivated conjectures for finite forbidden families, but does not prove the full conjecture (Alon, Shikhelman, 2018).
October 2026 finite-family result
On October 22, 2026, a report on the preprint NP-Hardness of Generalized-Turán Graph Modification Problems by Lior Gishboliner, Yevgeny Levanzov, and Asaf Shapira stated that the hardness conjecture is proved for finite graph families, with an elementary recovery of the earlier case. This is a claimed advance, not independently verified here; arbitrary, possibly infinite forbidden families remain outside the result.
Current status (as of October 2026): The finite-family case is claimed proved but remains unverified; the conjecture for arbitrary, possibly infinite forbidden families remains open.
Solutions 0
No solutions have been posted yet.