WorksComputer Science
A Polynomial Time Algorithm for Finding a Minimum 5-Partition of a Submodular Function
Abstract
Given a real-valued submodular function on a finite ground set, the minimum -partition problem asks for a partition into nonempty parts minimizing the sum of their function values. We give a polynomial-time algorithm for . The idea follows directly from the previous result, where there is precisely one obstruction for generalizing it to . We show the special case can be handled by reasoning about a restricted family of -partitions.
Introduction
Let be a finite set and let be submodular, meaning that for all . The minimum -partition problem asks for a partition of into nonempty parts minimizing . The problem is NP-hard when is part of the input [2], and polynomial-time algorithms were known for [6], [5], and [3 Theorem 6.1]. Our algorithm extends the compatibility approach of Hirayama et al. [3] to .
Theorem 1.1 For a submodular function with given by a value oracle, a minimum 5-partition can be found in polynomial time.
By Chandrasekaran and Chekuri [1 Corollary 4.1], this also gives a polynomial-time algorithm for symmetric submodular 6-partition, including minimum-sum 6-partition in hypergraphs with nonnegative edge weights.
After handling small parts, the 4-partition algorithm of Hirayama et al. [3] contracts each pair of parts of a minimum non-trivial 3-partition, where non-trivial means having at least two parts of size at least 2. Their compatibility theorem guarantees that contracting some pair preserves a minimum 4-partition. The analogous compatibility condition for would require three parts of a 4-partition to be contained in parts of a minimum 5-partition. Their concluding example, whose pattern of nonempty pairwise intersections appears in Figure 4.2, shows that this can fail even for graphs [3 Section 7].
Lemma 4.2 proves that every incompatible configuration of a minimum non-trivial 4-partition with the minimum 5-partition has this pattern of nonempty cells when the minimum 5-partition is unique and all its parts have size at least 5. We overcome this obstruction by finding a minimum 3-partition among those in which and lie in the same part of the 4-partition and at least two parts have size at least 3. Lemma 4.3 shows that and each lie in a part of the minimum 5-partition, making compatible with it. Contracting and therefore preserves the minimum 5-partition even when the 4-partition is incompatible. It also leaves the updated 4-partition a minimum non-trivial 4-partition, so the algorithm can repeat this step.
Preliminaries
We follow the terminology and notation of Hirayama et al. [3]. We work in the value-oracle model, where evaluations of and elementary arithmetic operations and comparisons take unit time. All partitions have nonempty parts, and denotes the sum of over the parts of . For , let be the restriction of to . For nonempty , let be the function on obtained from by contracting into a new element , defined by if and if . Both operations preserve submodularity. For a family of nonempty disjoint subsets of , let be obtained by contracting each into a distinct new element . The lift of a subset of the contracted ground set replaces each by the elements of , and the lift of a partition of the contracted ground set is the partition of formed by the lifts of its parts. Lifting preserves partition values, maps distinct partitions to distinct lifts, and composes across iterated contractions. Unless stated otherwise, cardinalities refer to the current ground set.
A set is noncrossing with a partition if it is contained in one of its parts, and otherwise crosses the partition. A partition is compatible with , written , if at least parts of are noncrossing with , and is incompatible with otherwise. The noncrossing parts need not lie in distinct parts of . For an integer , a partition is -non-trivial if at least two parts have size at least . A partition is non-trivial if it is 2-non-trivial, and trivial otherwise. For an integer , a partition is -size if every part has size at least .
For partitions and , write . Their configuration is the matrix with . The sets are its cells. Configurations are equivalent up to row and column permutations. Rows and columns also denote the corresponding parts and . The configuration graph is the bipartite graph with a row vertex for each row, a column vertex for each column, and an edge whenever . For a graph and a vertex set of , write for the subgraph induced by . For a vertex set of , a cell is internal to if both and belong to .
Optimization and Tie-Breaking
For disjoint , minimizing over has only the candidate when , and otherwise reduces to submodular function minimization (SFM) on via . Enumerating disjoint of size therefore finds a minimum -size 2-partition for every fixed in polynomial time [3 Lemma 5.3]. For , a minimum 2-partition is found by minimizing the symmetric submodular function over nonempty using Queyranne’s symmetric submodular function minimization (SSFM) algorithm [6]. For fixed , a minimum -non-trivial 3-partition (called -size in [3]) can be found in polynomial time by [3 Lemmas 5.1 and 5.4]. For , the small-part enumeration in [3 Lemma 5.4] pairs each enumerated set with with a minimum -size 2-partition of , and each with with a minimum 2-partition of , which has a part of size at least because . A minimum 3-partition [5] (see [3 Section 3]) and a minimum 4-partition [3 Theorem 6.1] (using above) can likewise be found in polynomial time. Infeasible subproblems contribute no candidate.
Let be the initial ground set of size , number the unordered pairs by , and define . The function is submodular, and determines the unordered pairs inside parts of , hence . Throughout, compare values lexicographically as , passing to and under restriction and contraction. Every resulting pair orders subsets and partitions identically to for sufficiently small , so minimum partitions are unique and submodular structural lemmas apply. Applying the SFM and SSFM reductions above to gives submodular and symmetric submodular pairs .
Queyranne’s SSFM algorithm [6] and the strongly polynomial, fully combinatorial SFM algorithm at the end of Section 7 of Iwata and Orlin [4] apply directly to every symmetric submodular or submodular pair constructed above. On an -element ground set, Queyranne’s algorithm uses only objective evaluations, additions, subtractions, comparisons, and contractions, while Iwata and Orlin’s algorithm keeps the fixed denominator for convex combinations and uses only additional multiplications by polynomially bounded integers, rounding bounded ratios via comparisons with integer multiples of the divisor without dividing by function values. Their executions on agree with those on for sufficiently small , preserving optimality and the strongly polynomial operation bounds. Since takes -bit integer values and all integer multipliers and denominators are polynomially bounded across polynomially many additions, the second coordinates have bit length polynomial in . Any algorithm that accesses its input only through restrictions, contractions, additions, comparisons, and these SFM and SSFM primitives therefore applies directly to and agrees with its execution on for sufficiently small .
The Auxiliary 3-Partition
For a 4-partition of , let be the family of 3-non-trivial 3-partitions of with and contained in the same part of . Only and are noncrossing with , since contains the other three parts of .
Lemma 2.1. For a submodular function and a 4-partition of with , a minimum partition in can be found in polynomial time.
Proof. Fix and let , with new element . Compute a minimum 3-non-trivial 3-partition of as in § 2.1. Its lift belongs to , since the lift of the part containing contains and therefore has size at least 3, while another part already has size at least 3. Conversely, for any with and , the corresponding partition of is 3-non-trivial and is covered by this call.
Otherwise , so or for some . For each such , compute a minimum 2-partition of when , enumerate all 2-partitions of with when , and skip . Taking a minimum-value candidate over proves the lemma.
Uncrossing
Lemma 2.2. Let be submodular, let and be partitions of , and let be a vertex set of their configuration graph with such that is connected. For each , let be the part of or corresponding to , and write . There is a partition of the union of the cells internal to into parts such that .
Proof. Let . Since is connected, order its vertices as so that each vertex after the first has an earlier neighbor. Set for and for . Each is nonempty because has an earlier neighbor. The sets are disjoint: a nonempty cell internal to is contained in if and only if is the later of its row and column in the ordering. Hence partitions the union of the cells internal to into parts. By submodularity, for . Summing over and using and gives the desired inequality.
Minimum Non-trivial 4-Partitions
Lemma 3.1. For a submodular function with given by a value oracle, a minimum non-trivial 4-partition can be found in polynomial time.
Proof: We use the exchanges of Hirayama et al. [3 Section 4], checking the additional non-triviality condition on the 4-partition. Suppose every minimum non-trivial 4-partition is 13-size. Fix a minimum non-trivial 4-partition and a minimum 5-non-trivial 3-partition . We show that for some minimum non-trivial 4-partition .
Let be the configuration of and , with as rows and as columns, and consider vertex degrees in . Call a row full if all its cells are nonempty, and a cell heavy if its size is at least 5. Every column has a heavy cell, since . At least two rows have size at least 5. The cited exchanges, obtained by Lemma 2.2, satisfy . Whenever is 5-non-trivial and is non-trivial, both are optimal [3 Proposition 4.1]. Thus it suffices that , or that has a part of size at most 12, contradicting the hypothesis.
Call the configuration a cross at column if, after relabeling the rows and setting , the cells are nonempty with heavy, and are nonempty with (Figure 3.1). The cross exchange of [3 Lemma 4.1] sets and . The heavy cell and ensure that is 5-non-trivial, while and make non-trivial. The rows and are noncrossing with , giving compatibility. Hence assume that no cross exists.

