# Additive approximation for edge-deletion problems

### Abstract

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone property $\mathcal{P}$ and a graph $G$, compute the smallest number of edge deletions that are needed in order to turn $G$ into a graph satisfying $\mathcal{P}$. We denote this quantity by $E’_{\mathcal{P}}(G)$. The first result of this paper states that the edge-deletion problem can be efficiently approximated for any monotone property.

• For any fixed $\varepsilon > 0$ and any monotone property $\mathcal{ P}$, there is a deterministic algorithm which, given a graph $G=(V,E)$ of size $n$, approximates $E’_{\mathcal{P}}(G)$ in linear time $O(|V|+|E|)$ to within an additive error of $\varepsilon n^2$.

Given the above, a natural question is for which monotone properties one can obtain better additive approximations of $E’_{\mathcal{P}}$. Our second main result essentially resolves this problem by giving a precise characterization of the monotone graph properties for which such approximations exist.

• (1)  If there is a bipartite graph that does not satisfy $\mathcal{P}$, then there is a $\delta > 0$ for which it is possible to approximate $E’_{\mathcal{P}}$ to within an additive error of $n^{2-\delta}$ in polynomial time.
• (2)  On the other hand, if all bipartite graphs satisfy $\mathcal{P}$, then for any $\delta > 0$ it is NP-hard to approximate $E’_{\mathcal{ P}}$ to within an additive error of $n^{2-\delta}$.

While the proof of (1) is relatively simple, the proof of (2) requires several new ideas and involves tools from Extremal Graph Theory together with spectral techniques. Interestingly, prior to this work it was not even known that computing $E’_{\mathcal{P}}$ precisely for the properties in (2) is NP-hard. We thus answer (in a strong form) a question of Yannakakis, who asked in 1981 if it is possible to find a large and natural family of graph properties for which computing $E’_{\mathcal{P}}$ is NP-hard.

