La fragmentación de grafos tiene como objetivo encontrar el subconjunto de vértices más pequeño cuya eliminación divide un grafo en componentes de tamaño limitado. Aunque este problema tiene aplicaciones en el desmantelamiento de redes y combinatoria, los límites teóricos en las soluciones óptimas siguen siendo limitados.