Conjunto de vértices de retroalimentação

Dentro da disciplina da Teoria dos Grafos, um conjunto de vértices de retroalimentação de um grafo é um conjunto de vértices cujas folhas removíveis deixa o grafo sem ciclo (teoria de grafos). Em outra palavras, cada conjunto de vértices retroativos contém pelo menos um vértice contido em algum ciclo no grafo. O problema dos conjuntos de vértices retroativos é um problema NP-completo em complexidade computacional. Ele estava presente nos 21 problemas NP-completos de Karp. O conjunto de vértices de retroalimentação possui várias aplicações em sistemas operacionais, sistemas de banco de dados, montagem de genoma (criação de cromossomos artificiais) e no design de chips.

DefiniçãoEditar

O problema de decisão segue abaixo:

INSTÂNCIA: Um Grafo (direcionado ou não)   e um inteiro positivo  .
PERGUNTA: Existe um subconjunto   com   tal que   sem os vértices de   é livre de qualquer ciclo (teoria de grafos)?

O grafo   subsequente da remoção dos vértices de X do grafo   é uma floresta (pode ser definida como uma união disjunta de árvores) induzida. Assim, achar um conjunto de vértices retroativos mínimo é equivalente a achar uma floresta induzida máxima.

NP-difícilEditar

Karp (1972) mostrou que o problema dos conjuntos de vértices retroativos para grafos direcionados é NP-completo. O problema permanece NP-completo em grafos direcionados com máximo grau de entrada e saída dois, e em grafos planares com máximo grau de entrada e saída três.[1] A redução de Karp também implica na NP-completude do problema dos conjuntos de vértices retroativos para grafos não-direcionados, onde o problema se mantém NP-difícil em grafos de grau de entrada e saída quatro.

Perceba que o problema em remover arestas para tornar o grafo não-cíclico é equivalente a achar uma árvore de extensão mínima, que pode ser feita em tempo polinomial. Em contrapartida, o problema em remover arestas em grafos direcionados para torná-lo um grafo não-cíclico direcionado, o problema do conjunto dos vértices retroativos, é NP-completo.

Algoritmos exatosEditar

O correspondente problema de otimização NP de achar o tamanho do conjunto mínimo de vértices retroativos pode ser resolvido em tempo O(1.7347n), onde n é o número de vértices do grafo.[2] Este algoritmo computa a floresta induzida máxima, e quando a floresta é obtida, seu complemento é o conjunto de vértices retroativos mínimo. Seu número de vértices em um grafo é limitado por O(1.8638n).[3] O problema dos vértices retroativos direcionados pode ainda ser resolvido em tempo O*(1.9977n), onde  n é o número de vértices no grafo direcionado dado.[4] As versões parametrizadas do problema direcionado e não-direcionado são ambos tratáveis com parâmetros fixos.[5]

AproximaçãoEditar

O problema é APX-completo (classe de problemas que permitem uma aproximação em tempo polinomial), que se deriva da APX-completude do problema da cobertura de vértices,[6] e da existência da aproximação do problema da cobertura de vértices para ele.[7] A melhor aproximação conhecida em grafos não-direcionados é em um fator de dois.[8]

LimitesEditar

De acordo com o teorema de Erdős-Pósa, o tamanho mínimo de um conjunto de vértices retroativos está abaixo de um fator logarítmico do número máximo de ciclos com vértices disjuntos no grafo dado.

AplicaçõesEditar

Em sistemas operacionais, conjuntos de vértices retroativos desempenham um papel proeminente no estudo de recuperação de deadlock. Em grafos Wait-for de um sistema operacional, cada ciclo direcionado corresponde a uma situação de deadlock. Para resolver todos os deadlocks, alguns processos bloqueados devem ser abortados. Um conjunto mínimo de vértices retroativos corresponde ao número mínimo de processos que precisam ser abortados(Silberschatz & Galvin 2008).

Além disso, o problema do conjunto dos vértices retroativos tem aplicações em design de chips (cf. Festa, Pardalos & Resende (2000)) e montagem de genomas.[carece de fontes?]

NotasEditar

Referências

  1. unpublished results due to Garey and Johnson, cf. Garey & Johnson (1979): GT7
  2. Fomin & Villanger (2010)
  3. Fomin et al. (2008)
  4. Razgon (2007)
  5. Chen et al. (2008)
  6. Dinur & Safra 2005
  7. Karp (1972)
  8. Becker & Geiger (1996)

ReferênciasEditar

Artigos de pesquisaEditar

  • ==Referências em contribuições recentes==

Olá, Conjunto de vértices de retroalimentação. Alerto que algumas contribuições que realizou não possuem fontes confiáveis e independentes, conforme orienta a política de verificabilidade da Wikipédia, por isso seu texto pode ter sido removido, modificado ou marcado com o uso de predefinições (como {{sem-fontes}} e {{carece de fontes}}).

Para adicionar referências é necessário colocar <ref>referência</ref> após sua edição, substituindo o termo referência pela bibliografia ou ligação de onde obteve a informação que adicionou, de acordo com o livro de estilo. Encontre fontes: Google (notícias, livros e acadêmico).

Por favor, leia as ligações apresentadas acima e observe o que dizem, assim seu esforço aqui terá um bom resultado. Se, ao ler a política, lhe surgir alguma dúvida, por favor deixe-me uma mensagem em minha página de discussão e quando eu puder lhe responderei, ou então, pode consultar algum membro do programa de tutoria ou um administrador da Wikipédia. Também pode utilizar o assistente para a criação de artigos, que o guiará passo a passo no processo de criação. Saudações e boa sorte em suas edições.

  • I. Razgon : Computing Minimum Directed Feedback Vertex Set in O*(1.9977n). In: Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura (Eds.), Proceedings of the 10th Italian Conference on Theoretical Computer Science 2007, World Scientific, pp. 70–81 (author's version (pdf), preliminary full version (pdf)).

Livros-texto e artigos de pesquisaEditar

  • P. Festa, P.M. Pardalos, and M.G.C. Resende, Feedback set problems, Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos, Eds., Kluwer Academic Publishers, Supplement vol. A, pp. 209–259, 2000. author's version (pdf)
  • Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts, ISBN 978-0-470-12872-5 8th ed. , John Wiley & Sons. Inc