{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T10:46:03Z","timestamp":1776681963931,"version":"3.51.2"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,14]],"date-time":"2017-12-14T00:00:00Z","timestamp":1513209600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS KAKENHI","award":["JP25240002, JP16H02782, JP17H04676"],"award-info":[{"award-number":["JP25240002, JP16H02782, JP17H04676"]}]},{"name":"JST ERATO","award":["JPMJER1305"],"award-info":[{"award-number":["JPMJER1305"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>\n            This article studies property testing for NP optimization problems with parameter\n            <jats:italic>k<\/jats:italic>\n            under the general graph model with an augmentation of random edge sampling capability. It is shown that a variety of such problems, including\n            <jats:italic>k<\/jats:italic>\n            -Vertex Cover,\n            <jats:italic>k<\/jats:italic>\n            -Feedback Vertex Set,\n            <jats:italic>k<\/jats:italic>\n            -Multicut,\n            <jats:italic>k<\/jats:italic>\n            -Path-Free, and\n            <jats:italic>k<\/jats:italic>\n            -Dominating Set, are constant-query testable if\n            <jats:italic>k<\/jats:italic>\n            is constant. It should be noted that the first four problems are fixed parameter tractable (FPT) and it turns out that algorithmic techniques for their FPT algorithms (branch-and-bound search, color coding, etc.)\u00a0are also useful for our testers.\n            <jats:italic>k<\/jats:italic>\n            -Dominating Set is\n            <jats:italic>W<\/jats:italic>\n            [2]-hard, but we can still test the property with a constant number of queries, since the definition of \u03b5-farness makes the problem trivial for non-sparse graphs that are the source of hardness for the original optimization problem. We also consider\n            <jats:italic>k<\/jats:italic>\n            -Odd Cycle Transversal, which is another well-known FPT problem, but we only give a sublinear-query tester when\n            <jats:italic>k<\/jats:italic>\n            is a constant.\n          <\/jats:p>","DOI":"10.1145\/3155294","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T13:39:24Z","timestamp":1513345164000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Testability"],"prefix":"10.1145","volume":"9","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[{"name":"Kyoto University, Kyoto, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/060667177"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/07067917X"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/050633445"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Ben-Eliezer I.","unstructured":"I. Ben-Eliezer , T. Kaufman , M. Krivelevich , and D. Ron . 2008. Comparing the strength of query types in property testing: The case of testing -colorability . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . 1213--1222. I. Ben-Eliezer, T. Kaufman, M. Krivelevich, and D. Ron. 2008. Comparing the strength of query types in property testing: The case of testing -colorability. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 1213--1222."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.10.018"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00242-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01270385"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.69"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Vol. 3. Springer.   R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Vol. 3. Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1980617"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v32:4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.77"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629508"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/120890946"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007433"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Onak K.","unstructured":"K. Onak , D. Ron , M. Rosen , and R. Rubinfeld . 2012. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size . In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912) . 1123--1131. K. Onak, D. Ron, M. Rosen, and R. Rubinfeld. 2012. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912). 1123--1131."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000029"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791075"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the International Colloquium of the CNRS. 399--401","author":"Szemer\u00e9di E.","year":"1978","unstructured":"E. Szemer\u00e9di . 1978 . Regular partitions of graphs . In Proceedings of the International Colloquium of the CNRS. 399--401 . E. Szemer\u00e9di. 1978. Regular partitions of graphs. In Proceedings of the International Colloquium of the CNRS. 399--401."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.01.045"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/110828691"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3155294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:28Z","timestamp":1750213588000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,14]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3155294"],"URL":"https:\/\/doi.org\/10.1145\/3155294","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,14]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}