Conjunto de vértices de retroalimentação

Predefinição:Revisã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) $G=(V,E)$ e um inteiro positivo $k$.

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

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

Predefinição:Harvtxt 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. 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ⁿ), onde n é o número de vértices do grafo. 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ⁿ). O problema dos vértices retroativos direcionados pode ainda ser resolvido em tempo O*(1.9977ⁿ), onde n é o número de vértices no grafo direcionado dado. As versões parametrizadas do problema direcionado e não-direcionado são ambas tratáveis com parâmetros fixos.

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; e da existência da aproximação do problema da cobertura de vértices para ele. A melhor aproximação conhecida em grafos não-direcionados é em um fator de dois.

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 abortadosPredefinição:Harv.

Além disso, o problema do conjunto dos vértices retroativos tem aplicações em design de chips (cf. Predefinição:Harvtxt) e montagem de genomas.Predefinição:Carece de fontes

Bibliografia

• Ann Becker, Reuven Bar-Yehuda, Dan Geiger: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res. (JAIR) 12: 219-234 (2000)
• Predefinição:Citation
• Predefinição:Citation
• 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)
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation A1.1: GT7, pg.191.
• Predefinição:Cite
• 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)
• Predefinição:Citation