Finding cycles and trees in sublinear time. Issue 2 (22nd August 2012)

• Record Type: Journal Article
• Authors: Czumaj, Artur; Goldreich, Oded; Ron, Dana; Seshadhri, C.; Shapira, Asaf; Sohler, Christian
• Is Part Of: Random structures & algorithms. Volume 45:Issue 2(2014)
• Page Start: 139
• Page End: 184
• Publication Date: 2012-08-22
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20462
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>ABSTRACT</title> <p>We present sublinear‐time (randomized) algorithms for finding simple cycles of length at least <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzj55" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20462:rsa20462-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> and tree‐minors in bounded‐degree graphs. The complexity of these algorithms is related to the distance of the graph from being <italic>C</italic><sub><italic>k</italic></sub>‐minor free (resp., free from having the corresponding tree‐minor). In particular, if the graph is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzjds" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20462:rsa20462-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Ω</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐far from being cycle‐free (i.e., a constant fraction of the edges must be deleted to make the graph cycle‐free), then the algorithm finds a cycle of polylogarithmic length in time <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzjf9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20462:rsa20462-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mover accent="true"><mml:mi>O</mml:mi><mml:mo>˜</mml:mo></mml:mover><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>N</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, where <italic>N</italic> denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors.</p> <p>The foregoing results are the outcome of our study of the complexity of <italic>one‐sided error</italic> property testing algorithms in the bounded‐degree graphs model. For example, we show that cycle‐freeness of <italic>N</italic>‐vertex graphs can be tested with one‐sided error within time complexity <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzj97" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20462:rsa20462-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mover accent="true"><mml:mi>O</mml:mi><mml:mo>˜</mml:mo></mml:mover><mml:mo stretchy="false">(</mml:mo><mml:mtext>poly</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mo>ϵ</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>·</mml:mo><mml:msqrt><mml:mi>N</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, where <italic>∊</italic> denotes the proximity parameter. This matches the known <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzjbr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20462:rsa20462-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Ω</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>N</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> query lower bound for one‐sided error cycle‐freeness testing, and contrasts with the fact that any minor‐free property admits a <italic>two‐sided error</italic> tester of query complexity that only depends on <italic>∊</italic>. We show that the same upper bound holds for testing whether the input graph has a simple cycle of length at least <italic>k</italic>, for any <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzjqf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20462:rsa20462-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. On the other hand, for any fixed tree <italic>T</italic>, we show that <italic>T</italic>‐minor freeness has a one‐sided error tester of query complexity that only depends on the proximity parameter <italic>∊</italic>.</p> <p>Our algorithm for finding cycles in bounded‐degree graphs extends to general graphs, where distances are measured with respect to the actual number of edges. Such an extension is not possible with respect to finding tree‐minors in <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghv4nzjnd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20462:rsa20462-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mi>N</mml:mi></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> complexity. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 139–184, 2014</p> </abstract>