Minimizing Submodular Functions over Hierarchical Families
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _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 |