A characterization of unimodular hypergraphs with disjoint hyperedges
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915461761859584 |
|---|---|
| author | Caoduro, Marco Neuwohner, Meike Paat, Joseph |
| author_facet | Caoduro, Marco Neuwohner, Meike Paat, Joseph |
| contents | The incidence matrix of a graph is totally unimodular if and only if the graph is bipartite, i.e., it contains no odd cycles. We extend the characterization of total unimodularity to hypergraphs whose hyperedges of size at least four are pairwise disjoint, which we call disjoint hypergraphs. Disjoint hypergraphs have been used to model problems with fairness constraints that ensure balanced representation. We prove that total unimodularity for disjoint hypergraphs is equivalent to forbidding both odd cycles and structures that we call odd tree houses. Our result extends to disjoint mixed hypergraphs, whose incidence matrices have $\{0, \pm1\}$-entries. As a corollary, we resolve a special case of a conjecture on almost totally unimodular matrices, originally posed by Padberg and later modified by Cornuéjols and Zuluaga. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_10593 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A characterization of unimodular hypergraphs with disjoint hyperedges Caoduro, Marco Neuwohner, Meike Paat, Joseph Combinatorics Optimization and Control The incidence matrix of a graph is totally unimodular if and only if the graph is bipartite, i.e., it contains no odd cycles. We extend the characterization of total unimodularity to hypergraphs whose hyperedges of size at least four are pairwise disjoint, which we call disjoint hypergraphs. Disjoint hypergraphs have been used to model problems with fairness constraints that ensure balanced representation. We prove that total unimodularity for disjoint hypergraphs is equivalent to forbidding both odd cycles and structures that we call odd tree houses. Our result extends to disjoint mixed hypergraphs, whose incidence matrices have $\{0, \pm1\}$-entries. As a corollary, we resolve a special case of a conjecture on almost totally unimodular matrices, originally posed by Padberg and later modified by Cornuéjols and Zuluaga. |
| title | A characterization of unimodular hypergraphs with disjoint hyperedges |
| topic | Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2411.10593 |