Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.14805 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912987246231552 |
|---|---|
| author | Mizutani, Ryuhei |
| author_facet | Mizutani, Ryuhei |
| contents | This paper considers submodular function minimization (SFM) restricted to a family of subsets. We show that SFM over complements of families with certain hierarchical structures can be solved in polynomial-time. This yields a polynomial-time algorithm for SFM over complements of various families, such as intersecting families, crossing families, and the unions of lattices. Moreover, this tractability result partially settles the open question posed by Nägele, Sudakov, and Zenklusen on polynomial-solvability of SFM over the intersection of parity families. Furthermore, our tractability result implies that for a constant positive integer $k$, the $k$-th smallest value of a submodular function can be obtained in polynomial-time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_14805 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Minimizing Submodular Functions over Hierarchical Families Mizutani, Ryuhei Combinatorics This paper considers submodular function minimization (SFM) restricted to a family of subsets. We show that SFM over complements of families with certain hierarchical structures can be solved in polynomial-time. This yields a polynomial-time algorithm for SFM over complements of various families, such as intersecting families, crossing families, and the unions of lattices. Moreover, this tractability result partially settles the open question posed by Nägele, Sudakov, and Zenklusen on polynomial-solvability of SFM over the intersection of parity families. Furthermore, our tractability result implies that for a constant positive integer $k$, the $k$-th smallest value of a submodular function can be obtained in polynomial-time. |
| title | Minimizing Submodular Functions over Hierarchical Families |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.14805 |