Data e hora: quarta, 18 de outubro de 2023, às 9h30.
Local: sala 2077 (ICEx)
Palestrante: Ana Karolinna Maia de Oliveira (DC – UFC)
Título: Os números de fecho e de intervalo de orientações de grafos
Resumo: Neste trabalho, seja D um grafo orientado, estudamos seu número de intervalo e número de envoltória, denotados por \oin(D) e \ohn(D), respectivamente, na geodésica orientada, convexidades P_3 e P_3* orientadas. Esta última, acreditamos ter sido formalmente definida e estudada pela primeira vez neste artigo, embora sua versão não direcionada seja bem conhecida na literatura. Com relação aos limitantes, para um grafo orientado D fortemente conexo na convexidade geodésica orientada, provamos que \ohng(D)<= m(D)-n(D)+2 e que existe pelo menos um grafo orientado D tal que \ohng(D) = m(D)-n(D). Também determinamos valores exatos para os números de envoltória nessas três convexidades para torneios, o que implicam algoritmos com tempo polinomial para calculá-los. Esses resultados nos permitem deduzir algoritmos com tempo polinomial para calcular \ohnp(D) quando o gráfico subjacente de D é split ou cobipartido. Além disso, fornecemos um meta-teorema provando que decidir se \oing(D)<= k ou \ohng(D)<= k é NP-hard ou W[i]-hard parametrizado por k, para algum i em Z*_+, então o mesmo vale mesmo se o gráfico subjacente de D for bipartido. Provamos que decidir se \ohnp(D)<= k ou \ohnps(D)<= k$ é W[2]-hard parametrizado por k, mesmo que o gráfico subjacente de D seja bipartido; decidir se \oinp(D)<= k ou \oinps(D)<=k$ é NP-completo, e o mesmo para \ohnps(D)<= k mesmo que D não tenha ciclos direcionados e o gráfico subjacente de D seja um gráfico bipartido cordal; decidir se \oinp(D)<= k, e o mesmo para \oinps(D)<= k$ é W[2]-hard parametrizado por k, mesmo que o grafo subjacente de D seja split. Finalmente, mostramos também que o número de intervalo e número de envoltória nas convexidades P_3 e P_3* orientadas podem ser calculadas em tempo polinomial para grafos com largura em árvore limitada usando o Teorema de Courcelle.
