Garra é a denominação dada a um grafo bipartido completo K1,3, ou seja, que possui uma partição com um vértice e outra com três vértices. Um grafo G=(V,E) é tido como livre de garras se não existirem subgrafos induzidos por vértices em G isomorfos ao grafo K1,3. O Problema de Eliminação de Garras (PEG) consiste em encontrar um conjunto de cardinalidade mínima S ⊆ V(G) de tal maneira que G[V(G)\S] seja um grafo livre de garras. O PEG é NP-Difícil, derivando-se a prova genérica de Lewis e Yannakakis (1980) para problemas de eliminação de vértices. Neste trabalho, propomos dois métodos baseados nas meta-heurísticas Algoritmos Genéticos e VNS, respectivamente. 27 grupos de instâncias de grafos intervalares e 4 grupos de instâncias de grafos randômicos foram utilizados nos testes computacionais, que demonstraram que ambos os métodos são capazes de chegar a soluções de alta qualidade com pequeno esforço computacional.