Figure 3.1. The cross exchange, where . Here denotes an entry at least , and ? denotes an arbitrary entry. Colors mark the parts of and . After relabeling, and . If all columns have size at least 13, then is 5-non-trivial and is non-trivial.
If two rows have degree 1, compatibility already holds. If a row has degree 2, relabel it as . If it meets columns and , use the exchange of [3 Lemma 4.2]:
where . The parts and ensure that is 5-non-trivial. If , both and have size at least 5. Otherwise , so one of has size at least 3, while at least one of has size at least 5. Thus is non-trivial, and since . Assume henceforth that every row has degree 1 or at least 3, and at most one row has degree 1.
Case 1: every row has degree at least 3. Follow the column-degree cases of [3 Theorem 4.1]. When every column has degree at least 2, any row with an empty cell has size at most 3: such a row of size at least 4 has three nonempty cells, including one of size at least 2, and would give a cross at the column containing its empty cell, since every column has a heavy cell. Thus every row of size at least 4 is full. Since at least two rows have size at least 5, at most one row is not full, so some column has no empty cell. Relabel the rows so that is heavy and is another row of size at least 5. If has a cell of size at least 2 outside , there is a cross at . Otherwise, its three cells outside are singletons, so . Choose such that is nonempty. Column has a heavy cell in or , giving a cross at with .
When some column has degree 1, after relabeling, say , where and meet all of . The absence of a cross forces to be full and all cells in and to have size at most 4. Consequently every cell in is heavy. Use the exchange of [3 Theorem 4.1, Case 3]:
The parts and ensure that is 5-non-trivial. The unions and make non-trivial, but , a contradiction.
Case 2: exactly one row has degree 1. After relabeling, say , where each of and meets at least two of . We adapt the exchanges of [3 Theorem 4.2].
When either or is empty, after relabeling, say . Choose with so that one of has size at least 2. Such a choice exists: if , then , so some cell of outside has size at least 2, while has degree at least 3. Use the exchange
The parts and ensure that is 5-non-trivial. Together with , the part among of size at least 2 makes non-trivial. The rows and are noncrossing with , giving compatibility.
When , relabel and and choose so that the cells are nonempty, one of is heavy, and one of has size at least 2. Such a choice exists: each of has a heavy cell in or , so after relabeling and the row has at least two heavy cells and among . If is heavy, all conditions hold. Otherwise is also heavy, and relabeling so that ensures that whenever . Use the exchange
Then is 5-non-trivial, is non-trivial, and and are noncrossing with .
For the algorithm, let . If , return infeasible, and if $6\le n\le 51$, solve by enumeration. Otherwise enumerate each nonempty of size at most 12, combining with a minimum non-trivial 3-partition of when and with a minimum 3-partition of when n-|S|\ge 40$ when , every resulting 4-partition is non-trivial. Also compute a minimum 5-non-trivial 3-partition (§ 2.1), recurse on for each pair , lift each returned 4-partition to , and return a candidate of minimum value.
If every minimum non-trivial 4-partition is 13-size, some such satisfies . For the two parts of noncrossing with , contracting and changes at most two parts of and leaves at least two parts of size at least 13, so corresponds to a non-trivial 4-partition of of the same value. Conversely, every non-trivial 4-partition of lifts to a non-trivial 4-partition of . For , each recursive call has size , and the measure on instances of size satisfies with , at least two positive terms, and immediate termination when . Thus the recursion tree has nodes, each taking polynomial time.
Configurations of 4- and 5-Partitions
Throughout this section, consider a bipartite graph on rows and columns . Call a row of degree 1 a leaf row and its unique incident edge a leaf edge. Let , and write for the set of indices such that is an edge. A connected 4/5 split is a partition of the vertices into sets of sizes 4 and 5, respectively, each inducing a connected subgraph. When the graph is the configuration graph of a 4-partition and a 5-partition , applying Lemma 2.2 to a connected 4/5 split gives partitions
where and have three and four parts, respectively. If a cell internal to has size at least 2, or if contains a 4-cycle, then some part of has size at least 2: in the latter case at least four nonempty cells internal to are distributed among three parts. Together with a column of size at least 5 in , this makes non-trivial. Placing any leaf rows belonging to last in the vertex ordering in the proof of Lemma 2.2 retains each such leaf row as a part of .
Lemma 4.1 Let be a connected bipartite graph with rows and columns . Assume that no row has degree 2.
(i) Suppose that has at most one leaf row. Then at least one of the following holds:
(a) Some column has, for each incident edge, a connected 4/5 split in which contains both endpoints of the edge and exactly two rows.
(b) There is a connected 4/5 split such that contains a 4-cycle.
(ii) Suppose that has exactly two leaf rows with distinct neighbors and is not, up to relabeling, the graph with leaf edges and and neighborhoods and . Then some column has, for each incident edge, a connected 4/5 split in which contains both endpoints of the edge and one or two rows.
In (i)(a) and (ii), the split may depend on the edge.
Proof: When has no leaf rows, every row has degree at least 3. We find a connected 4/5 split such that contains a 4-cycle. Pass to a spanning subgraph obtained by retaining three edges at each row while keeping all columns covered: if some column is uncovered, replace a retained edge by an unretained edge , where is also covered by another row, as any two rows cover at least one common column. Let be the missing pair of in this subgraph. We need a 2-element set of row indices, its complement , and a 2-element set of column indices such that
The first condition makes a 4-cycle. The last two conditions ensure that the rows indexed by cover all columns outside and share at least one such column. Thus the complement is connected. When two missing pairs coincide, choose their row indices for . The rows indexed by cover the same three columns, including those indexed by . If , take . If , add any other common neighbor index of the rows indexed by . If , avoid the unique common neighbor index of the rows indexed by . These choices satisfy all three conditions. When the four missing pairs are distinct, view them as four edges on . The star with four edges is excluded because every column is covered. With denoting , each row of the table below satisfies the three conditions, covering the remaining cases up to relabeling.
| Missing pairs | Missing pairs indexed by | |
Table 1.
When has a single leaf row adjacent to , let and write for . Since each have degree at least 3, we have . Consider an arbitrary non-leaf edge at , say . For , try and . If , take the unique index , which lies in because is covered. If and , choose avoiding the unique element of when . Connectedness gives at least one non-leaf edge at , and any such split also covers , so is the required column whenever this construction works for every non-leaf edge at . Otherwise, assume that it fails for . Then and are equal or disjoint 2-element sets. If , then is a 4-cycle for , and its complement is connected because is adjacent to and to both columns indexed by . If , both and are adjacent to . Interchange and if needed, choose , and use . Its complement is connected through and . The only edges incident with are and , both inside . Thus is the required column.
When the leaf edges are and , let . Write and for . Connectedness gives and . Figure 4.1 gives the two split templates. Write for template (a), and for template (b). The templates with subscript 4 are obtained by interchanging and, for template (a), also and .

