2011 | OriginalPaper | Buchkapitel
Inflatable Graph Properties and Natural Property Tests
verfasst von : Eldar Fischer, Eyal Rozenberg
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider
natural
graph property tests, which act entirely independently of the size of the graph being tested. We introduce the notion of properties being
inflatable
— closed under taking (balanced) blowups — and show that the query complexity of natural tests for a property is related to the degree to which it is approximately hereditary and inflatable. Specifically, we show that for properties which are almost hereditary and almost inflatable, any test can be made natural, with a polynomial increase in the number of queries. The naturalization can be considered as an extension of the canonicalization due to [15], so that natural canonical tests can be described as
strongly canonical
.
Using the technique for naturalization, we restore in part the claim in [15] regarding testing hereditary properties by ensuring that a small random subgraph itself satisfies the property. This allows us to generalize the triangle-freeness lower bound result of [5]: Any lower bound, not only the currently established quasi-polynomial one, on one-sided testing for triangle-freeness holds essentially for two-sided testing as well. We also explore the relations of the notion of inflatability and other already-studied features of properties and property tests, such as one-sidedness, heredity, and proximity-oblivion.