Conjunto de vértices de retroalimentação

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Nuvola apps important.svg
A tradução deste artigo ou se(c)ção está abaixo da qualidade média aceitável.
É possível que tenha sido feita por um tradutor automático ou por alguém que não conhece bem o português ou a língua original do texto. Caso queira colaborar com a Wikipédia, tente encontrar a página original e melhore este artigo conforme o guia de tradução.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.
Searchtool.svg
Esta página ou secção foi marcada para revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Se tem algum conhecimento sobre o tema, por favor, verifique e melhore a consistência e o rigor deste artigo. Considere utilizar {{revisão-sobre}} para associar este artigo com um WikiProjeto e colocar uma explicação mais detalhada na discussão.

Dentro das 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ção[editar | editar código-fonte]

O problema de decisão segue abaixo:

INSTÂNCIA: Um Grafo (direcionado ou não) G = (V, E) e um inteiro positivo k.
PERGUNTA: Existe um subconjunto X \subseteq V com |X| \leq k tal que G sem os vértices de X é livre de qualquer ciclo (teoria de grafos)?

O grafo G[V \setminus X] subsequente da remoção dos vértices de X do grafo G é 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ícil[editar | editar código-fonte]

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 exatos[editar | editar código-fonte]

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ção[editar | editar código-fonte]

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]

Limites[editar | editar código-fonte]

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ções[editar | editar código-fonte]

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?]

Notas[editar | editar código-fonte]

  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ências[editar | editar código-fonte]

Artigos de pesquisa[editar | editar código-fonte]

  • Ann Becker, Reuven Bar-Yehuda, Dan Geiger: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res. (JAIR) 12: 219-234 (2000)
  • Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's Method of Conditioning and Greedy-Like Approximation Algorithms for the Vertex Feedback Set Problem.", Artif. Intell. 83 (1): 167–188, doi:10.1016/0004-3702(95)00004-6 
  • Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7): 1188-1198 (2008)
  • Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5): (2008)
  • Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms.", Algorithmica 52 (2): 293–307, doi:10.1007/s00453-007-9152-0 
  • Fomin, Fedor V.; Villanger, Yngve (2010), "Finding Induced Subgraphs via Minimal Triangulations.", Proc. of STACS 2010, pp. 383–394, doi:10.4230/LIPIcs.STACS.2010.2470 
  • ==Referências em contribuições recentes==
Commons-emblem-question book orange.svg

Olá, Conjunto de vértices de retroalimentação. Algumas contribuições que realizou não possuem referências necessárias para cumprir a política de verificabilidade da Wikipédia, pelo que o texto foi removido, modificado ou marcado com a predefinição {{Sem-fontes}}.

Para referenciar, é necessário colocar <ref>referência</ref> após sua edição, substituindo referência pela bibliografia ou ligação de onde obteve a informação, de acordo com o livro de estilo.

Antes de retirar a predefinição, por favor, consulte o usuário que a colocou, ou com alguém que goze da confiança da comunidade (ex. um administrador).

Por favor, leia as ligações observando 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 da Wikipédia. Se desta vez não o fez, 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 pesquisa[editar | editar código-fonte]

  • 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 (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5