Figure 4.1. The two-leaf case of Lemma 4.1. In (a), . The blue and green blocks mark the row-column pairs with both vertices in and in , respectively, and the entries marked ensure that and are connected. In (c), is the excluded graph in Lemma 4.1(ii). The symbols and ? have the meanings in Figure 3.1.
Up to these interchanges, has the four types below. Each row gives a column index and splits covering all edges at , allowing different splits per edge.
| Column index | Splits | ||
| the exception in Figure 4.1(c) | |||
| any | |||
| and |
Table 4.1.
In the second type, interchange with if needed. In the fourth, interchange if needed. A proper subset used in the table has size 2, so makes valid. In the last two types, when , template covers and covers at any . The first type has by the degree bound, giving either or the stated exception.
Lemma 4.2 Let be submodular, let be a minimum non-trivial 4-partition of , and let be the unique minimum 5-partition of . If is 5-size and is incompatible with , their configuration has the nonempty cells in Figure 4.2, up to relabeling.

Figure 4.2. The configuration in Lemma 4.2. Rows are parts of and columns are parts of . Named cells are nonempty, and 0 denotes an empty cell. Thus and , with . This is the obstruction in [3 Section 7].
Proof: If a row has degree 2, apply Lemma 2.2 to the vertex set consisting of and its two neighboring columns, which induces a connected subgraph. The new 5-partition consists of the two nonempty cells of and the other three rows, while the new 4-partition consists of the resulting union and the three untouched columns. The latter is non-trivial. Since is minimum among non-trivial 4-partitions, the new 5-partition is also minimum and is compatible with it, contradicting the uniqueness of . This is the degree-2 exchange of [3 Lemma 4.2], with one additional untouched row and column. Thus every row has degree 1 or at least 3, and at most two rows are leaf rows.
We claim that two leaf rows share a column. Suppose otherwise. If is connected and is not the exception in Lemma 4.1(ii), each column has size at least 5 and therefore contains a cell of size at least 2. Applying Lemma 4.1 (at such a cell in cases (i)(a) and (ii)) and Lemma 2.2 yields a non-trivial 4-partition and a minimum 5-partition . Either contains two rows, so the part of contains two rows of , or contains one row and contains both leaf rows, which remain separate parts of while the row in lies in , giving . Since no two leaf rows share a column, no part of contains two rows of , and is incompatible with . Thus in both cases, contradicting the uniqueness of . For the exception, with and , uncrossing successively with and , and with , gives
again with non-trivial and .
If is disconnected, all rows of degree at least 3 lie in the same component, since any such row has at least three neighbors among the five columns. Unless two leaf rows share a column, another component is an isolated edge, say . For , the partition is the unique minimum 4-partition and is 5-size. The restricted ground set has at least 20 elements. Every 3-partition of this ground set has a part of size at least 2, so adjoining gives a non-trivial 4-partition. Thus the three remaining rows of form a minimum 3-partition of . Either they are non-trivial, or their two singletons together with already make compatible with . In the former case, [3 Theorem 4.3] implies that two of the remaining rows are noncrossing with , hence with , contradicting incompatibility. This proves the claim.
Relabel so that the leaf rows are and , both adjacent to . The rows and both have degree at least 3, and for every . For any 2-element set such that satisfies and , applying Lemma 2.2 to and to gives
@page 8/11 starts_mid=1 ends_mid=1

