Abstract
A graph property is monotone if it is closed under removal of vertices and edges. We consider the following algorithmic problem, called the edge-deletion problem; given a monotone property P and a graph G, compute the smallest number of edge deletions that are needed in order to turn G into a graph satisfying P. We denote this quantity by E′ P (G). Our first result states that the edge-deletion problem can be efficiently approximated for any monotone property.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon, N.: Ranking Tournaments. SIAM J. Discrete Math. 20, 137–142 (2006)
Alon, N., Duke, R.A., Lefmann, H., Rödl, V., Yuster, R.: The algorithmic aspects of the Regularity Lemma. In: Proc. 33rd IEEE FOCS, pp. 473–481. IEEE, Los Alamitos (1992); also J. of Algorithms 16, 80-109 (1994)
Alon, N., Fernandez de la Vega, W., Kannan, R., Karpinski, M.: Random Sampling and Approximation of MAX-CSP Problems. In: Proc. of 34th ACM STOC, pp. 232–239. ACM Press, New York (2002); also JCSS 67, 212-243 (2003)
Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs. In: Proc. of 40th FOCS, pp. 656–666. IEEE, Los Alamitos (1999); also Combinatorica 20, 451-476 (2000)
Alon, N., Shapira, A.: Every monotone graph property is testable. In: Proc. of 37th STOC, pp. 128–137 (2005)
Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of graph problems. In: Proc. of 28th STOC (1995); also: JCSS 58, 193-210 (1999)
Borgs, C., Chayes, J., Lovász, L., Sós, V.T., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing. In: STOC 2006 (to appear, 2006)
Frieze, A., Kannan, R.: The regularity lemma and approximation schemes for dense problems. In: Proc. of 37th FOCS, pp. 12–20 (1996)
Kohayakawa, Y., Rödl, V., Thoma, L.: An optimal algorithm for checking regularity. SIAM J. on Computing 32(5), 1210–1235 (2003)
Komlós, J., Simonovits, M.: Szemerédi’s Regularity Lemma and its applications in graph theory. In: Miklós, D., Sós, V.T., Szönyi, T. (eds.) Combinatorics, Paul Erdös is Eighty. János Bolyai Math. Soc., Budapest, vol. II, pp. 295–352 (1996)
Kövari, T., Sós, V.T., Turán, P.: On a problem of K. Zarankiewicz. Colloquium Math. 3, 50–57 (1954)
Szemerédi, E.: Regular partitions of graphs. In: Bermond, J.C., Fournier, J.C., Las Vergnas, M., Sotteau, D. (eds.) Proc. Colloque Inter. CNRS, pp. 399–401 (1978)
Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10, 297–309 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alon, N., Shapira, A., Sudakov, B. (2006). Additive Approximation for Edge-Deletion Problems (Abstract). In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds) Automata, Languages and Programming. ICALP 2006. Lecture Notes in Computer Science, vol 4051. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11786986_1
Download citation
DOI: https://doi.org/10.1007/11786986_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35904-3
Online ISBN: 978-3-540-35905-0
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science