NP-Hardness of Generalized-Tur'an Graph Modification Problems

arXiv:2610.30654 · math.CO · Submitted 2026-10-22 · Read on arXiv

math.CO

Submitted: 2026-10-22

Updated: 2026-10-22

Terminology

• NP-hardness — 1× in this paper · explained in 3 episodes

Related papers

• Exponential random graph models with soft clique constraints
• Two Linear Programs are Better than One
• Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy
• A complete classification of perfect state transfer in Grover walks on abelian Cayley graphs
• Arithmetic Circuits and Neural Networks for Regular Matroids
• On composition and decomposition operations for vector spaces, graphs and matroids