{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T17:38:04Z","timestamp":1790185084886,"version":"4.1.0"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs and one most suitable for bounded-degree graphs. Roughly speaking, dense graphs can be tested for bipartiteness with constant complexity, while the complexity of testing bounded-degree graphs is $\\tilde{\\Theta}(\\sqrt{n})$, where n is the number of vertices in the graph (and $\\tilde{\\Theta}(f(n))$ means $\\Theta(f(n)\\cdot{\\rm polylog}(f(n)))$). Thus there is a large gap between the complexity of testing in the two cases.<\/jats:p>\n                  <jats:p>In this work we bridge the gap described above. In particular, we study the problem of testing bipartiteness in a model that is suitable for all densities. We present an algorithm whose complexity is $\\tilde{O}(\\min(\\sqrt{n},n^2\/m))$, where m is the number of edges in the graph, and we match it with an almost tight lower bound.<\/jats:p>","DOI":"10.1137\/s0097539703436424","type":"journal-article","created":{"date-parts":[[2004,9,20]],"date-time":"2004-09-20T21:00:29Z","timestamp":1095714029000},"page":"1441-1483","source":"Crossref","is-referenced-by-count":67,"title":["Tight Bounds for Testing Bipartiteness in General Graphs"],"prefix":"10.1137","volume":"33","author":[{"given":"Tali","family":"Kaufman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199358655"},{"key":"R4","unstructured":"N. Alon and A. Shapira,\n                      Testing subgraph in directed graphs\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 700\u2013709."},{"key":"R5","volume-title":"The probabilistic method","author":"Alon Noga","year":"1992"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10023.abs"},{"key":"R7","unstructured":"A. Bogdanov, K. Obata, and L. Trevisan,\n                      A lower bound for testing 3\u2010colorability in bounded\u2010degree graphs\n                      , in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 93\u2013102."},{"key":"R8","unstructured":"A. Bogdanov and L. Trevisan,\n                      Lower Bounds for Testing Bipartiteness in Dense Graphs\n                      , Tech. report TR02\u2010064, Electronic Colloquium on Computational Complexity (ECCC), 2002."},{"key":"R8","unstructured":"Available from http:\/\/www.eccc.uni\u2010trier.de\/eccc\/."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70495-3"},{"key":"R10","unstructured":"A. Czumaj and C. Sohler,\n                      Abstract combinatorial programs and efficient property testers\n                      , in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 83\u201392."},{"key":"R11","unstructured":"U. Feige,\n                      On sums of independent random variables with unbounded variance, and estimating the average degree in a graph\n                      , in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 594\u2013603."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"R15","unstructured":"O. Goldreich and D. Ron,\n                      On Estimating the Average Degree of a Graph\n                      , Tech. report TR04\u2010013, Electronic Colloquium on Computational Complexity (ECCC), 2004."},{"key":"R15","unstructured":"Available from http:\/\/www.eccc.uni\u2010trier.de\/eccc\/."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"R17","unstructured":"A. Lubotzky, R. Phillips, and P. Sarnak,\n                      Explicit expanders and the Ramanujan conjectures\n                      , in Proceedings of the 18th Annual ACM Symposium on Theory of Computing, ACM, New York, 1986, pp. 240\u2013246."},{"key":"R18","first-page":"71","volume":"9","author":"Margulis G.","year":"1973","journal-title":"Problemy Pereda\u010di Informacii"},{"key":"R19","unstructured":"M. Mihail,\n                      Conductance and convergence of Markov chains: A combinatorial treatment of expanders\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1989, pp. 526\u2013531."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013.abs"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R22","unstructured":"A. Yao,\n                      Probabilistic computation: Towards a unified measure of complexity\n                      , in Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1977, pp. 222\u2013227."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703436424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:48Z","timestamp":1787336268000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703436424"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0097539703436424"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703436424","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}