Figure 4.2 (PDF p. 8). The configuration in Lemma 4.2. Rows are parts of and columns are parts of . Named cells are nonempty, and 0 denotes an empty cell. Thus and , with . This is the obstruction in [3 Section 7].
Proof: If a row has degree 2, apply Lemma 2.2 to the vertex set consisting of and its two neighboring columns, which induces a connected subgraph. The new 5-partition consists of the two nonempty cells of and the other three rows, while the new 4-partition consists of the resulting union and the three untouched columns. The latter is non-trivial. Since is minimum among non-trivial 4-partitions, the new 5-partition is also minimum and is compatible with it, contradicting the uniqueness of . This is the degree-2 exchange of [3 Lemma 4.2], with one additional untouched row and column. Thus every row has degree 1 or at least 3, and at most two rows are leaf rows.
We claim that two leaf rows share a column. Suppose otherwise. If is connected and is not the exception in Lemma 4.1(ii), each column has size at least 5 and therefore contains a cell of size at least 2. Applying Lemma 4.1 (at such a cell in cases (i)(a) and (ii)) and Lemma 2.2 yields a non-trivial 4-partition and a minimum 5-partition . Either contains two rows, so the part of contains two rows of , or contains one row and contains both leaf rows, which remain separate parts of while the row in lies in , giving . Since no two leaf rows share a column, no part of contains two rows of , and is incompatible with . Thus in both cases, contradicting the uniqueness of . For the exception, with and , uncrossing successively with and , and with , gives
again with non-trivial and .
If is disconnected, all rows of degree at least 3 lie in the same component, since any such row has at least three neighbors among the five columns. Unless two leaf rows share a column, another component is an isolated edge, say . For , the partition is the unique minimum 4-partition and is 5-size. The restricted ground set has at least 20 elements. Every 3-partition of this ground set has a part of size at least 2, so adjoining gives a non-trivial 4-partition. Thus the three remaining rows of form a minimum 3-partition of . Either they are non-trivial, or their two singletons together with already make compatible with . In the former case, [3 Theorem 4.3] implies that two of the remaining rows are noncrossing with , hence with , contradicting incompatibility. This proves the claim.
Relabel so that the leaf rows are and , both adjacent to . The rows and both have degree at least 3, and for every . For any 2-element set such that satisfies and , applying Lemma 2.2 to and to gives
which have four and five parts, respectively. Whenever is non-trivial, is also a minimum 5-partition and satisfies , contradicting the uniqueness of . If , choose to consist of one index in when , or two indices in when . In both cases the untouched column makes non-trivial. By symmetry, . The sets and each have size at least 2 and satisfy . Unless , relabel so that , giving and , and choose with . Setting gives and . If , an untouched column in makes non-trivial. If , each column with has size at least 5, so relabeling gives for some , and choosing gives so that and make non-trivial. Hence , and makes and disjoint, as asserted. □
Lemma 4.3 Let be submodular, let be a minimum non-trivial 4-partition of , and let be the unique minimum 5-partition of . Suppose is 5-size and is incompatible with , and let minimize over with in one part of . Then and are noncrossing with .
Proof. Suppose otherwise and, by symmetry, assume that crosses . By Lemma 4.2, , so is contained in or . Interchanging and and the column pairs and if needed, assume , so that and , while . Let for . Since crosses , at least two of the three sets are nonempty.
If all three are nonempty, Lemma 2.2 gives
so and satisfy . Here since have size at least 5, making a minimum 5-partition with , a contradiction.
Otherwise, exactly two of are nonempty, say and , with . Consider
The 4-partition is non-trivial because has at least two parts of size at least 3, and splitting into and produces a part of size at least 2 whenever . Moreover, is a 5-partition and . Submodularity gives
where the second inequality applies submodularity to and and then to and . Adding the remaining part values gives , using and together with . Since the partitions are optimal in their respective families, is also a minimum 5-partition. But and are separate in and together in , contradicting the uniqueness of . □
The Algorithm
For a submodular function on a current ground set with , let be a minimum 5-partition of among those having a part of size at most 4. Enumerate each nonempty with and combine with a minimum 4-partition of . This computes in polynomial time by § 2.1 (see [3 Theorem 6.1]), and for it returns a minimum 5-partition of .
Given , pass to the lexicographic pair from § 2.1, which we still write as . By § 2.1, and Lemmas 2.1 and 3.1 apply directly to and its contractions, and every instance has a unique minimum 5-partition. Figure 5.1 gives the recursive procedure , where is the ground set of the current call and every is to .

