Document Open Access Logo

Faster Property Testers in a Variation of the Bounded Degree Model

Authors Isolde Adler , Polly Fahey

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.7.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Isolde Adler
  • University of Leeds, School of Computing, UK
Polly Fahey
  • University of Leeds, School of Computing, UK

Cite As Get BibTex

Isolde Adler and Polly Fahey. Faster Property Testers in a Variation of the Bounded Degree Model. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSTTCS.2020.7

Abstract

Property testing algorithms are highly efficient algorithms, that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions), that are necessary to transform a graph into one with property P. Much research has focussed on the query complexity of such algorithms, i. e. the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. 
In (Adler, Harwath STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time.
In this paper we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. We also show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true.
We argue that our model is natural and our meta-theorem showing constant-time CMSO testability supports this.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Theory of computation → Database query processing and optimization (theory)
Keywords
  • Constant Time Algorithms
  • Logic and Databases
  • Property Testing
  • Bounded Degree Model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Isolde Adler and Frederik Harwath. Property testing for bounded degree databases. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume 96, page 6. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  2. Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron. Testing triangle-freeness in general graphs. SIAM Journal on Discrete Mathematics, 22(2):786-819, 2008. Google Scholar
  3. Noga Alon, Paul D. Seymour, and Robin Thomas. A separator theorem for graphs with an excluded minor and its applications. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 293-299. ACM, 1990. URL: https://doi.org/10.1145/100216.100254.
  4. Jasine Babu, Areej Khoury, and Ilan Newman. Every property of outerplanar graphs is testable. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  5. Sagi Ben-Moshe, Yaron Kanza, Eldar Fischer, Arie Matsliah, Mani Fischer, and Carl Staelin. Detecting and exploiting near-sortedness for efficient relational query evaluation. In Proceedings of the 14th International Conference on Database Theory, pages 256-267. ACM, 2011. Google Scholar
  6. Itai Benjamini, Oded Schramm, and Asaf Shapira. Every minor-closed property of sparse graphs is testable. Advances in mathematics, 223(6):2200-2218, 2010. Google Scholar
  7. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering fo+ mod queries under updates on bounded degree databases. ACM Transactions on Database Systems (TODS), 43(2):7, 2018. Google Scholar
  8. Hubie Chen and Yuichi Yoshida. Testability of homomorphism inadmissibility: Property testing meets database theory. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 365-382. ACM, 2019. Google Scholar
  9. Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In Formal Models and Semantics, pages 193-242. Elsevier, 1990. Google Scholar
  10. Bruno Courcelle and Joost Engelfriet. Graph structure and monadic second-order logic: a language-theoretic approach, volume 138. Cambridge University Press, 2012. Google Scholar
  11. Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM Transactions on Computational Logic (TOCL), 8(4):21, 2007. Google Scholar
  12. Hendrik Fichtenberger, Pan Peng, and Christian Sohler. On constant-size graphs that preserve the local structure of high-girth graphs. In Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, volume 40 of LIPIcs, pages 786-799. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.786.
  13. Hendrik Fichtenberger, Pan Peng, and Christian Sohler. Every testable (infinite) property of bounded-degree graphs contains an infinite hyperfinite subproperty. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 714-726. SIAM, 2019. Google Scholar
  14. Eldar Fischer, Johann A Makowsky, et al. On spectra of sentences of monadic second order logic with counting. Journal of Symbolic Logic, 69(3):617-640, 2004. Google Scholar
  15. Jörg Flum and Martin Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag, Berlin, Heidelberg, 2006. Google Scholar
  16. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. Google Scholar
  17. Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, and Krzysztof Onak. Local graph partitions for approximation and testing. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 22-31. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.77.
  18. Piotr Indyk, Andrew McGregor, Ilan Newman, and Krzysztof Onak. Open problems in data streams, property testing, and related topics. In Bernitoro Workshop on Sublinear Algorithms, 2011. Google Scholar
  19. Hiro Ito, Areej Khoury, and Ilan Newman. On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs. computational complexity, 29(1):1, 2020. Google Scholar
  20. Wojciech Kazana and Luc Segoufin. First-order query evaluation on structures of bounded degree. Logical Methods in Computer Science, 7(2), 2011. URL: https://doi.org/10.2168/LMCS-7(2:20)2011.
  21. Leonid Libkin. Elements of finite model theory. Springer, 2004. Google Scholar
  22. László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012. Google Scholar
  23. Ilan Newman and Christian Sohler. Every property of hyperfinite graphs is testable. SIAM Journal on Computing, 42(3):1095-1112, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact