Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove \varepsilon n edges from G to make it H-minor free (for some small constant \varepsilon > 0).
We give an n^{1/2+o(1)}-time randomized procedure that, with high probability, finds an ... more >>>

Let G be an undirected, bounded degree graph
with n vertices. Fix a finite graph H, and suppose one must remove \varepsilon n edges from G to make it H-minor free (for some small constant \varepsilon > 0). We give an n^{1/2+o(1)}-time randomized procedure that, with high probability, finds an ... more >>>

Let G be a graph with n vertices and maximum degree d. Fix some minor-closed property \mathcal{P} (such as planarity).
We say that G is \varepsilon-far from \mathcal{P} if one has to remove \varepsilon dn edges to make it have \mathcal{P}.
The problem of property testing \mathcal{P} was introduced in ... more >>>