skip to main content
research-article

Approximating the distance to properties in bounded-degree and general sparse graphs

Published: 23 March 2009 Publication History

Abstract

We address the problem of approximating the distance of bounded-degree and general sparse graphs from having some predetermined graph property P. That is, we are interested in sublinear algorithms for estimating the fraction of edge modifications (additions or deletions) that must be performed on a graph so that it obtains P. This fraction is taken with respect to a given upper bound m on the number of edges. In particular, for graphs with degree bound d over n vertices, m = dn. To perform such an approximation the algorithm may ask for the degree of any vertex of its choice, and may ask for the neighbors of any vertex.
The problem of estimating the distance to having a property was first explicitly addressed by Parnas et al. [2006]. In the context of graphs this problem was studied by Fischer and Newman [2007] in the dense graphs model. In this model the fraction of edge modifications is taken with respect to n2, and the algorithm may ask for the existence of an edge between any pair of vertices of its choice. Fischer and Newman showed that every graph property that has a testing algorithm in this model, with query complexity independent of the size of the graph, also has a distance approximation algorithm with query complexity that is independent of the size of graph.
In this work we focus on bounded-degree and general sparse graphs, and give algorithms for all properties shown to have efficient testing algorithms by Goldreich and Ron [2002]. Specifically, these properties are k-edge connectivity, subgraph freeness (for constant-size subgraphs), being an Eulerian graph, and cycle freeness. A variant of our subgraph-freeness algorithm approximates the size of a minimum vertex cover of a graph in sublinear time. This approximation improves on a recent result of Parnas and Ron [2007].

References

[1]
Ailon, N., Chazelle, B., Comandur, S., and Liu, D. 2007. Estimating the distance to a monotone function. Random Structures Algor. 31, 3, 371--383.
[2]
Alon, N., Kaufman, T., Krivilevich, M., and Ron, D. 2008. Testing triangle-freeness in general graphs. SIAM J. Discrete Math. 22, 2, 786--819.
[3]
Alon, N., Shapira, A., and Sudakov, B. 2005. Additive approximation for edge-deletion problems. In Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS), 419--428. To appear in Annals of Mathematics.
[4]
Bogdanov, A., Obata, K., and Trevisan, L. 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), 93--102.
[5]
Chazelle, B., Rubinfeld, R., and Trevisan, L. 2005. Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput. 34, 6, 1370--1379.
[6]
Feige, U. 2006. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput. 35, 4, 964--984.
[7]
Fischer, E., and Fortnow, L. 2005. Tolerant versus intolerant testing for boolean properties. Theory Comput. 2, 173--183.
[8]
Fischer, E., and Newman, I. 2007. Testing versus estimation of graph properties. SIAM J. Comput. 37, 2, 482--501.
[9]
Goldreich, O., Goldwasser, S., and Ron, D. 1998. Property testing and its connection to learning and approximation. J. ACM 45, 4, 653--750.
[10]
Goldreich, O., and Ron, D. 2002. Property testing in bounded degree graphs. Algorithmica 32, 2, 302--343.
[11]
Goldreich, O., and Ron, D. 2008. Approximating average parameters of graphs. Random Structures Algor. 32, 4, 473--493.
[12]
Gomory, R. E., and Hu, T. C. 1961. Multi-Terminal network flows. SIAM J. Appl. Math. 9, 4, 551--560.
[13]
Guruswami, V., and Rudra, A. 2005. Tolerant locally testable codes. In Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM), 306--317.
[14]
Gusfield, D. 1990. Very simple methods for all pairs network flow analysis. SIAM J. Comput. 19, 1, 143--155.
[15]
Håstad, J. 2001. Some optimal inapproximability results. J. ACM 48, 4, 798--859.
[16]
Karger, D. 1993. Global min-cuts in RNC and other ramifications of a simple mincut algorithm. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 21--30.
[17]
Kaufman, T., Krivelevich, M., and Ron, D. 2004. Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput. 33, 6, 1441--1483.
[18]
Kuhn, F., Moscibroda, T., and Wattenhofer, R. 2006. The price of being near-sighted. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 980--989.
[19]
Luby, M. 1986. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 2, 1036--1055.
[20]
Naor, D., Gusfield, D., and Martel, C. 1997. A fast algorithm for optimally increasing the edge connectivity. SIAM J. Comput. 26, 4, 1139--1165.
[21]
Parnas, M., and Ron, D. 2002. Testing the diameter of graphs. Random Structures Algor. 20, 2, 165--183.
[22]
Parnas, M. and Ron, D. 2007. On approximating the minimum vertex cover in sublinear time and the connection to distributed algorithms. Theor. Comput. Sci. 381, 1-3, 183--186.
[23]
Parnas, M., Ron, D., and Rubinfeld, R. 2006. Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72, 6, 1012--1042.
[24]
Yanakakis, M. 1981. Edege-deletion problems. SIAM J. Comput. 10, 2, 297--309.

