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

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