Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

What Graph Properties Are Constant-Time Testable?

Dense Graphs, Sparse Graphs, and Complex Networks

  • Article
  • Published:
The Review of Socionetwork Strategies Aims and scope Submit manuscript

Abstract

In this paper, we survey what graph properties have been found to be constant-time testable at present. How to handle big data is a very important issue in computer science. Developing efficient algorithms for problems on big data is an urgent task. For this purpose, constant-time algorithms are powerful tools, since they run by reading only a constant-sized part of each input. In other words, the running time is invariant regardless of the size of the input. The idea of constant-time algorithms appeared in the 1990s and spread quickly especially in this century. Research on graph algorithms is one of the best studied areas in theoretical computer science. When we study constant-time algorithms on graphs, we have three models that differ in the way that the graphs are represented: the dense-graph model, the bounded-degree model, and the general model. The first one is used to treat properties on dense graphs, and the other two are used to treat properties on sparse graphs. In this paper, we survey one by one what properties have been found to be constant-time testable in each of the three models.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Since every graph considered in this paper has no self-loop, the definitions of \(\varGamma _G(v)\) and \(\varGamma _G( \{ v\} )\) are consistent.

  2. There is another framework that does not use this assumption. It is called oblivious testing (see [5, 16, 18]).

  3. Every set of non-bipartite graphs that includes all odd cycles can also be a set of forbidden subgraphs for bipartiteness.

  4. Note that if \( |\mathcal{G}|\) is finite, there is a constant c, such that \(|V(G)| \le c\) for every \(G \in \mathcal{G}\), and thus, \(\mathcal{G}\) is an p-expander and \(\rho \)-hyperfinite for every \(p \ge c\) and \(\rho (\epsilon ) =c\).

  5. This is easily proven and the proof is omitted.

  6. \(\mathcal{HSF}\) was initially introduced in the preliminary version [21] of paper [22]. However, the definition of the latter is more general (wider) than in the preliminary version.

  7. Two distinct isolated cliques never overlap, except in the special case of double-isolated-cliques, which consists of two isolated cliques with size k sharing \(k-1\) vertices. A double-isolated-clique Q has no edge between Q and the other part of the graph (i.e., \(\mathrm {deg}_G(Q)=0\)), and thus, we specially define that a double-isolated-clique in G is contracted into a vertex in \(\mathcal{E}(G)\). Under this assumption, \(\mathcal{E}(G)\) is uniquely defined.

