Conjunto de vértices de retroalimentação

Dentro da disciplina de teoria dos grafos, um conjunto de vértices de retroalimentação de um grafo é um conjunto de vértices cujas folhas removíveis deixam o grafo sem ciclo. 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

O problema de decisão segue abaixo:

INSTÂNCIA: Um grafo (direcionado ou não) ${\displaystyle G=(V,E)}$ e um inteiro positivo ${\displaystyle k}$.

PERGUNTA: Existe um subconjunto ${\displaystyle X\subseteq V}$ com ${\displaystyle |X|\leq k}$, tal que ${\displaystyle G}$ sem os vértices de ${\displaystyle X}$, é livre de qualquer ciclo?

O grafo ${\displaystyle G[V\setminus X]}$ subsequente da remoção dos vértices de ${\displaystyle X}$ do grafo ${\displaystyle 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

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á-los grafos não-cíclicos direcionados (ou seja, o problema do conjunto dos vértices retroativos) é NP-completo.

Algoritmos exatos

O correspondente problema de otimização NP de encontrar o tamanho do conjunto mínimo de vértices retroativos pode ser resolvido em tempo O(1.7347^n), 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.8638^n).[3] O problema dos vértices retroativos direcionados pode ainda ser resolvido em tempo O*(1.9977^n), 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 ambas tratáveis com parâmetros fixos.[5]

Aproximação

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

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

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

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)

Bibliografia

• 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 
• Cao, Yixin; Chen, Jianer; Liu, Yang (2010), Kaplan, Haim, ed., «SWAT 2010», LNCS, 6139: 93–104, doi:10.1007/978-3-642-13731-0 
• 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)
• Dinur, Irit; Safra, Samuel (2005), «On the hardness of approximating minimum vertex cover» (PDF), Annals of Mathematics, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, consultado em 5 de março de 2010. 
• 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 
• Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 0-7167-1045-5, W.H. Freeman  A1.1: GT7, pg.191.
• == Referências em contribuições recentes ==

Olá, Conjunto de vértices de retroalimentação. Boas-vindas à Wikipédia! 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 foi 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 as orientações de formatação do livro de estilo. Encontre fontes: ABW  • CAPES  • Google (notícias • livros • acadêmico).

Por favor, leia com atenção as políticas e regulamentos apresentados acima, 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)).
• 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