NP-Hardness of Generalized-Tur\'an Graph Modification Problems
En palabras de los autores
For graphs and a graph-family , let denote the maximum possible number of copies of in an -free subgraph of . Alon and Shikhelman conjectured that for every family of graphs with for every , it is NP-hard to compute , and even to approximate it up to additive error on -vertex graphs, for any fixed . The case was established in a breakthrough result of Alon, Shapira and Sudakov. We prove the Alon-Shikhelman conjecture for finite families . In particular, we obtain an elementary proof of the Alon-Shapira-Sudakov result when is finite.
Resultado principalLimitación que admiten los autores
Apareció: viernes, 23 de octubre. arXiv. Preprint, todavía sin revisión por pares.