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

• a zero row/column vector,
• a (negated) standard unit row/column vector, or
• a (negated) copy of an existing row/column.

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$$,

• a $$2$$-by- $$2$$ submatrix $$M_2 := \begin{pmatrix} -1 & 1 \\ 1 & 1 \end{pmatrix}$$,
• a $$3$$-by- $$3$$ submatrix $$M_3' := \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{pmatrix}$$, or
• a $$k$$-by- $$k$$-submatrix $$M_k := \begin{pmatrix} 1 & 0 & 0 & 0 & \dotsb & 0 & 1 \\ 1 & 1 & 0 & 0 & \dotsb & 0 & 0 \\ 0 & 1 & 1 & 0 & \dotsb & 0 & 0 \\ 0 & 0 & 1 & 1 & \ddots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \dotsb & 1 & 0 \\ 0 & 0 & 0 & 0 & \dotsb & 1 & 1 \end{pmatrix}$$ for $$k \geq 3$$.

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:

• -i FORMAT Format of input FILE; default: dense.
• -o FORMAT Format of output matrices; default: dense.
• -sp Output the list of series-parallel reductions.
• -r Output the elements of the reduced matrix.
• -R Output the reduced matrix.
• -n Output the elements of a minimal non-series-parallel submatrix.
• -N Output a minimal non-series-parallel submatrix.
• -s Print statistics about the computation to stderr.

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.