References

  1. Albert, R., & Barabási, A.-L. (2002). Statistical mechanics of complex networks. Review of Modern Physics, 74, 47–97.

    Article  Google Scholar 

  2. Alon, N., Fischer, E., Newman, I., & Shapira, A. (2008). A combinatorial characterization of the testable graph properties: It’s all about regularity. SIAM Journal on Computing, 37(6), 1703–1727.

    Article  Google Scholar 

  3. Alon, N., Seymour, P., & Thomas, R. (1990). Separator theorem for graphs with an excluded minor and its applications. Proceedings STOC, 1990, 293–299.

    Article  Google Scholar 

  4. Alon, N., & Shapira, A. (2005). Every monotone graph property is testable. In Proceedings of STOC 2005 (pp. 128–138). (Journal version: SIAM J. Comput., Vol. 38, No. 6, pp. 1703–1727, (2008)).

  5. Alon, N., & Shapira, A. (2005). A characterization of the (natural) graph properties testable with one-sided error. In Proceedings of FOCS 2005 (pp. 429–438) (Journal version: SIAM J. Comput., Vol. 37, No. 6, pp. 1703–1727, (2008)).

  6. Babu, J., Khoury, A., & Newman, I. (2016). Every property of outerplanar graphs is testable. In Proceedings of RANDOM 2016. LIPICS (pp. 1–21:19).

  7. Benjamini, I., Schramm, O., & Shapira, A. (2008). Every minor-closed property of sparse graphs is testable. In Proceedings of STOC 2008. ACM (pp. 393–402).

  8. Bottreau, A., & Métivier, Y. (1998). Some remarks on the Kronecker product of graphs. In Information Processing Letters (vol. 68, pp. 55–61). Amsterdam: Elsevier.

  9. Broder, A. Z., Kumar, S. R., Maghoul, F., Raghavan, R., Rajagoplalan, S., Stata, R., et al. (2000). Graph structure in the Web. Computer Networks, 33, 309–320.

    Article  Google Scholar 

  10. Cohen-Steiner, D., Kong, W., Sohler, C., & Valiant, G. (2018). Approximating the spectrum of a graph. Proceedings of SIGKDD, 2018, 1263–1271.

    Google Scholar 

  11. Cooper, C., & Uehara, R. (2010). Scale free properties of random \(k\)-trees. Mathematics in Computer Science, 3, 489–496.

    Article  Google Scholar 

  12. Diestel, R. (2016). Graph Theory (5th ed.). Berlin: Springer.

    Google Scholar 

  13. Elek, G. (2008). \(L^2\)-spectral invariants and convergent sequence of finite graphs. Journal of Functional Analysis, 254(10), 2667–2689.

    Article  Google Scholar 

  14. Fichtenberger, H., Peng, P., & Sohler, C. (2018). Every testable (infinite) property of bounded-degree graphs contains an infinite hyperfinite subproperty. arXiv: 1811.02937 (also appeared in SODA2019).

  15. Gao, Y. (2009). The degree distribution of random \(k\)-trees. Theoretical Computer Science, 410, 688–695.

    Article  Google Scholar 

  16. Goldreich, O. (2017). Introduction to Property Testing. Cambridge: Cambridge University Press.

    Book  Google Scholar 

  17. Goldreich, O., & Ron, D. (1997). Property testing in bounded degree graphs: Proc. STOC, 1997, 406–415.

    Article  Google Scholar 

  18. Goldreich, O., & Ron, D. (2011). On proximity-oblivious testing. SIAM Journal on Computing, 40(02), 534–566.

    Article  Google Scholar 

  19. Goldreich, O., & Trevisan, L. (2001). Three theorems regarding testing graph properties. In Proceedings FOCS 2001 (pp. 460–469) (Journal version: Random Structures & Algorithms, Wiley, Vol. 23, Issue 1, pp. 23–57, (2003)).

  20. Hassidim, A., Kelner, J.A., Nguyen, H.N., & Onak, K. (2009). Local graph partitions for approximation and testing. In: Proceedings FOCS 2009 (pp. 22–31). IEEE.

  21. Ito, H. (2015). Every property is testable on a natural class of scale-free multigraphs, Cornell University (pp. 1–12). arXiv:1504.00766

  22. Ito, H. (2016). Every property is testable on a natural class of scale-free multigraphs. In: Proceedings of ESA 2016, LIPICS (ISBN 978-3-95977-005-7) (vol. 49, pp. 21:2–21:15).

  23. Ito, H., & Iwama, K. (2009). Enumeration of isolated cliques and pseudo-cliques. In ACM Transactions on Algorithms (vol. 5, Issue 4, Article 40, pp. 1–13).

  24. Ito, H., Iwama, K., & Osumi, T. (2005). Linear-time enumeration of isolated cliques. In Proceedings ESA2005, LNCS (vol. 3669, pp. 119–130). Springer.

  25. Kawarabayashi, K., & Reed, B. (2010). A separator theorem in minor-closed classes. Proceedings of FOCS, 2010, 153–162.

    Google Scholar 

  26. Kleinberg, J., & Lawrence, S. (2001). The structure of the web. Science, 294, 1894–1895.

    Article  Google Scholar 

  27. Kusumoto, M., & Yoshida, Y. (2014). Testing forest-isomorphizm in the adjacency list model. In Proceedings of ICALP2014 (1), LNSC 8572 (pp. 763–774).

  28. Levi, R., & Ron, D. (2013). A quasi-polynomial time partition oracle for graphs with an excluded mino. In Proceedings of ICALP 2013 (1), LNCS, 7965 (pp. 709–720). Springer. (Journal version: ACM Transactions on Algorithms, Vol. 11, No. 3, Article 24, pp. 1–13, (2014)).

  29. Mahdian, M., & Xu, Y. (2007). Stochastic Kronecker graphs. In Proc. WAW 2007, LNCS, 4863. (pp. 179–186). Springer.

  30. Marko, S., & Ron, D. (2009). Approximating the distance to properties in bounded-degree and general sparse graphs. In ACM Transactions on Algorithms (Vol. 5, Issue. 2, Article No. 22).

  31. Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45, 167–256.

    Google Scholar 

  32. Newman, I., & Sohler, C. (2011). Every property of hyperfinite graphs is testable. In PROC. STOC 2011, ACM (pp. 675–784) (Journal version: SIAM J. Comput., Vol. 42, No. 3, pp. 1095–1112, (2013)).

  33. Robertson, N., & Seymour, P.D. (1983–2012). Graph Minors I–XXII. Journal of Combinatorial Theory, Series B.

  34. Shigezumi, T., Uno, Y., & Watanabe, O. (2011). A new model for a scale-free hierarchical structure of isolated cliques. Journal of Graph Algorithms and Applications, 15(5), 661–682.

    Article  Google Scholar 

  35. Szemerédi, E. (1978). Regular partitions of graphs. In J. C. Bermond, J. C. Fournier, M. Las Vergnas, & D. Sotteau (Eds.) Colloq. Internat. CNRS, Paris (pp. 399–401).

  36. Sárközy, G.N., Song, F., Szemerédi, E., & Trivedi, S. (2012). A practical regularity partitioning algorithm and its applications in clustering. (pp. 1–13) Cornell University, Sept. 28. arXiv:1209.6540v1.

  37. Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442.

    Article  Google Scholar 

  38. Yoshida, Y., & Ito, H. (2008). Property testing on k-vertex connectivity of graphs. In: Proc. ICALP 2008, (1), LNCS, #5125 (pp. 539–550). Springer (Journal version: Algorithmica, Vol. 62, No. 3–4, pp. 701–712, (2012)).

  39. Yoshida, Y., Yamamoto, M., & Ito, H. (2009). An improved constant-time approximation algorithm for maximum matchings. In Proceedings of STOC 2009 (pp. 225–234). (Journal version: SIAM J. Comput., Vol. 41, No. 4, pp. 1074–1093, (2012)).

  40. Zhang, Z., Rong, L., & Comellas, F. (2006). High-dimensional random apollonian networks. Physica A: Statistical Mechanics and its Applications, 364, 610–618.

    Article  Google Scholar 

Download references

Acknowledgements

The author thanks Professor Ilan Newman of the University of Haifa, Israel, Associate Professor Yuichi Yoshida of the National Institute of Informatics, Japan, and Associate Professor Suguru Tamaki of University of Hyogo, Japan for their helpful advice.

Author information

Authors and Affiliations

  1. School of Informatics and Engineering, The University of Electro-Communications, Tokyo, 182-0021, Japan

    Hiro Ito

Authors
  1. Hiro Ito
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hiro Ito.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work is partially supported by CREST, JST, Grant No. JPMJCR1402 and KAKENHI, JSPS, Grant No. 15K11985.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ito, H. What Graph Properties Are Constant-Time Testable?. Rev Socionetwork Strat 13, 101–121 (2019). https://doi.org/10.1007/s12626-019-00054-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12626-019-00054-0

Keywords

Search

Navigation