Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Given an undirected graph G = ( V , E ) with matching number ν ( G ) , a d -blocker is a subset of edges B such that ν ( ( V , E ∖ B ) ) ≤ ν ( G ) − d and a d -transversal T is a subset of edges such that every maximum matching M has | M ∩ T | ≥ d . While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d -transversals and minimum d -blockers in the special cases where G is a grid graph or a tree.