×

zbMATH — the first resource for mathematics

Introduction to testing graph properties. (English) Zbl 1343.68299
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 470-506 (2011).
Summary: The aim of this article is to introduce the reader to the study of testing graph properties, while focusing on the main models and issues involved. No attempt is made to provide a comprehensive survey of this study, and specific results are often mentioned merely as illustrations of general themes.
For the entire collection see [Zbl 1220.68005].

MSC:
68W20 Randomized algorithms
05C85 Graph algorithms (graph-theoretic aspects)
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N.: Testing subgraphs of large graphs. Random Structures and Algorithms 21, 359–370 (2002) · Zbl 1027.68095
[2] Alon, N.V., Fischer, E., Krivelevich, M.V., Szegedy, M.V.: Efficient Testing of Large Graphs. Combinatorica 20, 451–476 (2000) · Zbl 1052.68096
[3] Alon, N., Fischer, E., Newman, I., Shapira, A.: A Combinatorial Characterization of the Testable Graph Properties: It’s All About Regularity. In: 38th STOC, pp. 251–260 (2006) · Zbl 1301.05354
[4] Alon, N.V., Krivelevich, M.V.: Testing k-Colorability. SIAM Journal on Disc. Math. 15(2), 211–227 (2002) · Zbl 1001.05058
[5] Alon, N., Kaufman, T., Krivelevich, M., Ron, D.: Testing triangle freeness in general graphs. In: 17th SODA, pp. 279–288 (2006) · Zbl 1192.68465
[6] Alon, N., Shapira, A.: Testing subgraphs in directed graphs. JCSS 69, 354–482 (2004) · Zbl 1084.68087
[7] Alon, N., Shapira, A.: Every Monotone Graph Property is Testable. In: 37th STOC, pp. 128–137 (2005) · Zbl 1192.68466
[8] Alon, N., Shapira, A.: A Characterization of the (natural) Graph Properties Testable with One-Sided. In: 46th FOCS, pp. 429–438 (2005)
[9] Alon, N., Shapira, A.: A Characterization of Easily Testable Induced Subgraphs. Combinatorics Probability and Computing 15, 791–805 (2006) · Zbl 1318.68191
[10] Alon, N., Shapira, A.: A Separation Theorem in Property Testing. Combinatorica 28(3), 261–281 (2008) · Zbl 1174.05063
[11] Alon, N., Spencer, J.H.: The Probabilistic Method. John Wiley & Sons, Inc., Chichester (1992) · Zbl 0767.05001
[12] Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-hard problems. JCSS 58(1), 193–210 (1999) · Zbl 0937.68160
[13] Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that Distributions are Close. In: 41st FOCS, pp. 259–269 (2000)
[14] Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. In: The 36th FOCS, pp. 432–441 (1995) · Zbl 0938.68926
[15] Bellare, M., Goldreich, O., Sudan, M.: Free Bits, PCPs and Non-approximability – Towards Tight Results. SIAM Journal on Computing 27(3), 804–915 (1998) · Zbl 0912.68041
[16] Bender, M.V., Ron, D.V.: Testing acyclicity of directed graphs in sublinear time. In: Random Structures and Algorithms, pp. 184–205 (2002) · Zbl 1002.68113
[17] Ben-Eliezer, I., Kaufman, T., Krivelevich, M., Ron, D.: Comparing the strength of query types in property testing: the case of testing k-colorability. In: 19th SODA (2008) · Zbl 1192.68470
[18] Benjamini, I.V., Schramm, O., Shapira, A.: Every Minor-Closed Property of Sparse Graphs is Testable. In: 40th STOC, pp. 393–402 (2008) · Zbl 1231.68176
[19] Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. JCSS 47(3), 549–595 (1993) · Zbl 0795.68131
[20] Bogdanov, A., Obata, K., Trevisan, L.: A lower bound for testing 3-colorability in bounded-degree graphs. In: 43rd FOCS, pp. 93–102 (2002)
[21] Bogdanov, A., Trevisan, L.: Lower Bounds for Testing Bipartiteness in Dense Graphs. In: IEEE Conference on Computational Complexity, pp. 75–81 (2004)
[22] Canetti, R., Even, G., Goldreich, O.: Lower Bounds for Sampling Algorithms for Estimating the Average. IPL 53, 17–25 (1995) · Zbl 0875.68529
[23] Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. In: 19th ICALP, pp. 190–200 (2001) · Zbl 0987.68527
[24] de la Vega, W.F.: MAX-CUT has a randomized approximation scheme in dense graphs. Random Structures and Algorithms 8(3), 187–198 (1996) · Zbl 0848.90120
[25] Even, S.: Graph Algorithms. Computer Science Press (1979) · Zbl 0441.68072
[26] Even, S., Selman, A.L., Yacobi, Y.: The Complexity of Promise Problems with Applications to Public-Key Cryptography. Inform. and Control 61, 159–173 (1984) · Zbl 0592.94012
[27] Fischer, E., Matsliah, A.: Testing graph isomorphism. In: 17th SODA, pp. 299–308 (2006) · Zbl 1192.68479
[28] Fischer, E., Matsliah, A., Shapira, A.: Approximate hypergraph partitioning and applications. In: 48th FOCS, pp. 579–589 (2007) · Zbl 1271.68113
[29] Fischer, E., Newman, I.: Testing versus estimation of graph properties. In: 37th STOC, pp. 138–146 (2005) · Zbl 1192.68480
[30] Goldreich, O.: On promise problems: A survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254–290. Springer, Heidelberg (2006)
[31] Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008) · Zbl 1154.68056
[32] Goldreich, O.: A brief introduction to property testing. In: Goldreich, O. (ed.) Property Testing. LNCS, vol. 6390, pp. 1–5. Springer, Heidelberg (2010) · Zbl 1308.68149
[33] Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM, 653–750 (July 1998); Extended abstract in 37th FOCS (1996) · Zbl 1065.68575
[34] Goldreich, O., Krivelevich, M., Newman, I., Rozenberg, E.: Hierarchy Theorems for Property Testing. In: ECCC, TR08-097 (2008); Extended abstract in the proceedings of RANDOM 2009 · Zbl 1309.68221
[35] Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica, 302–343 (2002) · Zbl 0990.68103
[36] Goldreich, O., Ron, D.: A sublinear bipartite tester for bounded degree graphs. Combinatorica 19(3), 335–373 (1999) · Zbl 0932.68053
[37] Goldreich, O., Ron, D.: On Testing Expansion in Bounded-Degree Graphs. In: ECCC, TR00-020 (March 2000)
[38] Goldreich, O., Ron, D.: Approximating Average Parameters of Graphs. Random Structures and Algorithms 32(3), 473–493 (2008) · Zbl 1155.05057
[39] Goldreich, O., Ron, D.: Algorithmic Aspects of Property Testing in the Dense Graphs Model. In: ECCC TR08-039 (2008)
[40] Goldreich, O., Ron, D.: On Proximity Oblivious Testing. In: ECCC, TR08-041 (2008); Also in the proceedings of the 41st STOC (2009)
[41] Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. Random Structures and Algorithms 23(1), 23–57 (2003) · Zbl 1048.68062
[42] Gonen, M., Ron, D.: On the Benefits of Adaptivity in Property Testing of Dense Graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol. 4627, pp. 525–539. Springer, Heidelberg (2007) · Zbl 1171.68696
[43] Håstad, J.: Clique is hard to approximate within n 1 - {\(\epsilon\)} . Acta Mathematica 182, 105–142 (1999); (Preliminary Version in 28th STOC, 1996 and 37th FOCS (1996) · Zbl 0989.68060
[44] Hassidim, A., Kelner, J., Nguyen, H., Onak, K.: Local Graph Partitions for Approximation and Testing. In: 50th FOCS, pp. 22–31 (2009) · Zbl 1292.68126
[45] Hochbaum, D.: Approximation Algorithms for NP-Hard Problems. PWS (1996) · Zbl 1368.68010
[46] Kale, S., Seshadhri, C.: Testing expansion in bounded degree graphs. In: 35th ICALP, pp. 527–538 (2008); Preliminary version appeared as TR07-076, ECCC (2007) · Zbl 1153.68466
[47] Kaufman, T., Krivelevich, M., Ron, D.: Tight Bounds for Testing Bipartiteness in General Graphs. SIAM Journal on Computing 33(6), 1441–1483 (2004) · Zbl 1101.68607
[48] Lovász, L., Young, N.: Lecture notes on evasiveness of graph properties. Technical Report TR–317–91, Princeton University, Computer Science Department (1991)
[49] Marko, S., Ron, D.: Distance approximation in bounded-degree and general sparse graphs. Transactions on Algorithms 5(2) Article number 22 (2009) · Zbl 1155.68582
[50] Mihail, M.: Conductance and convergence of Markov chains– A combinatorial treatment of expanders. In: 30th FOCS, pp. 526–531 (1989)
[51] A. Nachmias and A. Shapira. Testing the expansion of a graph. TR07-118. In: ECCC (2007) · Zbl 1194.68173
[52] Orenstein, Y.: Testing properties of directed graphs. Master’s thesis, School of Electrical Engineering (2010)
[53] Parnas, M., Ron, D.: Testing the diameter of graphs. Random Structures and Algorithms 20(2), 165–183 (2002) · Zbl 1052.68104
[54] Parnas, M., Ron, D., Rubinfeld, R.: Tolerant Property Testing and Distance Approximation. Journal of Computer and System Sciences 72(6), 1012–1042 (2006) · Zbl 1100.68109
[55] Raskhodnikova, S., Smith, A.: A note on adaptivity in testing properties of bounded-degree graphs. In: ECCC TR06-089 (2006)
[56] Ron, D.: Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in TCS 5(2), 73–205 (2010) · Zbl 1184.68610
[57] Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996) · Zbl 0844.68062
[58] Szemeŕedi, E.: Regular partitions of graphs. In: Proceedings, Colloque Inter. CNRS, pp. 399–401 (1978)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.