skip to main content
10.5555/1347082.1347214acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

Comparing the strength of query types in property testing: the case of testing k-colorability

Published: 20 January 2008 Publication History

Abstract

We study the power of four query models in the context of property testing in general graphs, where our main case study is the problem of testing k-colorability. Two query types, which have been studied extensively in the past, are pair queries and neighbor queries. The former corresponds to asking whether there is an edge between any particular pair of vertices, and the latter to asking for the i'th neighbor of a particular vertex. We show that while for pair queries, testing k-colorability requires a number of queries that is a monotone decreasing function in the average degree d, the query complexity in the case of neighbor queries remains roughly the same for every density and for large values of k. We also consider a combined model that allows both types of queries, and we propose a new, stronger, query model, which is related to the field of Group Testing. We give one-sided error upper and lower bounds for all the models, where the bounds are nearly tight for three of the models. In some of the cases our lower bounds extend to two-sided error algorithms.
The problem of testing k-colorability was previously studied in the contexts of dense and sparse graphs, and in our proofs we unify approaches from those cases, and also provide some new tools and techniques which may be of independent interest.

References

[1]
N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. Combinatorica, 20:451--476, 2000.
[2]
N. Alon, E. Fischer, I. Newman, and A. Shapira. A combinatorial characterization of the testable graph properties: it's all about regularity. In Proc. of the 38 ACM STOC, pages 251--260, 2007.
[3]
N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle freeness in general graphs. In Proceedings of the 17th Symposium on Discrete Algorithms (SODA'06), pages 279--288, 2006.
[4]
N. Alon and M. Krivelevich. Testing k-colorability. SIAM Journal on Discrete Math, 15(2):211--227, 2002.
[5]
N. Alon and J. Spencer. The probablistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
[6]
I. Ben-Eliezer, T. Kaufman, M. Krivelevich, and D. Ron. Comparing the strength of query types in property testing: The case of testing k-colorability. Manuscript, available from http://www.eng.tau.ac.il/~danar/papers.html, 2007.
[7]
A. Bogdanov, K. Obata, and L. Trevisan. A lower bound for testing 3-colorability in bounded degree graphs. In Proceedings of the Forty-Third Annual Symposium on Foundations of Computer Science, pages 93--102, 2002.
[8]
A. Czumaj, A. Shapira, and C. Sohler. Testing hereditary properties of non-expanding bounded-degree graphs. Manuscript, 2007.
[9]
D. Du and F. Hwang. Combinatorial group testing and its applications. World Scientific, 1993.
[10]
R. Duke and V. Rödl. On graphs with small subgraphs of large chromatic number. Graphs Combin, 1:91--96, 1985.
[11]
E. Fischer. The art of uninformed decisions: A primer to property testing. The Bulletin of the European Association for Theoretical Computer Science, 75:97--126, 2001.
[12]
O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. JACM, 45(4):653--750, 1998.
[13]
O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302--343, 2002.
[14]
T. Kaufman, M. Krivelevich, and D. Ron. Tight bounds for testing bipartiteness in general graphs. SIAM Journal on Computing, 33(6):1441--1483, 2004.
[15]
M. Parnas and D. Ron. Testing the diameter of graphs. Random Structures and Algorithms, 20(2):165--183, 2002.
[16]
D. Ron. Property testing. In Handbook of Randomized Computing, Volume II, Chapter 15, pages 597--649. Edited by S. Rajasekaran, P. M. Pardalos, J. H. Reif and J. Rolim, Kluwer Academic Publishers.
[17]
R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252--271, 1996.
[18]
D. West. Introduction to Graph Theory. Prentice Hall, 2000.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media