An independence system Σ=(X,F) is called bimatroidal if there exist two matroids M=(X,FM) and N=(X,FN) such that F=FMℝFN. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This paper initiates the study of bimatroidal systems. Given the collection of circuits of an arbitrary independence system Σ (or, equivalently, the constraints of a set-covering problem), we address the following question: does Σ admit a bimatroidal decomposition {M,N} and, if so, how can we actually produce the circuits of M and N? The authors derive a number of results concerning this problem, and they present a polynomial time algorithm to solve it when every two circuits of Σ have at most one common element. The authors also propose different polynomial time algorithms for set covering problems defined on the circuit-set of bimatroidal systems.
