{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:58Z","timestamp":1750220638957,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T00:00:00Z","timestamp":1604793600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["671\/13 and 1146\/18"],"award-info":[{"award-number":["671\/13 and 1146\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>Following Newman (2010), we initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph. The tester is given free access to a base graph<jats:italic>G<\/jats:italic>= ([<jats:italic>n<\/jats:italic>],<jats:italic>E<\/jats:italic>) and oracle access to a function<jats:italic>f<\/jats:italic>:<jats:italic>E<\/jats:italic>\u2192 {0, 1} that represents a subgraph of<jats:italic>G<\/jats:italic>. The tester is required to distinguish between subgraphs that possess a predetermined property and subgraphs that are far from possessing this property.<\/jats:p><jats:p>We focus on bounded-degree base graphs and on the relation between testing graph properties in the subgraph model and testing the same properties in the bounded-degree graph model. We identify cases in which testing is significantly easier in one model than in the other as well as cases in which testing has approximately the same complexity in both models. Our proofs are based on the design and analysis of efficient testers and on the establishment of query-complexity lower bounds.<\/jats:p>","DOI":"10.1145\/3428675","type":"journal-article","created":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T11:52:50Z","timestamp":1604836370000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Subgraph Testing Model"],"prefix":"10.1145","volume":"12","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,8]]},"reference":[{"volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC\u201990)","author":"Alon N.","key":"e_1_2_1_1_1","unstructured":"N. Alon , P. D. Seymour , and R. Thomas . 1990. A separator theorem for graphs with an excluded minor and its applications . In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC\u201990) . 293--299. N. Alon, P. D. Seymour, and R. Thomas. 1990. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC\u201990). 293--299."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445445"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.10.018"},{"volume-title":"Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS\u201902)","author":"Bogdanov A.","key":"e_1_2_1_4_1","unstructured":"A. Bogdanov , K. Obata , and L. Trevisan . 2002. A lower bound for testing 3-colorability in bounded-degree graphs . In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS\u201902) . 93--102. A. Bogdanov, K. Obata, and L. Trevisan. 2002. A lower bound for testing 3-colorability in bounded-degree graphs. In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS\u201902). 93--102."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1002\/rsa.20826","article-title":"Planar graphs: Random walks and bipartiteness testing","volume":"55","author":"Czumaj A.","year":"2019","unstructured":"A. Czumaj , M. Monemizadeh , K. Onak , and C. Sohler . 2019 . Planar graphs: Random walks and bipartiteness testing . Rand. Struct. Algor. 55 , 1 (2019), 104 -- 124 . A. Czumaj, M. Monemizadeh, K. Onak, and C. Sohler. 2019. Planar graphs: Random walks and bipartiteness testing. Rand. Struct. Algor. 55, 1 (2019), 104--124.","journal-title":"Rand. Struct. Algor."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070681831"},{"volume-title":"Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM\u201911)","author":"Edelman A.","key":"e_1_2_1_7_1","unstructured":"A. Edelman , A. Hassidim , H. N. Nguyen , and K. Onak . 2011. An efficient partitioning oracle for bounded-treewidth graphs . In Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM\u201911) . 530--541. A. Edelman, A. Hassidim, H. N. Nguyen, and K. Onak. 2011. An efficient partitioning oracle for bounded-treewidth graphs. In Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM\u201911). 530--541."},{"key":"e_1_2_1_8_1","unstructured":"G. Elek. 2006. The combinatorial cost. arXiv:math\/0608474. Retrieved from https:\/\/arxiv.org\/abs\/math\/0608474. G. Elek. 2006. The combinatorial cost. arXiv:math\/0608474. Retrieved from https:\/\/arxiv.org\/abs\/math\/0608474."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1841364.1841367"},{"volume-title":"Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP\u201912)","author":"Feige U.","key":"e_1_2_1_10_1","unstructured":"U. Feige and S. Jozeph . 2012. Universal factor graphs . In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP\u201912) . 339--350. U. Feige and S. Jozeph. 2012. Universal factor graphs. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP\u201912). 339--350."},{"key":"e_1_2_1_11_1","article-title":"On the query complexity of testing orientations for being Eulerian","volume":"8","author":"Fischer E.","year":"2012","unstructured":"E. Fischer , O. Lachish , A. Matsliah , I. Newman , and O. Yahalom . 2012 . On the query complexity of testing orientations for being Eulerian . ACM Trans. Algor. 8 , 2 (2012), 15:1--15:41. E. Fischer, O. Lachish, A. Matsliah, I. Newman, and O. Yahalom. 2012. On the query complexity of testing orientations for being Eulerian. ACM Trans. Algor. 8, 2 (2012), 15:1--15:41.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Forster S.","year":"2046","unstructured":"S. Forster , D. Nanongkai , L. Yang , T. Saranurak , and S. Yingchareonthawornchai . 2020. Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms . In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920) , Shuchi Chawla (Ed.). SIAM , 2046 --2065. DOI:https:\/\/doi.org\/10.1137\/1.9781611975994.126 10.1137\/1.9781611975994.126 S. Forster, D. Nanongkai, L. Yang, T. Saranurak, and S. Yingchareonthawornchai. 2020. Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920), Shuchi Chawla (Ed.). SIAM, 2046--2065. DOI:https:\/\/doi.org\/10.1137\/1.9781611975994.126"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"volume-title":"Introduction to Property Testing","author":"Goldreich O.","key":"e_1_2_1_14_1","unstructured":"O. Goldreich . 2017. Introduction to Property Testing . Cambridge University Press . O. Goldreich. 2017. Introduction to Property Testing. Cambridge University Press."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/100789646"},{"key":"e_1_2_1_19_1","volume-title":"Electr. Colloq. Comput. Complex. 25","author":"Goldreich O.","year":"2018","unstructured":"O. Goldreich and D. Ron . 2018. The subgraph testing model . Electr. Colloq. Comput. Complex. 25 , 45 ( 2018 ). Technical report: TR18-045. O. Goldreich and D. Ron. 2018. The subgraph testing model. Electr. Colloq. Comput. Complex. 25, 45 (2018). Technical report: TR18-045."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118755.3119001"},{"key":"e_1_2_1_21_1","volume-title":"Electr. Colloq. Comput. Complex. 153","author":"Halevy S.","year":"2005","unstructured":"S. Halevy , O. Lachish , I. Newman , and D. Tsur . 2005. Testing orientation properties . Electr. Colloq. Comput. Complex. 153 ( 2005 ). S. Halevy, O. Lachish, I. Newman, and D. Tsur. 2005. Testing orientation properties. Electr. Colloq. Comput. Complex. 153 (2005)."},{"volume-title":"Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS\u201909)","author":"Hassidim A.","key":"e_1_2_1_22_1","unstructured":"A. Hassidim , J. Kelner , H. Nguyen , and K. Onak . 2009. Local graph partitions for approximation and testing . In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS\u201909) . 22--31. A. Hassidim, J. Kelner, H. Nguyen, and K. Onak. 2009. Local graph partitions for approximation and testing. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS\u201909). 22--31."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608018"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"e_1_2_1_25_1","article-title":"A quasi-polynomial time partition oracle for graphs with an excluded minor","volume":"11","author":"Levi R.","year":"2015","unstructured":"R. Levi and D. Ron . 2015 . A quasi-polynomial time partition oracle for graphs with an excluded minor . ACM Trans. Algor. 11 , 3 (2015), 24:1--24:13. R. Levi and D. Ron. 2015. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Trans. Algor. 11, 3 (2015), 24:1--24:13.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_26_1","first-page":"177","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton R. J.","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan . 1979 . A separator theorem for planar graphs . SIAM J. Discr. Math. 36 , 2 (1979), 177 -- 189 . R. J. Lipton and R. E. Tarjan. 1979. A separator theorem for planar graphs. SIAM J. Discr. Math. 36, 2 (1979), 177--189.","journal-title":"SIAM J. Discr. Math."},{"volume-title":"Property Testing: Current Research and Surveys, LNCS 6390","author":"Newman I.","key":"e_1_2_1_27_1","unstructured":"I. Newman . 2010. Property testing of massively parametrized problems\u2014A survey . In Property Testing: Current Research and Surveys, LNCS 6390 , O. Goldreich (Ed.). Springer , 142--157. I. Newman. 2010. Property testing of massively parametrized problems\u2014A survey. In Property Testing: Current Research and Surveys, LNCS 6390, O. Goldreich (Ed.). Springer, 142--157."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/120890946"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013.abs"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202286"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125643"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428675","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:59Z","timestamp":1750197719000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,8]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3428675"],"URL":"https:\/\/doi.org\/10.1145\/3428675","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,11,8]]},"assertion":[{"value":"2020-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}