CMR  1.3.0
Series-Parallel Matroids

A matrix \( A \in \{-1,0,+1\}^{m \times n} \) is called series-parallel if it can be obtained from a \( 0 \)-by- \( 0 \) matrix by successively adjoining

The removal of such a row/column is called an SP-reduction. A matroid is called series-parallel if it is represented by a series-parallel matrix. This is equivalent to being the graphic matroid of a series-parallel graph.

Theorem. A matrix \( A \in \{-1,0,1\}^{m \times n} \) is either series-parallel or it contains, up to scaling of rows/columns with \( -1 \),

The latter two matrices are called wheel matrices since they represent wheel graphs.

Usage

The executable cmr-series-parallel tests whether a given matrix \( A \) is series-parallel. If this is not the case, then a maximal number of SP-reductions is carried out, leading to the reduced matrix. Moreover, one can ask for one of the minimal non-series-parallel submatrices above.

./cmr-series-parallel [OPTION]... FILE

Options:

Formats for matrices are dense-matrix, sparse-matrix. If FILE is -, then the input will be read from stdin.

Algorithm

The implemented algorithm is not yet published. For a matrix \( A \in \{0,1\}^{m \times n}\) with \( k \) (sorted) nonzeros it runs in \( \mathcal{O}( m + n + k ) \) time assuming no hashtable collisions.

C Interface