Figure 5.1. Compute a minimum 5-partition.
Whenever an iteration reaches the minimization over , the current ground set of has at least 25 elements, so some part of has at least 7 elements. Taking three of them as , one as , and the rest of the ground set as shows that is nonempty. At least one of and has size at least 3, so contracting and reduces the ground-set size of by at least 2. Moreover, the updated 4-partition has in one part and three other nonempty parts, so the ground set of always has at least 5 elements.
Proof (Theorem 1.1): Run on (still written ) and induct on . For , the call returns , which is optimal. Assume and let be the unique minimum 5-partition of . Every candidate placed in or compared with lifts a 5-partition to , so throughout. If , then for some the parts in are noncrossing with , so lifts from a minimum 5-partition of . That contracted ground set has size , so and the recursive call for sets before the loop.
Suppose is incompatible with . At the start of each iteration, either , or has a unique minimum 5-partition lifting to and is a minimum non-trivial 4-partition of incompatible with . If after comparing with , then is 5-size, has at least 25 elements, and is non-trivial, so the iteration continues. By Lemmas 4.2 and 4.3, and each lie in a cell of and . Contracting and maps to a 5-partition of that has the same configuration graph with the updated , so the updated remains incompatible with and its two crossing rows still have degree 3, keeping non-trivial. Since lifting preserves values, is injective, and maps non-trivial 4-partitions to non-trivial 4-partitions, is the unique minimum 5-partition of and the updated remains a minimum non-trivial 4-partition. Each iteration removes at least 2 elements, so the loop terminates and returns .
For the running time, let . On an -element instance with and , each recursive call has , size , and positive measure . Since has at least two positive terms, there are invocations. Each invocation acts on a contraction of at at most elements with second coordinates of bit length polynomial in (in § 2.1), calls Lemma 3.1 once before the loop, and runs iterations that each compute and a minimum partition in (Lemma 2.1), so the algorithm runs in polynomial time. ∎
Acknowledgments GPT-6-Astra were used during the research for proof exploration and checking, and for drafting and editing the manuscript. The authors are responsible for the results and exposition.
References
- [1]Chandrasekaran, K., Chekuri, C.: Min–max partitioning of hypergraphs and symmetric submodular functions. Combinatorica 43(3), 455–477 (2023). https://doi.org/10.1007/s00493-023-00021-y
- [2]Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Mathematics of Operations Research 19(1), 24–37 (1994). https://doi.org/10.1287/moor.19.1.24
- [3]Hirayama, T., Liu, Y., Makino, K., Shi, K., Xu, C.: A polynomial time algorithm for finding a minimum 4-partition of a submodular function. Mathematical Programming 207(1–2), 717–732 (2024). https://doi.org/10.1007/s10107-023-02029-0
- [4]Iwata, S., Orlin, J.B.: A simple combinatorial algorithm for submodular function minimization. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 1230–1237 (2009). https://doi.org/10.1137/1.9781611973068.133
- [5]Okumoto, K., Fukunaga, T., Nagamochi, H.: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica 62(3–4), 787–806 (2012). https://doi.org/10.1007/s00453-010-9483-0
- [6]Queyranne, M.: Minimizing symmetric submodular functions. Mathematical Programming 82(1–2), 3–12 (1998). https://doi.org/10.1007/BF01585863