Tempo de Iteração e Número de Posição Geral em Convexidade de Grafos

Vol 55, 2023 - 160682
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Nesse artigo, estudamos dois parâmetros de convexidade de grafos: tempo de iteração e número de posição geral. O primeiro foi definido na convexidade geodésica em 1981, mas sua complexidade estava ainda em aberto. O segundo foi definido na convexidade geodésica e provado $\NP$-difícil em 2018. Estendemos esses parâmetros para qualquer convexidade e provamos que o tempo de iteração é $\NP$-difícil na convexidade $P_3$ e, com isso, conseguimos provar que ele também é $\NP$-difícil na convexidade geodésica mesmo em grafos com diâmetro dois, uma questão natural que estava sem resposta desde quando o parâmetro foi definido, em 1981. Esses resultados são também importantes, visto que são os últimos dois resultados de $\NP$-completude que faltavam entre os dez parâmetros mais estudados de convexidade de grafos nas convexidades $P_3$ e geodésica. Finalmente também provamos que o número de posição geral da convexidade monofônica é $\NP$-difícil, $W[1]$-difícil e $n^{1-\varepsilon}$-inaproximável em tempo polinomial para qualquer $\varepsilon>0$ a menos que $\P=\NP$, mesmo em grafos com diâmetro dois.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 UNIVERSIDADE FEDERAL DO CEARÁ
  • 2 Universidade Federal do Rio de Janeiro
  • 3 Universidade Federal Fluminense
Eixo Temático
  • 19. TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Convexidade de Grafos; Tempo de iteração; Posição Geral