1289:
Trivially, hereditary properties are also semi-hereditary. This characterization partially answers the converse to the other Alon & Shapira theorem above: the properties that are easy to test properties (having oblivious testers with one-sided error) are almost hereditary. In the same paper, they
1165:
In this case, the tester cannot even differentiate which property (bipartiteness or perfectness) to test unless it knows the number of vertices. There are many examples of such unnatural properties. In fact, the characterization of graph properties testable by an oblivious tester with one-sided error
298:
The main efficiency parameter of a property testing algorithm is its query complexity, which is the maximum number of input symbols inspected over all inputs of a given length (and all random choices made by the algorithm). One is interested in designing algorithms whose query complexity is as small
289:
if it performs all its queries before it "observes" any answers to previous queries. Such an algorithm can be viewed as operating in the following manner. First the algorithm receives its input. Before looking at the input, using its internal randomness, the algorithm decides which symbols of the
1550:
be the desired upper bound on error probability for the following testers. Note, query complexity should not be confused with running time. The latter is often exponential (as is the case of both) due to a lack of polynomial time decision algorithm to test the peroperty on the induced subgraph. We
359:
The query complexity of property testing algorithms grows as the proximity parameter ε becomes smaller for all non-trivial properties. This dependence on ε is necessary as a change of fewer than ε symbols in the input cannot be detected with constant probability using fewer than O(1/ε) queries.
536:
The field of graph property testing was first introduced by
Goldreich, Goldwasser, and Ron. In their seminal paper published in 1998, an abstract graph partition problem is analyzed and some testers provided. These include as special cases several important graph properties like
310:
Unlike other complexity-theoretic settings, the asymptotic query complexity of property testing algorithms is affected dramatically by the representation of instances. For example, when ε = 0.01, the problem of testing bipartiteness of
1659:
1805:
290:
input are to be queried. Next, the algorithm observes these symbols. Finally, without making any additional queries (but possibly using its randomness), the algorithm decides whether to accept or reject the input.
1407:
1502:
150:
384:, which also has tower-type bounds in its conclusions. The connection of property testing to the Szemerédi regularity lemma and related graph removal lemmas is elaborated on below.
354:
935:
1217:
1036:
753:
434:
1275:
1246:
885:
1006:
727:
1441:
806:
364:. However, the query complexity can grow enormously fast as a function of ε. For example, for a long time the best known algorithm for testing if a graph does not
962:
780:
686:
982:
905:
846:
826:
30:, concerned with the design of super-fast algorithms for approximate decision making, where the decision refers to properties or parameters of huge objects.
380:(1/ε). One of the reasons for this enormous growth in bounds is that many of the positive results for property testing of graphs are established using the
1576:
1714:
46:
557:
algorithms that sample a subgraph and check whether it satisfy the property are all correct albeit with perhaps suboptimal query complexities.
303:
in the instance length. Typically, the goal is first to make the query complexity as small as possible as a function of the instance size
360:
Many interesting properties of dense graphs can be tested using query complexity that depends only on ε and not on the graph size
1130:
Crucially, the number of queries an oblivious tester makes is a constant only dependent on ε and not the size of the input graph
436:
edges and get from the first graph to the second. Under a reasonable representation of graphs, this is equivalent to the earlier
1142:
We can certainly contrive some graph properties where a tester for it must access the number of vertices. Here is one example.
2074:
Alon, N.; Duke, R. A.; Lefmann, H.; Rodl, V.; Yuster, R. (1 January 1994). "The
Algorithmic Aspects of the Regularity Lemma".
2224:
528:
having one of these edges removed. Then, the tester cannot tell them apart unless it queries every edge, which it cannot do.
688:
come up naturally as the size of the samples. Also, the query complexity using this regularity approach is large due to the
661:
for infinite families of induced subgraphs. We reproduce the theorem here without proof. In particular, note that constant
2101:
Alon, Noga; Fischer, Eldar; Krivelevich, Michael; Szegedy, Mario (1 April 2000). "Efficient
Testing of Large Graphs".
164:, as a probabilistically checkable proof is essentially a proof that can be verified by a property testing algorithm.
2214:
1873:
445:
To make precise the general notions of property testing in the context of graphs, we say a tester for graph property
161:
84:
admits an algorithm whose query complexity is independent of the instance size (for an arbitrary constant ε > 0):
1377:
1134:. In complete analogy with property testing algorithms, we can talk about oblivious testers with one-sided error.
323:
vertices (which are represented by their adjacency list) require property testing algorithms of query complexity
2219:
2145:
1971:
1464:
623:
111:
49:
of the problem. Typically property testing algorithms are used to distinguish if some combinatorial structure
406:. That is, we say that the distance between two graphs is the smallest ε such that one can add and/or delete
694:
599:
graph properties. They also characterized properties are easy to test. Namely, these natural properties are
381:
54:
27:
326:
910:
1196:
1011:
732:
409:
1251:
1222:
851:
2043:
987:
708:
17:
1416:
785:
1333:. They are natural in the sense that we follow the natural idea of randomly sampling some subset
300:
618:
if it is preserved under deletion of vertices, or equivalently, if it is preserved under taking
2038:
1102:
chosen uniformly at random. It then accepts or rejects (possibly randomly) according to ε and
546:
940:
758:
664:
193:
45:
whose query complexity (the number of queries made to its input) is much smaller than the
8:
1365:
1361:
1319:
657:
614:
595:
590:(one that is preserved under vertex and edge deletion) is testable with one-sided error.
365:
65:, or is "far" from having this property (meaning an ε-fraction of the representation of
2170:
2151:
2056:
1552:
1346:
967:
890:
831:
811:
550:
2128:
Alon, Noga; Shapira, Asaf (22 May 2005). "Every monotone graph property is testable".
1945:
2141:
1967:
1869:
2155:
1909:"A characterization of the (natural) graph properties testable with one-sided error"
278:
if it satisfies the stronger condition that the accepting probability for instances
2133:
2110:
2083:
2060:
2048:
2009:
1957:
1923:
619:
438:
316:
58:
38:
319:) admits an algorithm of constant query complexity. In contrast, sparse graphs on
1908:
1654:{\displaystyle q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})}
1536:
1323:
538:
101:
81:
1941:
1861:
1540:
1327:
634:
542:
466:
1962:
299:
as possible. In many cases the running time of property testing algorithms is
2208:
2130:
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
1800:{\displaystyle q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})}
1349:. We have one-sided error since these properties are actually hereditary: if
1158:
575:
In 1999, Alon, Fischer, Krivelevich, and
Szegedy showed that for every graph
402:
2137:
520:
by changing only a few edges. One example is testing triangle-freeness with
108:
cannot be made bipartite even after removing an arbitrary subset of at most
2087:
641:
564:
In 1992, Alon, Duke, Lefmann, Rödl, and Yuster showed that for every graph
2114:
2014:
1997:
1952:. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
1086:
is an algorithm that takes as input a parameter ε. It computes an integer
1341:
and checking whether the graph property holds on the subgraph spanned by
593:
In 2008, Alon and
Shapira exhibited testers with one-sided error for all
622:, hence the name hereditary. A few important hereditary properties are
2052:
2029:
Rubinfeld, Ronitt; Shapira, Asaf (2011). "Sublinear Time
Algorithms".
1927:
376:(1/ε), and only in 2010 this has been improved to a tower function of
1904:
689:
369:
42:
1374:
is ε-far from being triangle-free, there is a (computable) constant
449:
should distinguish with at least ⅔ probability between the cases of
2190:
1998:"Property testing and its connection to learning and approximation"
2175:
651:
Every hereditary graph property is testable with one-sided error.
1055:, it is an algorithm that takes as input a parameter ε and graph
469:
to query whether a pair of vertices has an edge between them in
77:), using only a small number of "local" queries to the object.
1353:
satisfy the property, so must the induced subgraph spanned by
307:, and then study the dependency on the proximity parameter ε.
2169:
Fox, Jacob (2010). "A new proof of the graph removal lemma".
2100:
1996:
Goldreich, Oded; Goldwasser, Shafi; Ron, Dana (1 July 1998).
160:
Property testing algorithms are central to the definition of
1051:
is oblivious to the size of the input. For a graph property
1137:
481:
if it has false positives and not false negatives, i.e. if
1309:
477:
is the number of such oracle queries. Say the tester has
1515:, query if all three pairs of vertices are adjacent in
1301:
has an oblivious one-sided error tester if and only if
560:
Since then, several related discoveries have been made
1995:
1318:
oblivious testing algorithms with one-sided error for
1157:
if it is bipartite with an even number of vertices or
607:
492:
We can only differentiate between graphs that satisfy
119:
1717:
1579:
1467:
1419:
1380:
1254:
1225:
1199:
1014:
990:
970:
943:
913:
893:
854:
834:
814:
788:
761:
735:
711:
667:
412:
329:
114:
1090:(ε) and then asks an oracle for an induced subgraph
400:
vertices, the notion of distance we will use is the
2073:
1504:triples of vertices independently at random, where
1281:contains an induced subgraph that does not satisfy
1059:, and then runs as a property testing algorithm on
442:definition (up to possibly a change of constants).
1799:
1653:
1496:
1435:
1401:
1269:
1240:
1211:
1030:
1000:
976:
956:
929:
899:
879:
840:
820:
800:
774:
747:
721:
680:
428:
348:
144:
1526:if no triple of vertices induces a triangle, and
489:, the tester always outputs the correct answer.
2206:
2028:
603:. These statements will be made clearer below.
1448:Example (Triangle-freeness Testing Algorithm).
1110:if it accepts with probability at least ⅔ for
1067:with proximity parameter ε that makes exactly
1402:{\displaystyle \delta =\delta (\varepsilon )}
1118:, and rejects with probability at least ⅔ or
583:as an induced subgraph subgraph is testable.
274:A property testing algorithm is said to have
135:
122:
1181:if there exists a hereditary graph property
2127:
1946:"Combinatorial Property Testing (a survey)"
1903:
1698:Example (k-colorability Testing Algorithm).
1370:. In particular, it tells us that if graph
705:For each (possibly infinite) set of graphs
504:. In the latter case, consider two graphs:
387:
293:
644:. All hereditary properties are testable.
586:In 2005, Alon and Shapira showed that any
461:is ε-far in edit distance from satisfying
259:" means that the Hamming distance between
167:
2174:
2042:
2013:
1991:
1989:
1987:
1985:
1983:
1961:
1950:Randomization Methods in Algorithm Design
1940:
1860:
1497:{\displaystyle q(\varepsilon )=1/\delta }
500:as opposed to satisfy versus not satisfy
145:{\displaystyle \epsilon {\tbinom {n}{2}}}
2067:
1899:
1897:
1895:
1893:
1891:
1889:
1887:
1885:
1166:leads to a class of natural properties.
1138:Testing semi-hereditary graph properties
285:A property testing algorithm is said be
18:Software testing § Property testing
16:For the software testing technique, see
2094:
1856:
1854:
1852:
1310:Examples: testing some graph properties
1248:such that every graph of size at least
703:Theorem (Infinite graph removal lemma).
2207:
1980:
1560:Example (Bipartite Testing Algorithm).
1364:, the tester is an application of the
524:a graph with exactly one triangle and
2183:
2121:
2022:
1882:
655:The proof relies on a version of the
2162:
2031:SIAM Journal on Discrete Mathematics
1934:
1849:
1042:
1008:-free by adding/removing fewer than
349:{\displaystyle \Omega ({\sqrt {n}})}
2189:
2168:
1314:In this section, we will give some
1122:that is ε-far from having property
1106:. We say it tests for the property
930:{\displaystyle H\in {\mathcal {H}}}
608:Testing hereditary graph properties
13:
1295:Theorem (Alon & Shapira 2008).
993:
922:
714:
649:Theorem (Alon & Shapira 2008).
368:had a query complexity which is a
330:
162:probabilistically checkable proofs
126:
69:need be modified in order to make
14:
2236:
1212:{\displaystyle \varepsilon >0}
1031:{\displaystyle \varepsilon n^{2}}
748:{\displaystyle \varepsilon >0}
429:{\displaystyle \varepsilon n^{2}}
1866:Introduction to Property Testing
1814:, query if they are adjacent in
1668:, query if they are adjacent in
1511:For every triple of vertices in
1357:, so our tester always accepts.
531:
315:(which are represented by their
1270:{\displaystyle M(\varepsilon )}
1241:{\displaystyle M(\varepsilon )}
1185:such that any graph satisfying
1161:with an odd number of vertices.
880:{\displaystyle \delta n^{v(H)}}
1868:. Cambridge University Press.
1810:For every pair of vertices in
1794:
1776:
1762:
1736:
1727:
1721:
1664:For every pair of vertices in
1648:
1630:
1627:
1618:
1607:
1598:
1589:
1583:
1477:
1471:
1396:
1390:
1277:that is ε-far from satisfying
1264:
1258:
1235:
1229:
1001:{\displaystyle {\mathcal {H}}}
872:
866:
848:-vertex graph with fewer than
722:{\displaystyle {\mathcal {H}}}
343:
333:
1:
1842:
465:. The tester can access some
2225:Theoretical computer science
1436:{\displaystyle \delta n^{3}}
801:{\displaystyle \delta >0}
579:the property of not contain
568:the property of not contain
247:with probability at least ⅔.
232:with probability at least ⅔.
28:theoretical computer science
7:
1825:if the induced subgraph of
1679:if the induced subgraph of
572:as a subgraph is testable.
80:For example, the following
10:
2241:
695:Szemerédi regularity lemma
382:Szemerédi regularity lemma
174:property testing algorithm
61:) satisfies some property
15:
1916:SIAM Journal on Computing
188:ε for a decision problem
2215:Approximation algorithms
1907:; Shapira, Asaf (2008).
388:Testing graph properties
294:Features and limitations
243:, the algorithm rejects
228:, the algorithm accepts
216:and behaves as follows:
2138:10.1145/1060590.1060611
588:monotone graph property
168:Definition and variants
2088:10.1006/jagm.1994.1005
1840:
1801:
1707:, choose a random set
1694:
1655:
1569:, choose a random set
1533:
1498:
1457:, choose a random set
1437:
1403:
1367:triangle removal lemma
1271:
1242:
1213:
1032:
1002:
978:
958:
931:
901:
881:
842:
822:
802:
776:
749:
723:
682:
553:. In particular, the
496:versus those far from
430:
350:
176:with query complexity
146:
2220:Randomized algorithms
2115:10.1007/s004930070001
2076:Journal of Algorithms
2015:10.1145/285055.285060
1963:10.1090/dimacs/043/04
1802:
1695:
1656:
1557:
1499:
1445:
1438:
1404:
1272:
1243:
1214:
1033:
1003:
979:
959:
957:{\displaystyle h_{0}}
932:
902:
882:
843:
823:
803:
777:
775:{\displaystyle h_{0}}
750:
724:
683:
681:{\displaystyle h_{0}}
549:, and having a large
431:
351:
147:
2132:. pp. 128–137.
1715:
1577:
1465:
1417:
1378:
1305:is semi-hereditary.
1252:
1223:
1197:
1012:
988:
984:can be made induced
968:
941:
911:
891:
852:
832:
812:
786:
759:
733:
709:
665:
612:A graph property is
457:and the cases where
410:
366:contain any triangle
327:
194:randomized algorithm
112:
96:vertices, decide if
2197:(Technical report).
1833:is k-colorable and
1153:satisfies property
658:graph removal lemma
282:is 1 instead of ⅔.
186:proximity parameter
2002:Journal of the ACM
1797:
1651:
1553:brute-force search
1494:
1433:
1399:
1347:brute-force search
1267:
1238:
1209:
1114:that has property
1098:(ε) vertices from
1028:
998:
974:
954:
927:
897:
877:
838:
818:
798:
772:
745:
719:
678:
426:
346:
263:and any string in
142:
140:
2053:10.1137/100791075
1928:10.1137/06064888X
1687:is bipartite and
1551:instead check by
1362:triangle-freeness
1320:triangle-freeness
1297:A graph property
1173:A graph property
1063:for the property
1043:Oblivious testers
977:{\displaystyle G}
900:{\displaystyle H}
841:{\displaystyle n}
821:{\displaystyle G}
620:induced subgraphs
545:, having a large
341:
133:
2232:
2199:
2198:
2195:Property Testing
2187:
2181:
2180:
2178:
2166:
2160:
2159:
2125:
2119:
2118:
2098:
2092:
2091:
2071:
2065:
2064:
2046:
2037:(4): 1562–1588.
2026:
2020:
2019:
2017:
1993:
1978:
1977:
1965:
1938:
1932:
1931:
1922:(6): 1703–1727.
1913:
1901:
1880:
1879:
1858:
1806:
1804:
1803:
1798:
1793:
1792:
1783:
1772:
1758:
1757:
1748:
1747:
1660:
1658:
1657:
1652:
1647:
1646:
1637:
1617:
1503:
1501:
1500:
1495:
1490:
1442:
1440:
1439:
1434:
1432:
1431:
1408:
1406:
1405:
1400:
1276:
1274:
1273:
1268:
1247:
1245:
1244:
1239:
1218:
1216:
1215:
1210:
1193:, and for every
1084:oblivious tester
1049:oblivious tester
1037:
1035:
1034:
1029:
1027:
1026:
1007:
1005:
1004:
999:
997:
996:
983:
981:
980:
975:
963:
961:
960:
955:
953:
952:
936:
934:
933:
928:
926:
925:
906:
904:
903:
898:
886:
884:
883:
878:
876:
875:
847:
845:
844:
839:
827:
825:
824:
819:
807:
805:
804:
799:
781:
779:
778:
773:
771:
770:
754:
752:
751:
746:
728:
726:
725:
720:
718:
717:
687:
685:
684:
679:
677:
676:
629:(for some graph
475:query complexity
439:Hamming distance
435:
433:
432:
427:
425:
424:
355:
353:
352:
347:
342:
337:
317:adjacency matrix
204:) makes at most
200:(an instance of
151:
149:
148:
143:
141:
139:
138:
125:
59:boolean function
39:decision problem
37:algorithm for a
35:property testing
24:Property testing
2240:
2239:
2235:
2234:
2233:
2231:
2230:
2229:
2205:
2204:
2203:
2202:
2188:
2184:
2167:
2163:
2148:
2126:
2122:
2099:
2095:
2072:
2068:
2044:10.1.1.221.1797
2027:
2023:
1994:
1981:
1974:
1942:Goldreich, Oded
1939:
1935:
1911:
1902:
1883:
1876:
1862:Goldreich, Oded
1859:
1850:
1845:
1788:
1784:
1779:
1768:
1753:
1749:
1743:
1739:
1716:
1713:
1712:
1642:
1638:
1633:
1613:
1578:
1575:
1574:
1486:
1466:
1463:
1462:
1427:
1423:
1418:
1415:
1414:
1379:
1376:
1375:
1337:of vertices of
1312:
1253:
1250:
1249:
1224:
1221:
1220:
1198:
1195:
1194:
1179:semi-hereditary
1140:
1071:(ε) queries to
1047:Informally, an
1045:
1022:
1018:
1013:
1010:
1009:
992:
991:
989:
986:
985:
969:
966:
965:
964:vertices, then
948:
944:
942:
939:
938:
921:
920:
912:
909:
908:
892:
889:
888:
862:
858:
853:
850:
849:
833:
830:
829:
813:
810:
809:
787:
784:
783:
766:
762:
760:
757:
756:
734:
731:
730:
713:
712:
710:
707:
706:
672:
668:
666:
663:
662:
610:
601:semi-hereditary
534:
516:not satisfying
479:one-sided error
420:
416:
411:
408:
407:
390:
336:
328:
325:
324:
296:
276:one-sided error
196:that, on input
170:
134:
121:
120:
118:
113:
110:
109:
88:"Given a graph
82:promise problem
21:
12:
11:
5:
2238:
2228:
2227:
2222:
2217:
2201:
2200:
2182:
2161:
2146:
2120:
2109:(4): 451–476.
2093:
2066:
2021:
2008:(4): 653–750.
1979:
1972:
1933:
1881:
1874:
1847:
1846:
1844:
1841:
1839:
1838:
1819:
1808:
1796:
1791:
1787:
1782:
1778:
1775:
1771:
1767:
1764:
1761:
1756:
1752:
1746:
1742:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1693:
1692:
1673:
1662:
1650:
1645:
1641:
1636:
1632:
1629:
1626:
1623:
1620:
1616:
1612:
1609:
1606:
1603:
1600:
1597:
1594:
1591:
1588:
1585:
1582:
1532:
1531:
1522:The algorithm
1520:
1509:
1493:
1489:
1485:
1482:
1479:
1476:
1473:
1470:
1430:
1426:
1422:
1398:
1395:
1392:
1389:
1386:
1383:
1311:
1308:
1307:
1306:
1287:
1286:
1266:
1263:
1260:
1257:
1237:
1234:
1231:
1228:
1208:
1205:
1202:
1163:
1162:
1139:
1136:
1128:
1127:
1044:
1041:
1040:
1039:
1025:
1021:
1017:
995:
973:
951:
947:
924:
919:
916:
896:
874:
871:
868:
865:
861:
857:
837:
817:
797:
794:
791:
769:
765:
755:, there exist
744:
741:
738:
716:
690:tower function
675:
671:
653:
652:
609:
606:
605:
604:
591:
584:
573:
543:k-colorability
533:
530:
423:
419:
415:
389:
386:
370:tower function
345:
340:
335:
332:
295:
292:
267:is at least ε|
255:is ε-far from
249:
248:
239:is ε-far from
233:
212:|) queries to
169:
166:
158:
157:
137:
132:
129:
124:
117:
26:is a field of
9:
6:
4:
3:
2:
2237:
2226:
2223:
2221:
2218:
2216:
2213:
2212:
2210:
2196:
2192:
2186:
2177:
2172:
2165:
2157:
2153:
2149:
2143:
2139:
2135:
2131:
2124:
2116:
2112:
2108:
2104:
2103:Combinatorica
2097:
2089:
2085:
2082:(1): 80–109.
2081:
2077:
2070:
2062:
2058:
2054:
2050:
2045:
2040:
2036:
2032:
2025:
2016:
2011:
2007:
2003:
1999:
1992:
1990:
1988:
1986:
1984:
1975:
1969:
1964:
1959:
1955:
1951:
1947:
1943:
1937:
1929:
1925:
1921:
1917:
1910:
1906:
1900:
1898:
1896:
1894:
1892:
1890:
1888:
1886:
1877:
1875:9781107194052
1871:
1867:
1863:
1857:
1855:
1853:
1848:
1836:
1832:
1828:
1824:
1820:
1817:
1813:
1809:
1789:
1785:
1780:
1773:
1769:
1765:
1759:
1754:
1750:
1744:
1740:
1733:
1730:
1724:
1718:
1710:
1706:
1702:
1701:
1700:
1699:
1690:
1686:
1682:
1678:
1674:
1671:
1667:
1663:
1643:
1639:
1634:
1624:
1621:
1614:
1610:
1604:
1601:
1595:
1592:
1586:
1580:
1572:
1568:
1564:
1563:
1562:
1561:
1556:
1554:
1549:
1545:
1544:-colorability
1543:
1538:
1537:bipartiteness
1529:
1525:
1521:
1518:
1514:
1510:
1507:
1491:
1487:
1483:
1480:
1474:
1468:
1460:
1456:
1452:
1451:
1450:
1449:
1444:
1428:
1424:
1420:
1413:has at least
1412:
1393:
1387:
1384:
1381:
1373:
1369:
1368:
1363:
1358:
1356:
1352:
1348:
1344:
1340:
1336:
1332:
1331:-colorability
1330:
1325:
1324:bipartiteness
1321:
1317:
1304:
1300:
1296:
1293:
1292:
1291:
1284:
1280:
1261:
1255:
1232:
1226:
1206:
1203:
1200:
1192:
1188:
1184:
1180:
1176:
1172:
1169:
1168:
1167:
1160:
1156:
1152:
1148:
1145:
1144:
1143:
1135:
1133:
1125:
1121:
1117:
1113:
1109:
1105:
1101:
1097:
1093:
1089:
1085:
1081:
1078:
1077:
1076:
1074:
1070:
1066:
1062:
1058:
1054:
1050:
1023:
1019:
1015:
971:
949:
945:
937:with at most
917:
914:
894:
869:
863:
859:
855:
835:
815:
795:
792:
789:
767:
763:
742:
739:
736:
704:
701:
700:
699:
697:
696:
691:
673:
669:
660:
659:
650:
647:
646:
645:
643:
639:
638:-colorability
637:
632:
628:
626:
621:
617:
616:
602:
598:
597:
592:
589:
585:
582:
578:
574:
571:
567:
563:
562:
561:
558:
556:
552:
548:
544:
540:
539:bipartiteness
532:Short history
529:
527:
523:
519:
515:
511:
507:
503:
499:
495:
490:
488:
484:
480:
476:
472:
468:
464:
460:
456:
452:
448:
443:
441:
440:
421:
417:
413:
405:
404:
403:edit distance
399:
395:
385:
383:
379:
375:
371:
367:
363:
357:
338:
322:
318:
314:
308:
306:
302:
291:
288:
283:
281:
277:
272:
270:
266:
262:
258:
254:
246:
242:
238:
234:
231:
227:
223:
219:
218:
217:
215:
211:
207:
203:
199:
195:
191:
187:
183:
179:
175:
165:
163:
155:
130:
127:
115:
107:
103:
99:
95:
91:
87:
86:
85:
83:
78:
76:
72:
68:
64:
60:
56:
52:
48:
47:instance size
44:
40:
36:
31:
29:
25:
19:
2194:
2185:
2164:
2129:
2123:
2106:
2102:
2096:
2079:
2075:
2069:
2034:
2030:
2024:
2005:
2001:
1953:
1949:
1936:
1919:
1915:
1865:
1834:
1830:
1826:
1822:
1815:
1811:
1708:
1704:
1703:Given graph
1697:
1696:
1688:
1684:
1680:
1676:
1669:
1665:
1570:
1566:
1565:Given graph
1559:
1558:
1547:
1541:
1534:
1527:
1523:
1516:
1512:
1508:is as above.
1505:
1458:
1454:
1453:Given graph
1447:
1446:
1410:
1371:
1366:
1359:
1354:
1350:
1342:
1338:
1334:
1328:
1315:
1313:
1302:
1298:
1294:
1288:
1282:
1278:
1219:there is an
1190:
1186:
1182:
1178:
1174:
1170:
1164:
1154:
1150:
1146:
1141:
1131:
1129:
1123:
1119:
1115:
1111:
1107:
1103:
1099:
1095:
1091:
1087:
1083:
1079:
1072:
1068:
1064:
1060:
1056:
1052:
1048:
1046:
702:
693:
656:
654:
648:
635:
630:
624:
613:
611:
600:
594:
587:
580:
576:
569:
565:
559:
554:
535:
525:
521:
517:
513:
509:
505:
501:
497:
493:
491:
486:
482:
478:
474:
473:or not. The
470:
462:
458:
454:
450:
446:
444:
437:
401:
397:
393:
392:For a graph
391:
377:
373:
361:
358:
320:
313:dense graphs
312:
309:
304:
297:
287:non-adaptive
286:
284:
279:
275:
273:
268:
264:
260:
256:
252:
250:
244:
240:
236:
229:
225:
221:
213:
209:
205:
201:
197:
189:
185:
181:
177:
173:
172:Formally, a
171:
159:
153:
105:
97:
93:
89:
79:
74:
70:
66:
62:
50:
34:
32:
23:
22:
1837:otherwise.
1691:otherwise.
1530:otherwise.
1443:triangles.
1171:Definition.
1094:on exactly
1080:Definition.
808:so that if
508:satisfying
453:satisfying
53:(such as a
2209:Categories
2147:1581139608
1973:0821870874
1905:Alon, Noga
1843:References
1189:satisfies
907:for every
887:copies of
615:hereditary
596:hereditary
485:satisfies
2191:Ron, Dana
2176:1006.1300
2039:CiteSeerX
1956:: 45–59.
1807:vertices.
1786:ε
1774:δ
1760:
1725:ε
1661:vertices.
1640:ε
1625:δ
1622:ε
1605:
1587:ε
1492:δ
1475:ε
1421:δ
1394:ε
1388:δ
1382:δ
1262:ε
1233:ε
1201:ε
1016:ε
918:∈
856:δ
790:δ
737:ε
692:bound in
642:planarity
627:-freeness
414:ε
331:Ω
301:sublinear
152:edges of
116:ϵ
102:bipartite
43:algorithm
2193:(2000).
2156:14096855
1944:(1999).
1864:(2017).
1409:so that
1149:A graph
1147:Example.
73:satisfy
2061:1319122
1823:accepts
1677:accepts
1528:rejects
1524:accepts
1316:natural
1290:showed
1159:perfect
1038:edges.
555:natural
251:Here, "
2154:
2144:
2059:
2041:
1970:
1872:
1835:reject
1689:reject
1546:, let
1326:, and
828:is an
640:, and
547:clique
467:oracle
224:is in
184:) and
41:is an
2171:arXiv
2152:S2CID
2057:S2CID
1912:(PDF)
396:with
280:x ∈ L
192:is a
104:, or
57:or a
55:graph
2142:ISBN
1968:ISBN
1870:ISBN
1539:and
1535:For
1360:For
1204:>
793:>
782:and
740:>
729:and
512:and
374:poly
2134:doi
2111:doi
2084:doi
2049:doi
2010:doi
1958:doi
1924:doi
1829:on
1821:It
1751:log
1711:of
1683:on
1675:It
1602:log
1573:of
1555:.
1461:of
1345:by
1177:is
1082:An
633:),
551:cut
378:log
372:of
271:|.
235:If
220:If
100:is
92:on
2211::
2150:.
2140:.
2107:20
2105:.
2080:16
2078:.
2055:.
2047:.
2035:25
2033:.
2006:45
2004:.
2000:.
1982:^
1966:.
1954:43
1948:.
1920:37
1918:.
1914:.
1884:^
1851:^
1322:,
1285:.
1126:.
1075:.
698:.
541:,
356:.
208:(|
156:."
33:A
2179:.
2173::
2158:.
2136::
2117:.
2113::
2090:.
2086::
2063:.
2051::
2018:.
2012::
1976:.
1960::
1930:.
1926::
1878:.
1831:X
1827:G
1818:.
1816:G
1812:X
1795:)
1790:3
1781:/
1777:)
1770:/
1766:k
1763:(
1755:2
1745:4
1741:k
1737:(
1734:O
1731:=
1728:)
1722:(
1719:q
1709:X
1705:G
1685:X
1681:G
1672:.
1670:G
1666:X
1649:)
1644:2
1635:/
1631:)
1628:)
1619:(
1615:/
1611:1
1608:(
1599:(
1596:O
1593:=
1590:)
1584:(
1581:q
1571:X
1567:G
1548:δ
1542:k
1519:.
1517:G
1513:X
1506:δ
1488:/
1484:1
1481:=
1478:)
1472:(
1469:q
1459:X
1455:G
1429:3
1425:n
1411:G
1397:)
1391:(
1385:=
1372:G
1355:X
1351:G
1343:X
1339:G
1335:X
1329:k
1303:P
1299:P
1283:H
1279:P
1265:)
1259:(
1256:M
1236:)
1230:(
1227:M
1207:0
1191:H
1187:P
1183:H
1175:H
1155:P
1151:G
1132:G
1124:P
1120:G
1116:P
1112:G
1108:P
1104:H
1100:G
1096:q
1092:H
1088:q
1073:G
1069:q
1065:P
1061:G
1057:G
1053:P
1024:2
1020:n
994:H
972:G
950:0
946:h
923:H
915:H
895:H
873:)
870:H
867:(
864:v
860:n
836:n
816:G
796:0
768:0
764:h
743:0
715:H
674:0
670:h
636:k
631:H
625:H
581:H
577:H
570:H
566:H
526:G
522:H
518:P
514:H
510:P
506:G
502:P
498:P
494:P
487:P
483:G
471:G
463:P
459:G
455:P
451:G
447:P
422:2
418:n
398:n
394:G
362:n
344:)
339:n
334:(
321:n
305:n
269:x
265:L
261:x
257:L
253:x
245:x
241:L
237:x
230:x
226:L
222:x
214:x
210:x
206:q
202:L
198:x
190:L
182:n
180:(
178:q
154:G
136:)
131:2
128:n
123:(
106:G
98:G
94:n
90:G
75:P
71:S
67:S
63:P
51:S
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.