b'\n_START_ARTICLE_\nConjunto de v\xc3\xa9rtices de retroalimenta\xc3\xa7\xc3\xa3o\n_START_SECTION_\nNP-dif\xc3\xadcil\n_START_PARAGRAPH_\nKarp (1972) mostrou que o problema dos conjuntos de v\xc3\xa9rtices retroativos para grafos direcionados \xc3\xa9 NP-completo. O problema permanece NP-completo em grafos direcionados com m\xc3\xa1ximo grau de entrada e sa\xc3\xadda dois, e em grafos planares com m\xc3\xa1ximo grau de entrada e sa\xc3\xadda tr\xc3\xaas. A redu\xc3\xa7\xc3\xa3o de Karp tamb\xc3\xa9m implica na NP-completude do problema dos conjuntos de v\xc3\xa9rtices retroativos para grafos n\xc3\xa3o-direcionados, onde o problema se mant\xc3\xa9m NP-dif\xc3\xadcil em grafos de grau de entrada e sa\xc3\xadda quatro._NEWLINE_Perceba que o problema em remover arestas para tornar o grafo n\xc3\xa3o-c\xc3\xadclico \xc3\xa9 equivalente a achar uma \xc3\xa1rvore de extens\xc3\xa3o m\xc3\xadnima, que pode ser feita em tempo polinomial. Em contrapartida, o problema em remover arestas em grafos direcionados para torn\xc3\xa1-lo um grafo n\xc3\xa3o-c\xc3\xadclico direcionado, o problema do conjunto dos v\xc3\xa9rtices retroativos, \xc3\xa9 NP-completo.\n_START_SECTION_\nAlgoritmos exatos\n_START_PARAGRAPH_\nO correspondente problema de otimiza\xc3\xa7\xc3\xa3o NP de achar o tamanho do conjunto m\xc3\xadnimo de v\xc3\xa9rtices retroativos pode ser resolvido em tempo O(1.7347\xe2\x81\xbf), onde n \xc3\xa9 o n\xc3\xbamero de v\xc3\xa9rtices do grafo. Este algoritmo computa a floresta induzida m\xc3\xa1xima, e quando a floresta \xc3\xa9 obtida, seu complemento \xc3\xa9 o conjunto de v\xc3\xa9rtices retroativos m\xc3\xadnimo. Seu n\xc3\xbamero de v\xc3\xa9rtices em um grafo \xc3\xa9 limitado por O(1.8638\xe2\x81\xbf). O problema dos v\xc3\xa9rtices retroativos direcionados pode ainda ser resolvido em tempo O*(1.9977\xe2\x81\xbf), onde \xc2\xa0n \xc3\xa9 o n\xc3\xbamero de v\xc3\xa9rtices no grafo direcionado dado. As vers\xc3\xb5es parametrizadas do problema direcionado e n\xc3\xa3o-direcionado s\xc3\xa3o ambos trat\xc3\xa1veis com par\xc3\xa2metros fixos.\n_START_SECTION_\nAproxima\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nO problema \xc3\xa9 APX-completo (classe de problemas que permitem uma aproxima\xc3\xa7\xc3\xa3o em tempo polinomial), que se deriva da APX-completude do problema da cobertura de v\xc3\xa9rtices, e da exist\xc3\xaancia da aproxima\xc3\xa7\xc3\xa3o do problema da cobertura de v\xc3\xa9rtices para ele. A melhor aproxima\xc3\xa7\xc3\xa3o conhecida em grafos n\xc3\xa3o-direcionados \xc3\xa9 em um fator de dois.\n_START_SECTION_\nLimites\n_START_PARAGRAPH_\nDe acordo com o teorema de Erd\xc5\x91s-P\xc3\xb3sa, o tamanho m\xc3\xadnimo de um conjunto de v\xc3\xa9rtices retroativos est\xc3\xa1 abaixo de um fator logar\xc3\xadtmico do n\xc3\xbamero m\xc3\xa1ximo de ciclos com v\xc3\xa9rtices disjuntos no grafo dado.\n_START_SECTION_\nAplica\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nEm sistemas operacionais, conjuntos de v\xc3\xa9rtices retroativos desempenham um papel proeminente no estudo de recupera\xc3\xa7\xc3\xa3o de deadlock. Em grafos Wait-for de um sistema operacional, cada ciclo direcionado corresponde a uma situa\xc3\xa7\xc3\xa3o de deadlock. Para resolver todos os deadlocks, alguns processos bloqueados devem ser abortados. Um conjunto m\xc3\xadnimo de v\xc3\xa9rtices retroativos corresponde ao n\xc3\xbamero m\xc3\xadnimo de processos que precisam ser abortados(Silberschatz & Galvin 2008)._NEWLINE_Al\xc3\xa9m disso, o problema do conjunto dos v\xc3\xa9rtices retroativos tem aplica\xc3\xa7\xc3\xb5es em design de chips (cf. Festa, Pardalos & Resende (2000)) e montagem de genomas.'