Combinatorial Matrix Recognition Library

This C/C++ library contains efficient implementations of various algorithms for recognizing combinatorial matrices. It is the successor of the TUtest library. The following matrix classes can be recognized:

• Totally Unimodular Matrices
• Network Matrices
• Complement Totally Unimodular Matrices
• (Strongly) Equimodular and Unimodular Matrices
• Balanced / Balanceable Matrices (currently only via enumerative methods)

Moreover, representation matrices for the following matroid classes can be recognized:

• Binary and ternary regular matroids
• Graphic, cographic and planar matroids
• Series-parallel matroids

The following additional functionality is also part of the library:

• Basic Utilities
• Matrix Entries Inspection
• Camion's Signing Algorithm

The library also contains various instance generators.

The following matrix/matroid classes are planned:

• Totally Balanced Matrices
• Perfect Matrices
• Consecutive Ones
• Max-Flow-Min-Cut Matroids

Installation and Usage

The library can be found on github, or directly as a ZIP Archive. The functionality can be used via command-line tools or via its C interface (see build instructions for more information). There is one executable per matrix/matroid class. Its documentation and that of the interface can be found on the respective pages. The executables accept several File Formats.

Changes and bug fixes are listed here.

License

The software is released under the MIT License. Please cite the paper(s) corresponding to the respective tools.

Authors

• Rolf van der Hulst (graphicness, network matrices)
• Henk Kraaij (balancedness)
• Klaus Truemper (total unimodularity, regularity, complement total unimodularity)
• Matthias Walter (maintainer)

Funding support

• The software library acknowledges support from the Dutch Research Council (NWO) on grant number OCENW.M20.151 (11/2022-10/2026).