Testing subdivision-freeness: property testing meets structural graph theory

Testing a property P of graphs in the bounded-degree model deals with the following problem: given a graph G of bounded degree d, we should distinguish (with probability 2/3, say) between the case that G satisfies P and the case that one should add/remove at least ε dn edges of $G$ to make it satisfy P. In sharp contrast to property testing of dense graphs, which is relatively well understood, only few properties are known to be testable with a constant number of queries in the bounded-degree model. In particular, no global monotone (i.e,~closed under edge deletions) property that expander graphs can satisfy has been shown to be testable in constant time so far.

Authors

• Ken-ichi Kawarabayashi
• Yuichi Yoshida

Keywords

No keywords are indexed for this paper.