• [Al1] N. Alon, "Ranking tournaments," SIAM J. Discrete Math., vol. 20, iss. 1, pp. 137-142, 2006.
@article {Al1, MRKEY = {2257251},   AUTHOR = {Alon, Noga},   TITLE = {Ranking tournaments},   JOURNAL = {{\rm SIAM} J. Discrete Math.},   FJOURNAL = {{\rm SIAM} Journal on Discrete Mathematics},   VOLUME = {20},   YEAR = {2006},   NUMBER = {1},   PAGES = {137--142},   ISSN = {0895-4801},   MRCLASS = {05C20 (68Q25 68R10)},   MRNUMBER = {2007h:05068},   MRREVIEWER = {Arthur H. Busch},   DOI = {10.1137/050623905},   ZBLNUMBER = {1112.05043},   }
• [ADLRY] N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, "The algorithmic aspects of the regularity lemma," J. Algorithms, vol. 16, iss. 1, pp. 80-109, 1994.
@article {ADLRY, MRKEY = {1251840},   AUTHOR = {Alon, N. and Duke, R. A. and Lefmann, H. and R{ö}dl, V. and Yuster, R.},   TITLE = {The algorithmic aspects of the regularity lemma},   JOURNAL = {J. Algorithms},   FJOURNAL = {Journal of Algorithms},   VOLUME = {16},   YEAR = {1994},   NUMBER = {1},   PAGES = {80--109},   ISSN = {0196-6774},   CODEN = {JOALDV},   MRCLASS = {05C85 (68Q25 68R10)},   MRNUMBER = {94j:05112},   MRREVIEWER = {Andrzej Ruci{ń}ski},   DOI = {10.1006/jagm.1994.1005},   ZBLNUMBER = {0794.05119},   }
• [ADKK] N. Alon, W. Fernandez de la Vega, R. Kannan, and M. Karpinski, "Random sampling and approximation of MAX-CSP problems," in Proc. 34th Annual ACM Symposium on Theory of Computing, New York, 2002, pp. 232-239.
@inproceedings {ADKK, MRKEY = {2121147},   AUTHOR = {Alon, Noga and Fernandez de la Vega, W. and Kannan, Ravi and Karpinski, Marek},   TITLE = {Random sampling and approximation of {MAX}-{CSP} problems},   BOOKTITLE = {Proc. 34th {A}nnual {\rm ACM} {S}ymposium on {T}heory of {C}omputing},   PAGES = {232--239},   PUBLISHER = {ACM},   ADDRESS = {New York},   YEAR = {2002},   MRCLASS = {68W25 (68T20)},   MRNUMBER = {2121147},   }
• [AFKS] N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, "Efficient testing of large graphs," Combinatorica, vol. 20, iss. 4, pp. 451-476, 2000.
@article {AFKS, MRKEY = {1804820},   AUTHOR = {Alon, Noga and Fischer, Eldar and Krivelevich, Michael and Szegedy, Mario},   TITLE = {Efficient testing of large graphs},   JOURNAL = {Combinatorica},   FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},   VOLUME = {20},   YEAR = {2000},   NUMBER = {4},   PAGES = {451--476},   ISSN = {0209-9683},   MRCLASS = {05C85 (68R10)},   MRNUMBER = {2002f:05143},   MRREVIEWER = {Marek Kubale},   DOI = {10.1007/s004930070001},   ZBLNUMBER = {1052.68096},   }
• [ASsep] N. Alon and A. Shapira, "A separation theorem in property testing," Combinatorica, vol. 28, pp. 261-281, 2008.
@article{ASsep,   author = {Alon, Noga and Shapira, Asaf},   TITLE = {A separation theorem in property testing},   JOURNAL = {Combinatorica},   VOLUME = {28},   YEAR = {2008},   PAGES = {261--281},   }
• [ASher] N. Alon and A. Shapira, "A characterization of the (natural) graph properties testable with one-sided error," SIAM J. Comput., vol. 37, iss. 6, pp. 1703-1727, 2008.
@article {ASher, MRKEY = {2386211},   AUTHOR = {Alon, Noga and Shapira, Asaf},   TITLE = {A characterization of the (natural) graph properties testable with one-sided error},   JOURNAL = {{\rm SIAM} J. Comput.},   FJOURNAL = {{\rm SIAM} Journal on Computing},   VOLUME = {37},   YEAR = {2008},   NUMBER = {6},   PAGES = {1703--1727},   ISSN = {0097-5397},   MRCLASS = {68W20 (05C85 05D99 68W25)},   MRNUMBER = {2386211},   MRREVIEWER = {B{é}la Csaba},   DOI = {10.1137/06064888X},   ZBLNUMBER = {1152.05055},   }
• [ASmono] N. Alon and A. Shapira, "Every monotone graph property is testable," SIAM J. Comput., vol. 38, iss. 2, pp. 505-522, 2008.
@article {ASmono, MRKEY = {2411033},   AUTHOR = {Alon, Noga and Shapira, Asaf},   TITLE = {Every monotone graph property is testable},   JOURNAL = {{\rm SIAM} J. Comput.},   FJOURNAL = {{\rm SIAM} Journal on Computing},   VOLUME = {38},   YEAR = {2008},   NUMBER = {2},   PAGES = {505--522},   ISSN = {0097-5397},   MRCLASS = {05C35 (05C85 05D99 68R10 68W20 68W25)},   MRNUMBER = {2411033},   MRREVIEWER = {J{ó}zsef Balogh},   DOI = {10.1137/050633445},   }
• [ASp] N. Alon and J. H. Spencer, The Probabilistic Method, 2nd ed., New York: Wiley-Interscience, 2000.
@book {ASp, MRKEY = {1885388},   AUTHOR = {Alon, Noga and Spencer, Joel H.},   TITLE = {The Probabilistic Method},   EDITION = {2nd},   PUBLISHER = {Wiley-Interscience},   ADDRESS = {New York},   YEAR = {2000},   PAGES = {xviii+301},   ISBN = {0-471-37046-0},   MRCLASS = {60-02 (05C80 60C05 60F99 60G42)},   MRNUMBER = {2003f:60003},   MRREVIEWER = {Bert Fristedt},   ZBLNUMBER = {0996.05001},   }
• [AES] B. Andrásfai, P. ErdHos, and V. T. Sós, "On the connection between chromatic number, maximal clique and minimal degree of a graph," Discrete Math., vol. 8, pp. 205-218, 1974.
@article {AES, MRKEY = {0340075},   AUTHOR = {Andr{á}sfai, B. and Erd{ő}s, P. and S{ó}s, V. T.},   TITLE = {On the connection between chromatic number, maximal clique and minimal degree of a graph},   JOURNAL = {Discrete Math.},   FJOURNAL = {Discrete Mathematics},   VOLUME = {8},   YEAR = {1974},   PAGES = {205--218},   ISSN = {0012-365X},   MRCLASS = {05C15},   MRNUMBER = {49 \#4831},   MRREVIEWER = {D. J. Kleitman},   DOI = {10.1016/0012-365X(74)90133-2},   }
• [AFK] S. Arora, A. Frieze, and H. Kaplan, "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems," Math. Program., vol. 92, iss. 1, Ser. A, pp. 1-36, 2002.
@article {AFK, MRKEY = {1892295},   AUTHOR = {Arora, Sanjeev and Frieze, Alan and Kaplan, Haim},   TITLE = {A new rounding procedure for the assignment problem with applications to dense graph arrangement problems},   JOURNAL = {Math. Program.},   FJOURNAL = {Mathematical Programming. A Publication of the Mathematical Programming Society},   VOLUME = {92},   YEAR = {2002},   NUMBER = {1, Ser. A},   PAGES = {1--36},   ISSN = {0025-5610},   MRCLASS = {90C35 (90B80)},   MRNUMBER = {2002m:90091},   MRREVIEWER = {Gerard Sierksma},   DOI = {10.1007/s101070100271},   ZBLNUMBER = {1154.90602},   }
• [AKK] S. Arora, D. Karger, and M. Karpinski, "Polynomial time approximation schemes for dense instances of NP-hard problems," J. Comput. System Sci., vol. 58, iss. 1, pp. 193-210, 1999.
@article {AKK, MRKEY = {1688590},   AUTHOR = {Arora, Sanjeev and Karger, David and Karpinski, Marek},   TITLE = {Polynomial time approximation schemes for dense instances of {NP}-hard problems},   JOURNAL = {J. Comput. System Sci.},   FJOURNAL = {Journal of Computer and System Sciences},   VOLUME = {58},   YEAR = {1999},   NUMBER = {1},   PAGES = {193--210},   ISSN = {0022-0000},   CODEN = {JCSSBM},   MRCLASS = {68W25 (68Q25 68W20 90C27)},   MRNUMBER = {2001a:68112},   MRREVIEWER = {Ulrich Faigle},   DOI = {10.1006/jcss.1998.1605},   ZBLNUMBER = {0937.68160},   }
• [Asano] T. Asano, "An application of duality to edge-deletion problems," SIAM J. Comput., vol. 16, iss. 2, pp. 312-331, 1987.
@article {Asano, MRKEY = {882534},   AUTHOR = {Asano, Takao},   TITLE = {An application of duality to edge-deletion problems},   JOURNAL = {{\rm SIAM} J. Comput.},   FJOURNAL = {{\rm SIAM} Journal on Computing},   VOLUME = {16},   YEAR = {1987},   NUMBER = {2},   PAGES = {312--331},   ISSN = {0097-5397},   CODEN = {SMJCAT},   MRCLASS = {68Q25 (05C35 05C40 68R10)},   MRNUMBER = {88d:68036},   MRREVIEWER = {Mukkai S. Krishnamoorthy},   DOI = {10.1137/0216024},   ZBLNUMBER = {0634.68033},   }
• [AH] T. Asano and A. Hirata, "Edge-deletion and edge-contraction problems," in Proc. of STOC, , 1982, pp. 245-254.
@incollection{ AH,   author={Asano, T. and Hirata, A.},   TITLE={Edge-deletion and edge-contraction problems},   booktitle={Proc. of {\rm STOC}},   year=1982, pages={245--254},   }
• [BSTT] A. Bondy, J. Shen, S. Thomassé, and C. Thomassen, "Density conditions for triangles in multipartite graphs," Combinatorica, vol. 26, iss. 2, pp. 121-131, 2006.
@article {BSTT, MRKEY = {2223630},   AUTHOR = {Bondy, Adrian and Shen, Jian and Thomass{é},   St{é}phan and Thomassen, Carsten},   TITLE = {Density conditions for triangles in multipartite graphs},   JOURNAL = {Combinatorica},   FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},   VOLUME = {26},   YEAR = {2006},   NUMBER = {2},   PAGES = {121--131},   ISSN = {0209-9683},   MRCLASS = {05C35},   MRNUMBER = {2007a:05062},   MRREVIEWER = {Pedro Garc{\'ı}a-V{á}zquez},   DOI = {10.1007/s00493-006-0009-y},   }
• [BKS] J. Balogh, P. Keevash, and B. Sudakov, "On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs," J. Combinatorial Theory, Ser. B, vol. 96, pp. 919-932, 2006.
@article{BKS,   author = {Balogh, J and Keevash, P and Sudakov, B},   TITLE = {On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs},   JOURNAL = {J. Combinatorial Theory, Ser. {\rm B}},   VOLUME = {96},   YEAR = {2006},   PAGES = {919--932},   }
• [C] L. Cai, "Fixed-parameter tractability of graph modification problems for hereditary properties," Inform. Process. Lett., vol. 58, iss. 4, pp. 171-176, 1996.
@article {C, MRKEY = {1413637},   AUTHOR = {Cai, Leizhen},   TITLE = {Fixed-parameter tractability of graph modification problems for hereditary properties},   JOURNAL = {Inform. Process. Lett.},   FJOURNAL = {Information Processing Letters},   VOLUME = {58},   YEAR = {1996},   NUMBER = {4},   PAGES = {171--176},   ISSN = {0020-0190},   CODEN = {IFPLAT},   MRCLASS = {68R10 (68Q25)},   MRNUMBER = {97e:68098},   DOI = {10.1016/0020-0190(96)00050-6},   ZBLNUMBER = {0875.68702},   }
• [CMNR] K. Cirino, S. Muthukrishnan, N. Narayanaswamy, and H. Ramesh, "Graph editing to bipartite interval graphs: exact and asymptotic bounds," in Proc. of $17$th FSTTCS, , 1997, pp. 37-53.
@incollection{CMNR,   author = {Cirino, K. and Muthukrishnan, S. and Narayanaswamy, N. and Ramesh, H},   TITLE = {Graph editing to bipartite interval graphs: exact and asymptotic bounds},   booktitle = {Proc. of $17$th {\rm FSTTCS}},   year = {1997},   pages = {37--53},   }
• [EC] E. S. El-Mallah and C. J. Colbourn, "The complexity of some edge deletion problems," IEEE Trans. Circuits and Systems, vol. 35, iss. 3, pp. 354-362, 1988.
@article {EC, MRKEY = {931861},   AUTHOR = {El-Mallah, Ehab S. and Colbourn, Charles J.},   TITLE = {The complexity of some edge deletion problems},   JOURNAL = {{\rm IEEE} Trans. Circuits and Systems},   FJOURNAL = {Institute of Electrical and Electronics Engineers. Transactions on Circuits and Systems},   VOLUME = {35},   YEAR = {1988},   NUMBER = {3},   PAGES = {354--362},   ISSN = {0098-4094},   CODEN = {ICSYBT},   MRCLASS = {68R10 (05C35 05C75 68Q15 68Q25 68Q35)},   MRNUMBER = {89d:68068},   MRREVIEWER = {Toshimasa Watanabe},   DOI = {10.1109/31.1748},   ZBLNUMBER = {0654.68084},   }
• [E] P. ErdHos, "On extremal problems of graphs and generalized graphs," Israel J. Math., vol. 2, pp. 183-190, 1964.
@article {E, MRKEY = {0183654},   AUTHOR = {Erd{ő}s, P.},   TITLE = {On extremal problems of graphs and generalized graphs},   JOURNAL = {Israel J. Math.},   FJOURNAL = {Israel Journal of Mathematics},   VOLUME = {2},   YEAR = {1964},   PAGES = {183--190},   ISSN = {0021-2172},   MRCLASS = {05.40},   MRNUMBER = {32 \#1134},   MRREVIEWER = {A. H. Stone},   DOI = {10.1007/BF02759942},   }
• [Er] P. ErdHos, "On some new inequalities concerning extremal properties of graphs," in Theory of Graphs, New York: Academic Press, 1968, pp. 77-81.
@incollection {Er, MRKEY = {0232703},   AUTHOR = {Erd{ő}s, P.},   TITLE = {On some new inequalities concerning extremal properties of graphs},   BOOKTITLE = {Theory of {G}raphs},   venue = {Tihany, 1966},   PAGES = {77--81},   PUBLISHER = {Academic Press},   ADDRESS = {New York},   YEAR = {1968},   MRCLASS = {05.55},   MRNUMBER = {38 \#1026},   MRREVIEWER = {F. Harary},   }
• [ES] P. ErdHos and M. Simonovits, "On a valence problem in extremal graph theory," Discrete Math., vol. 5, pp. 323-334, 1973.
@article {ES, MRKEY = {0342429},   AUTHOR = {Erd{ő}s, P. and Simonovits, M.},   TITLE = {On a valence problem in extremal graph theory},   JOURNAL = {Discrete Math.},   FJOURNAL = {Discrete Mathematics},   VOLUME = {5},   YEAR = {1973},   PAGES = {323--334},   ISSN = {0012-365X},   MRCLASS = {05C35},   MRNUMBER = {49 \#7175},   MRREVIEWER = {D. R. Lick},   DOI = {10.1016/0012-365X(73)90126-X},   }
• [FDLV] F. W. de la Vega, "MAX-CUT has a randomized approximation scheme in dense graphs," Random Structures Algorithms, vol. 8, iss. 3, pp. 187-198, 1996.
@article {FDLV, MRKEY = {1605413},   AUTHOR = {de la Vega, W. Fernandez},   TITLE = {M{AX}-{CUT} has a randomized approximation scheme in dense graphs},   JOURNAL = {Random Structures Algorithms},   FJOURNAL = {Random Structures \& Algorithms},   VOLUME = {8},   YEAR = {1996},   NUMBER = {3},   PAGES = {187--198},   ISSN = {1042-9832},   MRCLASS = {05C85},   MRNUMBER = {98i:05148},   DOI = {10.1002/(SICI)1098-2418(199605)8:3%3C187::AID-RSA3%3E3.0.CO%3B2-U},   ZBLNUMBER = {0848.90120},   }
• [F] E. Fischer, "The art of uninformed decisions: a primer to property testing," Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, iss. 75, pp. 97-126, 2001.
@article {F, MRKEY = {1883003},   AUTHOR = {Fischer, Eldar},   TITLE = {The art of uninformed decisions: a primer to property testing},   JOURNAL = {Bull. Eur. Assoc. Theor. Comput. Sci. {\rm EATCS}},   FJOURNAL = {Bulletin of the European Association for Theoretical Computer Science. {\rm EATCS}},   NUMBER = {75},   YEAR = {2001},   PAGES = {97--126},   ISSN = {0252-9742},   MRCLASS = {68Q25 (68Q15)},   MRNUMBER = {1883003},   ZBLNUMBER = {1024.68045},   }
• [FN] E. Fischer and I. Newman, "Testing versus estimation of graph properties," in Proc. of 37th STOC, New York: ACM, 2005, pp. 138-146.
@incollection {FN, MRKEY = {2181611},   AUTHOR = {Fischer, Eldar and Newman, Ilan},   TITLE = {Testing versus estimation of graph properties},   BOOKTITLE = {{P}roc. of 37th {\rm STOC}},   PAGES = {138--146},   PUBLISHER = {ACM},   ADDRESS = {New York},   YEAR = {2005},   MRCLASS = {68R10 (05C35 68W20)},   MRNUMBER = {2181611},   }
• [FK] A. Frieze and R. Kannan, "The regularity lemma and approximation schemes for dense problems," in 37th Annual Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Comput. Soc. Press, 1996, pp. 12-20.
@incollection {FK, MRKEY = {1450598},   AUTHOR = {Frieze, Alan and Kannan, Ravi},   TITLE = {The regularity lemma and approximation schemes for dense problems},   BOOKTITLE = {37th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience},   venue = {{B}urlington, {\rm VT},   1996},   PAGES = {12--20},   PUBLISHER = {IEEE Comput. Soc. Press},   ADDRESS = {Los Alamitos, CA},   YEAR = {1996},   MRCLASS = {68Q25 (68Q15 68R10)},   MRNUMBER = {1450598},   }
• [FK2] A. Frieze and R. Kannan, "Quick approximation to matrices and applications," Combinatorica, vol. 19, iss. 2, pp. 175-220, 1999.
@article {FK2, MRKEY = {1723039},   AUTHOR = {Frieze, Alan and Kannan, Ravi},   TITLE = {Quick approximation to matrices and applications},   JOURNAL = {Combinatorica},   FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},   VOLUME = {19},   YEAR = {1999},   NUMBER = {2},   PAGES = {175--220},   ISSN = {0209-9683},   MRCLASS = {68Q25 (05C85 15-04 68R10 68W20)},   MRNUMBER = {2001i:68066},   MRREVIEWER = {Eugene V. Dulov},   DOI = {10.1007/s004930050052},   ZBLNUMBER = {0933.68061},   }
• [F1] Z. Füredi, "Turán type problems," in Surveys in Combinatorics, 1991, Cambridge: Cambridge Univ. Press, 1991, pp. 253-300.
@incollection {F1, MRKEY = {1161467},   AUTHOR = {F{ü}redi, Zolt{á}n},   TITLE = {Turán type problems},   BOOKTITLE = {Surveys in {C}ombinatorics, 1991},   venue = {Guildford, 1991},   SERIES = {London Math. Soc. Lecture Note Ser.},   NUMBER = {166},   PAGES = {253--300},   PUBLISHER = {Cambridge Univ. Press},   ADDRESS = {Cambridge},   YEAR = {1991},   MRCLASS = {05C35 (05C65 05C80 05D05)},   MRNUMBER = {93d:05072},   MRREVIEWER = {W. G. Brown},   }
• [GJ] M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, San Francisco, CA: W. H. Freeman and Co., 1979.
@book {GJ, MRKEY = {519066},   AUTHOR = {Garey, Michael R. and Johnson, David S.},   TITLE = {Computers and Intractability, A Guide to the Theory of {\rm NP}-Completeness},   PUBLISHER = {W. H. Freeman and Co.},   ADDRESS = {San Francisco, CA},   YEAR = {1979},   PAGES = {x+338},   ISBN = {0-7167-1045-5},   MRCLASS = {68C25 (03D15)},   MRNUMBER = {80g:68056},   MRREVIEWER = {Pavel Pudl{á}k},   }
• [GGKS] P. W. Goldberg, M. C. Golumbic, H. Kaplan, and R. Shamir, "Four strikes against physical mapping of DNA," J. Comput. Biology\/, vol. 2, pp. 139-152, 1995.
@article{GGKS,   author = {Goldberg, P. W. and Golumbic, M. C. and Kaplan, H. and Shamir, R},   TITLE = {Four strikes against physical mapping of DNA},   journal = {J. Comput. Biology\/},   volume = {2},   year = {1995},   pages = {139--152},   }
• [G] O. Goldreich, "Combinatorial property testing (a survey)," in Randomization Methods in Algorithm Design, Providence, RI: Amer. Math. Soc., 1999, pp. 45-59.
@incollection {G, MRKEY = {1660779},   AUTHOR = {Goldreich, Oded},   TITLE = {Combinatorial property testing (a survey)},   BOOKTITLE = {Randomization Methods in Algorithm Design},   venue = {Princeton, NJ, 1997},   SERIES = {{\rm DIMACS} Ser. Discrete Math. Theoret. Comput. Sci.},   NUMBER = {43},   PAGES = {45--59},   PUBLISHER = {Amer. Math. Soc.},   ADDRESS = {Providence, RI},   YEAR = {1999},   MRCLASS = {68Q22 (68Q25)},   MRNUMBER = {99g:68083},   ZBLNUMBER = {0912.68071},   }
• [GKS] M. C. Golumbic, H. Kaplan, and R. Shamir, "On the complexity of DNA physical mapping," Adv. in Appl. Math., vol. 15, iss. 3, pp. 251-261, 1994.
@article {GKS, MRKEY = {1288801},   AUTHOR = {Golumbic, Martin Charles and Kaplan, Haim and Shamir, Ron},   TITLE = {On the complexity of {DNA} physical mapping},   JOURNAL = {Adv. in Appl. Math.},   FJOURNAL = {Advances in Applied Mathematics},   VOLUME = {15},   YEAR = {1994},   NUMBER = {3},   PAGES = {251--261},   ISSN = {0196-8858},   MRCLASS = {92D20},   MRNUMBER = {95b:92008},   DOI = {10.1006/aama.1994.1009},   ZBLNUMBER = {0806.92007},   }
• [HR] P. E. Haxell and V. Rödl, "Integer and fractional packings in dense graphs," Combinatorica, vol. 21, iss. 1, pp. 13-38, 2001.
@article {HR, MRKEY = {1805712},   AUTHOR = {Haxell, P. E. and R{ö}dl, V.},   TITLE = {Integer and fractional packings in dense graphs},   JOURNAL = {Combinatorica},   FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},   VOLUME = {21},   YEAR = {2001},   NUMBER = {1},   PAGES = {13--38},   ISSN = {0209-9683},   MRCLASS = {05C70},   MRNUMBER = {2002m:05157},   MRREVIEWER = {R. Balakrishnan},   DOI = {10.1007/s004930170003},   ZBLNUMBER = {1107.05304},   }
• [KR] S. Khot and V. Raman, "Parameterized complexity of finding subgraphs with hereditary properties," in Computing and Combinatorics, New York: Springer-Verlag, 2000, pp. 137-147.
@incollection {KR, MRKEY = {1866122},   AUTHOR = {Khot, Subhash and Raman, Venkatesh},   TITLE = {Parameterized complexity of finding subgraphs with hereditary properties},   BOOKTITLE = {Computing and Combinatorics},   venue = {Sydney, 2000},   SERIES = {Lecture Notes in Comput. Sci.},   NUMBER = {1858},   PAGES = {137--147},   PUBLISHER = {Springer-Verlag},   ADDRESS = {New York},   YEAR = {2000},   MRCLASS = {68Q25 (68Q15 68R10)},   MRNUMBER = {1866122},   ZBLNUMBER = {0988.68081},   }
• [KRT] Y. Kohayakawa, V. Rödl, and L. Thoma, "An optimal algorithm for checking regularity," SIAM J. Comput., vol. 32, iss. 5, pp. 1210-1235, 2003.
@article {KRT, MRKEY = {2001271},   AUTHOR = {Kohayakawa, Y. and R{ö}dl, V. and Thoma, L.},   TITLE = {An optimal algorithm for checking regularity},   JOURNAL = {{\rm SIAM} J. Comput.},   FJOURNAL = {{\rm SIAM} Journal on Computing},   VOLUME = {32},   YEAR = {2003},   NUMBER = {5},   PAGES = {1210--1235},   ISSN = {0097-5397},   MRCLASS = {05C85 (68R10)},   MRNUMBER = {2004f:05176},   DOI = {10.1137/S0097539702408223},   ZBLNUMBER = {1025.05056},   }
• [KS] J. Komlós and M. Simonovits, "Szemerédi’s regularity lemma and its applications in graph theory," in Combinatorics, Paul Erdős is Eighty, Budapest: János Bolyai Math. Soc., 1996, vol. 2, pp. 295-352.
@incollection {KS, MRKEY = {1395865},   AUTHOR = {Koml{ó}s, J. and Simonovits, M.},   TITLE = {Szemerédi's regularity lemma and its applications in graph theory},   BOOKTITLE = {Combinatorics, {P}aul {E}rdős is Eighty},   volume = {2},   venue = {Keszthely, 1993},   SERIES = {Bolyai Soc. Math. Stud.},   number = {2},   PAGES = {295--352},   PUBLISHER = {János Bolyai Math. Soc.},   ADDRESS = {Budapest},   YEAR = {1996},   MRCLASS = {05C35},   MRNUMBER = {97d:05172},   MRREVIEWER = {W. G. Brown},   ZBLNUMBER = {0851.05065},   }
• [KST] T. Kövari, V. T. Sós, and P. Turán, "On a problem of K. Zarankiewicz," Colloquium Math., vol. 3, pp. 50-57, 1954.
@article {KST, MRKEY = {0065617},   AUTHOR = {K{ö}vari, T. and S{ó}s, V. T. and Tur{á}n, P.},   TITLE = {On a problem of {K}. {Z}arankiewicz},   JOURNAL = {Colloquium Math.},   VOLUME = {3},   YEAR = {1954},   PAGES = {50--57},   MRCLASS = {27.2X},   MRNUMBER = {16,456a},   MRREVIEWER = {J. Riguet},   ZBLNUMBER = {0055.00704},   }
• [KrS] M. Krivelevich and B. Sudakov, "Pseudo-random graphs," in More Sets, Graphs and Numbers, New York: Springer-Verlag, 2006, pp. 199-262.
@incollection {KrS, MRKEY = {2223394},   AUTHOR = {Krivelevich, M. and Sudakov, B.},   TITLE = {Pseudo-random graphs},   BOOKTITLE = {More Sets, Graphs and Numbers},   SERIES = {Bolyai Soc. Math. Stud.},   NUMBER = {15},   PAGES = {199--262},   PUBLISHER = {Springer-Verlag},   ADDRESS = {New York},   YEAR = {2006},   MRCLASS = {05C80 (05C50)},   MRNUMBER = {2007a:05130},   MRREVIEWER = {David B. Penman},   ZBLNUMBER = {1098.05075},   }
• [LY] J. M. Lewis and M. Yannakakis, "The node-deletion problem for hereditary properties is NP-complete," J. Comput. System Sci., vol. 20, iss. 2, pp. 219-230, 1980.
@article {LY, MRKEY = {574592},   AUTHOR = {Lewis, John M. and Yannakakis, Mihalis},   TITLE = {The node-deletion problem for hereditary properties is {NP}-complete},   INVNOTE = {ACM-SIGACT Symposium on the Theory of Computing (San Diego, Calif., 1978)},   JOURNAL = {J. Comput. System Sci.},   FJOURNAL = {Journal of Computer and System Sciences},   VOLUME = {20},   YEAR = {1980},   NUMBER = {2},   PAGES = {219--230},   ISSN = {0022-0000},   CODEN = {JCSSBM},   MRCLASS = {68C25 (68E10)},   MRNUMBER = {83b:68038},   DOI = {10.1016/0022-0000(80)90060-4},   ZBLNUMBER = {0436.68029},   }
• [NSS] A. Natanzon, R. Shamir, and R. Sharan, "Complexity classification of some edge modification problems," Discrete Appl. Math., vol. 113, iss. 1, pp. 109-128, 2001.
@article {NSS, MRKEY = {1855517},   AUTHOR = {Natanzon, Assaf and Shamir, Ron and Sharan, Roded},   TITLE = {Complexity classification of some edge modification problems},   JOURNAL = {Discrete Appl. Math.},   FJOURNAL = {Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences},   VOLUME = {113},   YEAR = {2001},   NUMBER = {1},   PAGES = {109--128},   ISSN = {0166-218X},   CODEN = {DAMADU},   MRCLASS = {68Q17 (05C85 68R10)},   MRNUMBER = {2002g:68043},   MRREVIEWER = {Stanis{\l}aw P. Radziszowski},   DOI = {10.1016/S0166-218X(00)00391-7},   ZBLNUMBER = {0982.68104},   }
• [PRR] M. Parnas, D. Ron, and R. Rubinfeld, "Tolerant property testing and distance approximation," J. Comput. System Sci., vol. 72, iss. 6, pp. 1012-1042, 2006.
@article {PRR, MRKEY = {2252941},   AUTHOR = {Parnas, Michal and Ron, Dana and Rubinfeld, Ronitt},   TITLE = {Tolerant property testing and distance approximation},   JOURNAL = {J. Comput. System Sci.},   FJOURNAL = {Journal of Computer and System Sciences},   VOLUME = {72},   YEAR = {2006},   NUMBER = {6},   PAGES = {1012--1042},   ISSN = {0022-0000},   CODEN = {JCSSBM},   MRCLASS = {68W20 (62H30 68W25)},   MRNUMBER = {2007k:68146},   MRREVIEWER = {Nir Y. Ailon},   DOI = {10.1016/j.jcss.2006.03.002},   ZBLNUMBER = {1100.68109},   }
• [Ron] D. Ron, "Property testing," in Handbook of Randomized Computing, Dordrecht: Kluwer Acad. Publ., 2001, vol. 2, pp. 597-649.
@incollection {Ron, MRKEY = {1966913},   AUTHOR = {Ron, Dana},   TITLE = {Property testing},   BOOKTITLE = {Handbook of Randomized Computing},   volume = {2},   SERIES = {Comb. Optim.},   number = {9},   PAGES = {597--649},   PUBLISHER = {Kluwer Acad. Publ.},   ADDRESS = {Dordrecht},   YEAR = {2001},   MRCLASS = {68W25 (05C75 68Q15 68Q17 68Q32 68R10 68W20)},   MRNUMBER = {2004c:68161},   ZBLNUMBER = {1048.68064},   }
• [Rose] D. J. Rose, "A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations," in Graph Theory and Computing, New York: Academic Press, 1972, pp. 183-217.
@incollection {Rose, MRKEY = {0341833},   AUTHOR = {Rose, Donald J.},   TITLE = {A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations},   BOOKTITLE = {Graph Theory and Computing},   PAGES = {183--217},   PUBLISHER = {Academic Press},   ADDRESS = {New York},   YEAR = {1972},   MRCLASS = {65F05},   MRNUMBER = {49 \#6579},   MRREVIEWER = {R. P. Tewarson},   ZBLNUMBER = {0266.65028},   }
• [Si] M. Simonovits, "A method for solving extremal problems in graph theory, stability problems," in Theory of Graphs, New York: Academic Press, 1968, pp. 279-319.
@incollection {Si, MRKEY = {0233735},   AUTHOR = {Simonovits, M.},   TITLE = {A method for solving extremal problems in graph theory, stability problems},   BOOKTITLE = {Theory of {G}raphs},   venue = {Tihany, 1966},   PAGES = {279--319},   PUBLISHER = {Academic Press},   ADDRESS = {New York},   YEAR = {1968},   MRCLASS = {05.55},   MRNUMBER = {38 \#2056},   MRREVIEWER = {J. W. Moon},   ZBLNUMBER = {0164.24604},   }
• [Sz] E. Szemerédi, "Regular partitions of graphs," in Problèmes Combinatoires et Théorie des Graphes, Paris: CNRS, 1978, pp. 399-401.
@incollection {Sz, MRKEY = {540024},   AUTHOR = {Szemer{é}di, Endre},   TITLE = {Regular partitions of graphs},   BOOKTITLE = {Problèmes Combinatoires et Théorie des Graphes},   venue = {Orsay, 1976},   SERIES = {Colloq. Internat. {\rm CNRS}},   NUMBER = {260},   PAGES = {399--401},   PUBLISHER = {CNRS},   ADDRESS = {Paris},   YEAR = {1978},   MRCLASS = {05C35 (10L10)},   MRNUMBER = {81i:05095},   MRREVIEWER = {D. A. Klarner},   ZBLNUMBER = {0413.05055},   }
• [W] D. B. West, Introduction to Graph Theory, Upper Saddle River, NJ: Prentice Hall, 1996.
@book {W, MRKEY = {1367739},   AUTHOR = {West, Douglas B.},   TITLE = {Introduction to Graph Theory},   PUBLISHER = {Prentice Hall},   ADDRESS = {Upper Saddle River, NJ},   YEAR = {1996},   PAGES = {xvi+512},   ISBN = {0-13-227828-6},   MRCLASS = {05-01},   MRNUMBER = {96i:05001},   ZBLNUMBER = {0845.05001},   }
• [Y] M. Yannakakis, "Edge-deletion problems," SIAM J. Comput., vol. 10, iss. 2, pp. 297-309, 1981.
@article {Y, MRKEY = {615220},   AUTHOR = {Yannakakis, Mihalis},   TITLE = {Edge-deletion problems},   JOURNAL = {{\rm SIAM} J. Comput.},   FJOURNAL = {{\rm SIAM} Journal on Computing},   VOLUME = {10},   YEAR = {1981},   NUMBER = {2},   PAGES = {297--309},   ISSN = {0097-5397},   CODEN = {SMJCAT},   MRCLASS = {68C25 (05C35 68E10)},   MRNUMBER = {83b:68039},   DOI = {10.1137/0210021},   ZBLNUMBER = {0468.05043},   }
• [Yu] R. Yuster, "Integer and fractional packing of families of graphs," Random Structures Algorithms, vol. 26, iss. 1-2, pp. 110-118, 2005.
@article {Yu, MRKEY = {2116578},   AUTHOR = {Yuster, Raphael},   TITLE = {Integer and fractional packing of families of graphs},   JOURNAL = {Random Structures Algorithms},   FJOURNAL = {Random Structures \& Algorithms},   VOLUME = {26},   YEAR = {2005},   NUMBER = {1-2},   PAGES = {110--118},   ISSN = {1042-9832},   MRCLASS = {05C70},   MRNUMBER = {2006a:05138},   MRREVIEWER = {R. Balakrishnan},   DOI = {10.1002/rsa.20048},   ZBLNUMBER = {1061.05076},   }
• [X] J. Xue, "Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem," Networks, vol. 24, iss. 2, pp. 109-120, 1994.
@article {X, MRKEY = {1264593},   AUTHOR = {Xue, Jue},   TITLE = {Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem},   JOURNAL = {Networks},   FJOURNAL = {Networks. An International Journal},   VOLUME = {24},   YEAR = {1994},   NUMBER = {2},   PAGES = {109--120},   ISSN = {0028-3045},   CODEN = {NTWKAA},   MRCLASS = {05C85 (05C35 68R10)},   MRNUMBER = {94k:05196},   DOI = {10.1002/net.3230240208},   ZBLNUMBER = {0791.90065},   }

## Authors

Noga Alon

Institute for Advanced Study
Einstein Drive
Princeton, NJ 08540
United States

Asaf Shapira

School of Mathematics and College of Computing
Georgia Institute of Technology
Atlanta, GA 30332
United States

Benny Sudakov

Department of Mathematics
UCLA
Box 951555
Los Angeles, CA 90095
United States