[en] A CHARACTERIZATION OF TESTABLE GRAPH PROPERTIES IN THE DENSE GRAPH MODEL

• Ano de defesa: 2023
• Autor(a) principal: FELIPE DE OLIVEIRA
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] ALGORITMOS ALEATORIZADOS; [pt] O LEMA DE REGULARIDADE DE SZEMEREDI; [pt] TESTAGEM DE PROPRIEDADES; [pt] ALGORITMOS EM GRAFOS; [pt] ALGORITMOS DE APROXIMACAO; [en] RANDOMIZED ALGORITHMS; [en] SZEMEREDI S REGULARITY LEMMA; [en] PROPERTY TESTING; [en] GRAPH ALGORITHMS; [en] APPROXIMATION ALGORITHMS
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=62907&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=62907&idi=2; http://doi.org/10.17771/PUCRio.acad.62907

[pt] Consideramos, nesta dissertação, a questão de determinar se um grafo tem uma propriedade P, tal como G é livre de triângulos ou G é 4- colorível. Em particular, consideramos para quais propriedades P existe um algoritmo aleatório com probabilidades de erro constantes que aceita grafos que satisfazem P e rejeita grafos que são epsilon-longe de qualquer grafo que o satisfaça. Se, além disso, o algoritmo tiver complexidade independente do tamanho do grafo, a propriedade é dita testável. Discutiremos os resultados de Alon, Fischer, Newman e Shapira que obtiveram uma caracterização combinatória de propriedades testáveis de grafos, resolvendo um problema em aberto levantado em 1996. Essa caracterização diz informalmente que uma propriedade P de um grafo é testável se e somente se testar P pode ser reduzido a testar a propriedade de satisfazer uma das finitas partições Szemerédi.