Buscando triángulos en grafos muy grandes: un ejemplo de property testing

• Espuny Díaz, Alberto ^[1]
  1. [1] University of Birmingham

     University of Birmingham

     Reino Unido

     
• Localización: TEMat: Divulgación de trabajos de estudiantes de matemáticas, ISSN-e 2530-9633, Nº. 3, 2019, págs. 87-100
• Idioma: español
• Enlaces
  • Texto completo
• Resumen
  • español

    El property testing hace referencia a un conjunto de técnicas algorítmicas que se han desarrollado para conseguir algoritmos decisionales que trabajen en tiempo sublineal en el tamaño de la entrada a cambio de perder precisión en la respuesta del algoritmo. En este artículo presentamos una breve discusión sobre el property testing, explicando el porqué de su utilidad y cómo valorar su eficiencia. En particular, nos centramos en algoritmos que comprueban propiedades en grafos, presentando los tres modelos más utilizados para comprobar estas propiedades y un ejemplo de cómo tratar una propiedad, la ausencia de triángulos, en cada uno de ellos.

  • English

    Property testing refers to a group of algorithmic techniques developed to achieve decision algorithms that work in sublinear time at the expense of some accuracy in the algorithms’ output. In this paper, we present a brief discussion about property testing, explaining its usefulness and how to evaluate the efficiency of property testing algorithms. In particular, we consider algorithms that test graph properties. We present the three most common property testing models for graphs and, as an example, show how to test one property, triangle-freeness, in each of these models

• Referencias bibliográficas
  • ALON, Noga. «Testing subgraphs in large graphs». En:Random Structures & Algorithms21.3-4 (2002).Random structures and algorithms (Poznan,...
  • ALON, Noga;FISCHER, Eldar;KRIVELEVICH, Michael, ySZEGEDY, Mario. «Efficient testing of largegraphs». En:Combinatorica. An International Journal...
  • ALON, Noga;FISCHER, Eldar;NEWMAN, Ilan, ySHAPIRA, Asaf. «A combinatorial characterization ofthe testable graph properties: it’s all about...
  • ALON, Noga;KAUFMAN, Tali;KRIVELEVICH, Michael, yRON, Dana. «Testing triangle-freeness in generalgraphs». En:SIAM Journal on Discrete Mathematics22.2...
  • ALON, Noga ySHAPIRA, Asaf. «Testing subgraphs in directed graphs». En:Journal of Computer andSystem Sciences69.3 (2004), págs. 353-382.ISSN:...
  • BENJAMINI, Itai;SCHRAMM, Oded, ySHAPIRA, Asaf. «Every minor-closed property of sparse graphs istestable». En:Advances in Mathematics223.6...
  • BLUM, Manuel;LUBY, Michael, yRUBINFELD, Ronitt. «Self-testing/correcting with applications tonumerical problems». En:Proceedings of the 22nd...
  • ESPUNY DÍAZ, Alberto;JOOS, Felix;KÜHN, Daniela, yOSTHUS, Deryk. «Edge correlations in randomregular hypergraphs and applications to subgraph...
  • FISCHER, Eldar yFORTNOW, Lance. «Tolerant versus intolerant testing for Boolean properties». En:Theory of Computing. An Open Access Journal2...
  • FISCHER, Eldar yNEWMAN, Ilan. «Testing versus estimation of graph properties». En:SIAM Journalon Computing37.2 (2007), págs. 482-501.ISSN:...
  • GLASNER, Dana ySERVEDIO, Rocco A. «Distribution-free testing lower bounds for basic Booleanfunctions». En:Theory of Computing. An Open Access...
  • GOLDREICH, Oded;GOLDWASSER, Shafi, yRON, Dana. «Property testing and its connection to learningand approximation». En:Journal of the ACM45.4...
  • GOLDREICH, Oded yRON, Dana. «Property testing in bounded degree graphs». En:Algorithmica.An International Journal in Computer Science32.2...
  • HALEVY, Shirley yKUSHILEVITZ, Eyal. «Distribution-free property-testing». En:SIAM Journal onComputing37.4 (2007), págs. 1107-1138.ISSN: 0097-5397.https://doi.org/10.1137/050645804.
  • HALEVY, Shirley yKUSHILEVITZ, Eyal. «Distribution-free connectivity testing for sparse graphs». En:Algorithmica. An International Journal...
  • JOOS, Felix;KIM, Jaehoon;KÜHN, Daniela, yOSTHUS, Deryk. «A characterization of testable hypergraphproperties». En:ArXiv e-prints(jul. de 2017)....
  • KARP, Richard M. «Reducibility among combinatorial problems». En:Complexity of computer compu-tations (Proc. Sympos., IBM Thomas J. Watson...
  • KAUFMAN, Tali;KRIVELEVICH, Michael, yRON, Dana. «Tight bounds for testing bipartiteness ingeneral graphs». En:SIAM Journal on Computing33.6...
  • MANTEL, W. «Problem 28 (solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh andW.A. Wythoff». En:Wiskundige Opgaven10 (1907),...
  • MARKO, Sharon yRON, Dana. «Distance approximation in bounded-degree and general sparsegraphs». En:Approximation,randomization and combinatorial...
  • NEWMAN, Ilan ySOHLER, Christian. «Every property of hyperfinite graphs is testable». En:SIAMJournal on Computing42 (2013), págs. 1095-1112.ISSN:...
  • PARNAS, Michal y RON, Dana. «Testing the diameter of graphs». En:Random Structures & Algorithms20.2 (2002), págs. 165-183.ISSN: 1042-9832.https://doi.org/10.1002/rsa.10013.abs.
  • PARNAS, Michal;RON, Dana, yRUBINFELD, Ronitt. «Tolerant property testing and distance approxi-mation». En:Journal of Computer and System Sciences72.6...
  • RON, Dana. «Algorithmic and analysis techniques in property testing». En:Foundations and Trendsrin Theoretical Computer Science5.2 (2009),...
  • RUBINFELD, Ronitt ySUDAN, Madhu. «Robust characterizations of polynomials with applicationsto program testing». En:SIAM Journal on Computing25.2...
  • SZEMERÉDI, Endre. «Regular partitions of graphs». En:Problèmes combinatoires et théorie des graphes(Colloq. Internat. CNRS, Univ. Orsay, Orsay,...