Study of systems of equations over various classes of finite matroids

Abstract

In the paper, it is proved that the problem of checking compatibility of a finite system of equations over a matroid of rank not exeeding $k$ is $\mathcal{NP}$-complete for ${k \geqslant 2}$.

Moreover, it is proved that the problem of checking compatibility of a finite system of equations over a $k$-uniform matroid is also $\mathcal{NP}$-complete for ${k \geqslant 2}$, and the problem of checking compatibility of a finite system of equations over a partition matroid of rank not exeeding $k$ is polynomially solvable for $k=2$ and $\mathcal{NP}$-complete for $k \geqslant 3$.