Cited By

View all
  • (2024)Sample-Based Distance-Approximation for Subsequence-FreenessAlgorithmica10.1007/s00453-024-01233-486:8(2519-2556)Online publication date: 13-May-2024
  • (2024)Testing versus estimation of graph properties, revisitedRandom Structures & Algorithms10.1002/rsa.2122165:3(460-487)Online publication date: 26-Apr-2024
  • (2023)Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00095(1563-1588)Online publication date: 6-Nov-2023
  • Show More Cited By

Index Terms

  1. Approximating the distance to properties in bounded-degree and general sparse graphs

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Transactions on Algorithms
      ACM Transactions on Algorithms  Volume 5, Issue 2
      March 2009
      235 pages
      ISSN:1549-6325
      EISSN:1549-6333
      DOI:10.1145/1497290
      Issue’s Table of Contents
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 23 March 2009
      Accepted: 01 November 2008
      Received: 01 September 2006
      Published in TALG Volume 5, Issue 2

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. Sublinear approximation algorithms
      2. distance approximation
      3. graph properties
      4. property testing

      Qualifiers

      • Research-article
      • Research
      • Refereed

      Funding Sources

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

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

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Sample-Based Distance-Approximation for Subsequence-FreenessAlgorithmica10.1007/s00453-024-01233-486:8(2519-2556)Online publication date: 13-May-2024
      • (2024)Testing versus estimation of graph properties, revisitedRandom Structures & Algorithms10.1002/rsa.2122165:3(460-487)Online publication date: 26-Apr-2024
      • (2023)Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00095(1563-1588)Online publication date: 6-Nov-2023
      • (2022)A Lower Bound on Cycle-Finding in Sparse DigraphsACM Transactions on Algorithms10.1145/341797918:4(1-23)Online publication date: 10-Oct-2022
      • (2022)Graph Family Characterization using the Path Length Array2022 11th International Conference on System Modeling & Advancement in Research Trends (SMART)10.1109/SMART55829.2022.10046959(1018-1022)Online publication date: 16-Dec-2022
      • (2021)On efficient distance approximation for graph propertiesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458162(1618-1637)Online publication date: 10-Jan-2021
      • (2021)Approximating the distance to monotonicity of Boolean functionsRandom Structures & Algorithms10.1002/rsa.2102960:2(233-260)Online publication date: 24-Jun-2021
      • (2020)On Approximating the Number of $k$-Cliques in Sublinear TimeSIAM Journal on Computing10.1137/18M117670149:4(747-771)Online publication date: 14-Jul-2020
      • (2020)Local Algorithms for Sparse Spanning GraphsAlgorithmica10.1007/s00453-019-00612-682:4(747-786)Online publication date: 1-Apr-2020
      • (2019)Tolerant Junta Testing and the Connection to Submodular Optimization and Function IsomorphismACM Transactions on Computation Theory10.1145/333778911:4(1-33)Online publication date: 22-Jul-2019
      • Show More Cited By

      View Options

      Login options

      Full Access

      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