NP-Hardness of Generalized-Turán Graph Modification Problems
For graphs $G, T$ and a graph-family $\mathcal{H}$, let $ex(G,T,\mathcal{H})$ denote the maximum possible number of copies of $T$ in an $\mathcal{H}$-free subgraph of $G$. Alon and Shikhelman conjectured that for every family of graphs $\mathcal{H}$ with $χ(H) > s$ for every $H \in \mathcal{H}$, it is NP-hard to compute $ex(G,K_s,\mathcal{H})$, and even to approximate it up to additive error $n^{s-δ}$ on $n$-vertex graphs, for any fixed $δ> 0$. The case $s=2$ was established in a breakthrough result of Alon, Shapira and Sudakov. We prove the Alon-Shikhelman conjecture for finite families…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.30654
curl -X POST /api/v1/records/arxiv/2610.30654/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.30654/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'