NP-hardness of additive approximation for generalized Turán problems
For a fixed graph $T$ and a fixed nonempty family $\mathcal{F}$ of graphs, let $\operatorname{ex}(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a graph $G$. Alon and Shikhelman~[Algorithmica, 2022] conjectured that if $e(T)> 0$ and no member of $\mathcal{F}$ is a subgraph of a blow-up of $T$, then for every $\varepsilon>0$, approximating $\operatorname{ex}(G, T, \mathcal{F})$ within an additive error $n^{v(T)-\varepsilon}$ is NP-hard for an input graph $G$ on $n$ vertices. The previously established general cases for this conjecture…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.16358
curl -X POST /api/v1/records/arxiv/2610.16358/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16358/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'