ANÁLISE DO PROBLEMA DE F-SUBDIVISÃO

Autores

  • Matheus Sousa Correia
  • Victor Almeida Campos

Resumo

Uma subdivisão de um digrafo F, também chamada de F-subdivisão, é um digrafo obtido de F ao substituir cada arco (a,b) de F por um (a,b)-caminho direcionado. No artigo estudado, foi considerado o problema de F-SUBDIVISÃO para um digrafo F fixo, onde a entrada é um digrafo D e cuja questão é “D contém uma subdivisão de F como um subdigrafo?”. Um vértice v em um digrafo F é grande, quando o seu grau de saída ou de entrada é pelo menos 3; ou ambos o seu grau de saída e de entrada são iguais a 2. Já uma grade cilíndrica de ordem k consiste de k ciclos direcionados concêntricos e 2k caminhos direcionados conectando os ciclos em direções alternantes. O teorema(Kawabarayashi and Kreutzer [3]) diz que para qualquer inteiro positivo, existe um inteiro f(k) tal que dado qualquer digrafo, em tempo polinomial, pode-se obter tanto uma grade cilíndrica de ordem k como um menor borboleta, ou uma árvore de decomposição direcionada de largura máxima f(k). Em [2], os autores mencionam que F-SUBDIVISÃO é de tempo polinomial resolvível em digrafos de largura de árvore direcionada limitada. Depois, mencionam sem provar que: (*) (para qualquer digrafo planar F com nenhum vértice grande, há um inteiro k_F tal que a grade cilíndrica de ordem k_F contém uma F-subdivisão.). Este trabalho, considera que (*) é falso e tem como objetivo caracterizar os digrafos F tais que (*) não seja válido. Para isto, deseja-se caracterizar F-modelos para ajudar nesta tarefa. Em suma, a pesquisa obteve como resultado a seguinte propriedade para dois digrafos H e G quaisquer, H é menor de G sse G tem H-modelo. [1] J. Bang-Jensen, F. Havet e A. Maia, “Finding a subdivision of a digraph”, Theoretical Comp. Sci. 562, 2015, 283–303. [2] F. Havet, A. Maia e B. Mohar, “Finding a subdivision of a prescribed digraph of order 4”, Journal of Graph Theory 87, 2018, 536–560. [3] K. Kawarabayashi et S. Kreutzer. The directed grid theorem. arXiv:1411.5681 [cs.DM]

Publicado

2019-01-14

Edição

Seção

XXXVII Encontro de Iniciação Científica