Grossman et al. show that the subdeterminants of the incidence ma-
trix of a graph can be characterized using the graph's odd cycle packing
number. In particular, a graph's incidence matrix is totally unimodular
if and only if the graph is bipartite. We extend the characterization of
total unimodularity to disjoint hypergraphs, i.e., hypergraphs whose hy-
peredges of size at least four are pairwise disjoint. Disjoint hypergraphs
interpolate between graphs and hypergraphs, which correspond to arbi-
trary {0, 1}-matrices. We prove that total unimodularity for disjoint hy-
pergraphs is equivalent to forbidding both odd cycles and a structure we
call an “odd tree house”. Our result extends to disjoint directed hyper-
graphs, i.e., those whose incidence matrices allow for {0, ±1}-entries. As
a corollary, we resolve a conjecture on almost totally unimodular matri-
ces, formulated by Padberg (1988) and Cornuéjols & Zuluaga (2000), in
the special case where columns with at least four non-zero elements have
pairwise disjoint supports.
- Poster