Bipartite Domination and Simultaneous Matroid Covers

Damaschke et al. gave a polynomial time algorithm to solve the minimum dominating set problem in {em convex} bipartite graphs $B=(X cup Y,E)$. That is, where the nodes in $Y$ can be ordered so that each node of $X$ is adjacent to a contiguous sequence of nodes. Gamble et al. gave an extension of their algorithm to weighted dominating sets. We formulate the dominating set problem as that of finding a minimum weight subset of elements of a graphic matroid which covers each fundamental circuit and fundamental cut with respect to some spanning tree $T$. 

When $T$ is a directed path, this {em simultaneous covering problem} coincides with the dominating set problem for the previously studied class of convex bipartite graphs. We describe a polynomial-time algorithm for the more general problem of simultaneous covering in the case when $T$ is an arborescence. We also give NP-completeness results for fairly specialized classes of the simultaneous cover problem. These are based on connections between the domination and induced matching problems.