betaFeedback

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 kk-partition problem asks for a partition into kk nonempty parts minimizing the sum of their function values. We give a polynomial-time algorithm for k=5k=5. The idea follows directly from the previous k=4k=4 result, where there is precisely one obstruction for generalizing it to k=5k=5. We show the special case can be handled by reasoning about a restricted family of 33-partitions.

Introduction

Let VV be a finite set and let f:2V→Rf : 2^V \to\mathbb{R} be submodular, meaning that f(X)+f(Y)≥f(X∩Y)+f(X∪Y)f(X) + f(Y) \ge f(X \cap Y) + f(X \cup Y) for all X,Y⊆VX, Y \subseteq V. The minimum kk-partition problem asks for a partition P={V1,…,Vk}\mathcal{P} = \{V_1, \ldots, V_k\} of VV into nonempty parts minimizing f(P)=∑i=1kf(Vi)f(\mathcal{P}) = \sum_{i=1}^{k} f(V_i). The problem is NP-hard when kk is part of the input [2], and polynomial-time algorithms were known for k=2k = 2 [6], k=3k = 3 [5], and k=4k = 4 [3 Theorem 6.1]. Our algorithm extends the compatibility approach of Hirayama et al. [3] to k=5k = 5.

Theorem 1.1 For a submodular function f:2V→Rf : 2^V \to\mathbb{R} with ∣V∣≥5|V| \ge5 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 k=5k = 5 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 {P,Q,R}\{P,Q,R\} among those in which PP and QQ lie in the same part of the 4-partition and at least two parts have size at least 3. Lemma 4.3 shows that PP and QQ each lie in a part of the minimum 5-partition, making {P,Q,R}\{P,Q,R\} compatible with it. Contracting PP and QQ 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 ff and elementary arithmetic operations and comparisons take unit time. All partitions have nonempty parts, and f(P)f(\mathcal{P}) denotes the sum of ff over the parts of P\mathcal{P}. For U⊆VU \subseteq V, let f\Uf_{\backslash U} be the restriction of ff to V∖UV \setminus U. For nonempty U⊆VU \subseteq V, let f/Uf/U be the function on (V∖U)∪{u}(V \setminus U) \cup\{u\} obtained from ff by contracting UU into a new element u∉Vu \notin V, defined by f/U(S)=f(S)f/U(S) = f(S) if u∉Su \notin S and f/U(S)=f((S∖{u})∪U)f/U(S) = f((S \setminus\{u\}) \cup U) if u∈Su \in S. Both operations preserve submodularity. For a family A\mathcal{A} of nonempty disjoint subsets of VV, let f/Af/\mathcal{A} be obtained by contracting each A∈AA \in\mathcal{A} into a distinct new element uAu_A. The lift of a subset SS of the contracted ground set replaces each uA∈Su_A \in S by the elements of AA, and the lift lift⁡(P)\operatorname{lift}(\mathcal{P}) of a partition P\mathcal{P} of the contracted ground set is the partition of VV 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 X\mathcal{X} is compatible with Y\mathcal{Y}, written X≺Y\mathcal{X} \prec\mathcal{Y}, if at least ∣X∣−1|\mathcal{X}|-1 parts of X\mathcal{X} are noncrossing with Y\mathcal{Y}, and is incompatible with Y\mathcal{Y} otherwise. The noncrossing parts need not lie in distinct parts of Y\mathcal{Y}. For an integer ℓ≥2\ell\ge2, a partition is ℓ\ell-non-trivial if at least two parts have size at least ℓ\ell. A partition is non-trivial if it is 2-non-trivial, and trivial otherwise. For an integer h≥1h \ge1, a partition is hh-size if every part has size at least hh.

For partitions X={X1,…,Xp}\mathcal{X} = \{X_1,\ldots,X_p\} and Y={Y1,…,Yq}\mathcal{Y} = \{Y_1,\ldots,Y_q\}, write Zij=Xi∩YjZ_{ij} = X_i \cap Y_j. Their configuration is the matrix MM with Mij=∣Zij∣M_{ij} = |Z_{ij}|. The sets ZijZ_{ij} are its cells. Configurations are equivalent up to row and column permutations. Rows and columns also denote the corresponding parts X1,…,XpX_1,\ldots,X_p and Y1,…,YqY_1,\ldots,Y_q. The configuration graph G(M)G(M) is the bipartite graph with a row vertex XiX_i for each row, a column vertex YjY_j for each column, and an edge XiYjX_iY_j whenever Mij>0M_{ij} > 0. For a graph GG and a vertex set UU of GG, write G[U]G[U] for the subgraph induced by UU. For a vertex set UU of G(M)G(M), a cell ZijZ_{ij} is internal to UU if both XiX_i and YjY_j belong to UU.

Optimization and Tie-Breaking

For disjoint I,E⊆VI,E \subseteq V, minimizing X↦f(X)+f(V∖X)X \mapsto f(X) + f(V \setminus X) over I⊆X⊆V∖EI \subseteq X \subseteq V \setminus E has only the candidate X=IX = I when I∪E=VI \cup E = V, and otherwise reduces to submodular function minimization (SFM) on V∖(I∪E)V \setminus(I \cup E) via A↦f(I∪A)+f(V∖(I∪A))A \mapsto f(I \cup A) + f(V \setminus(I \cup A)). Enumerating disjoint I,EI,E of size hh therefore finds a minimum hh-size 2-partition for every fixed h≥2h \ge2 in polynomial time [3 Lemma 5.3]. For ∣V∣≥2|V| \ge2, a minimum 2-partition is found by minimizing the symmetric submodular function S↦f(S)+f(V∖S)S \mapsto f(S) + f(V \setminus S) over nonempty S⊊VS \subsetneq V using Queyranne’s symmetric submodular function minimization (SSFM) algorithm [6]. For fixed ℓ≥2\ell\ge2, a minimum ℓ\ell-non-trivial 3-partition (called (1,ℓ)(1,\ell)-size in [3]) can be found in polynomial time by [3 Lemmas 5.1 and 5.4]. For ∣V∣≥18ℓ−16|V| \ge18\ell- 16, the small-part enumeration in [3 Lemma 5.4] pairs each enumerated set SS with 1≤∣S∣<ℓ1 \le|S| < \ell with a minimum ℓ\ell-size 2-partition of fSf_S, and each SS with ℓ≤∣S∣≤4ℓ−4\ell\le|S| \le4\ell- 4 with a minimum 2-partition of fSf_S, which has a part of size at least ℓ\ell because ∣V∖S∣≥14ℓ−12≥2ℓ−1|V \setminus S| \ge14\ell- 12 \ge2\ell- 1. A minimum 3-partition [5] (see [3 Section 3]) and a minimum 4-partition [3 Theorem 6.1] (using ℓ=2\ell= 2 above) can likewise be found in polynomial time. Infeasible subproblems contribute no candidate.

Let V0V_0 be the initial ground set of size n0=∣V0∣n_0 = |V_0|, number the unordered pairs e∈(V02)e \in\binom{V_0}{2} by r(e)∈{1,…,(n02)}r(e) \in\{1,\ldots,\binom{n_0}{2}\}, and define ψ(S)=−∑e∈(S2)2r(e)\psi(S) = -\sum_{e \in\binom{S}{2}} 2^{r(e)}. The function ψ\psi is submodular, and ψ(P)\psi(\mathcal{P}) determines the unordered pairs inside parts of P\mathcal{P}, hence P\mathcal{P}. Throughout, compare values lexicographically as (f,ψ)(f,\psi), passing to (f\U,ψ\U)(f_{\backslash U},\psi_{\backslash U}) and (f/U,ψ/U)(f/U,\psi/U) under restriction and contraction. Every resulting pair (g,ϕ)(g,\phi) orders subsets and partitions identically to g+ϵϕg+\epsilon\phi for sufficiently small ϵ>0\epsilon> 0, so minimum partitions are unique and submodular structural lemmas apply. Applying the SFM and SSFM reductions above to (g,ϕ)(g,\phi) gives submodular and symmetric submodular pairs (f′,ψ′)(f',\psi').

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 (f′,ψ′)(f',\psi') constructed above. On an mm-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 16m416m^{4} 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 (f′,ψ′)(f',\psi') agree with those on f′+εψ′f'+\varepsilon\psi' for sufficiently small ε>0\varepsilon>0, preserving optimality and the strongly polynomial operation bounds. Since ψ′\psi' takes O(n02)O(n_{0}^{2})-bit integer values and all integer multipliers and denominators are polynomially bounded across polynomially many additions, the second coordinates have bit length polynomial in n0n_{0}. Any algorithm that accesses its input only through restrictions, contractions, additions, comparisons, and these SFM and SSFM primitives therefore applies directly to (g,ϕ)(g,\phi) and agrees with its execution on g+εϕg+\varepsilon\phi for sufficiently small ε>0\varepsilon>0.

The Auxiliary 3-Partition

For a 4-partition X\mathcal{X} of VV, let FX\mathcal{F}_{\mathcal{X}} be the family of 3-non-trivial 3-partitions Z={P,Q,R}\mathcal{Z}=\{P,Q,R\} of VV with PP and QQ contained in the same part of X\mathcal{X}. Only PP and QQ are noncrossing with X\mathcal{X}, since RR contains the other three parts of X\mathcal{X}.

Lemma 2.1. For a submodular function f:2V→Rf:2^{V}\to\mathbb{R} and a 4-partition X\mathcal{X} of VV with FX≠∅\mathcal{F}_{\mathcal{X}}\ne\varnothing, a minimum partition in FX\mathcal{F}_{\mathcal{X}} can be found in polynomial time.

Proof. Fix Xi∈XX_i\in\mathcal{X} and let g=f/(V∖Xi)g=f_{/(V\setminus X_i)}, with new element zz. Compute a minimum 3-non-trivial 3-partition of gg as in § 2.1. Its lift belongs to FX\mathcal{F}_{\mathcal{X}}, since the lift of the part containing zz contains V∖XiV\setminus X_i and therefore has size at least 3, while another part already has size at least 3. Conversely, for any {P,Q,R}∈FX\{P,Q,R\}\in\mathcal{F}_{\mathcal{X}} with P,Q⊆XiP,Q\subseteq X_i and ∣R∩Xi∣≥2|R\cap X_i|\ge2, the corresponding partition {P,Q,(R∩Xi)∪{z}}\{P,Q,(R\cap X_i)\cup\{z\}\} of gg is 3-non-trivial and is covered by this call.

Otherwise ∣R∩Xi∣≤1|R\cap X_i|\le1, so R=V∖XiR=V\setminus X_i or R=(V∖Xi)∪{v}R=(V\setminus X_i)\cup\{v\} for some v∈Xiv\in X_i. For each such RR, compute a minimum 2-partition of f∖Rf_{\setminus R} when ∣Xi∖R∣≥5|X_i\setminus R|\ge5, enumerate all 2-partitions {P,Q}\{P,Q\} of Xi∖RX_i\setminus R with max⁡(∣P∣,∣Q∣)=3\max(|P|,|Q|)=3 when ∣Xi∖R∣=4|X_i\setminus R|=4, and skip ∣Xi∖R∣≤3|X_i\setminus R|\le3. Taking a minimum-value candidate over Xi∈XX_i\in\mathcal{X} proves the lemma. □\square

Uncrossing

Lemma 2.2. Let f:2V→Rf:2^{V}\to\mathbb{R} be submodular, let X\mathcal{X} and Y\mathcal{Y} be partitions of VV, and let UU be a vertex set of their configuration graph G(M)G(M) with ∣U∣≥2|U|\ge2 such that G(M)[U]G(M)[U] is connected. For each v∈Uv\in U, let SvS_v be the part of X\mathcal{X} or Y\mathcal{Y} corresponding to vv, and write U∗=⋃v∈USvU^{*}=\bigcup_{v\in U}S_v. There is a partition LU\mathcal{L}_U of the union of the cells internal to UU into ∣U∣−1|U|-1 parts such that ∑v∈Uf(Sv)≥f(U∗)+f(LU)\sum_{v\in U}f(S_v)\ge f(U^{*})+f(\mathcal{L}_U).

Proof. Let m=∣U∣m=|U|. Since G(M)[U]G(M)[U] is connected, order its vertices as v1,…,vmv_1,\ldots,v_m so that each vertex after the first has an earlier neighbor. Set Ai=⋃r=1iSvrA_i=\bigcup_{r=1}^{i}S_{v_r} for i=1,…,mi=1,\ldots,m and Li=Ai−1∩SviL_i=A_{i-1}\cap S_{v_i} for i=2,…,mi=2,\ldots,m. Each LiL_i is nonempty because viv_i has an earlier neighbor. The sets LiL_i are disjoint: a nonempty cell internal to UU is contained in LiL_i if and only if viv_i is the later of its row and column in the ordering. Hence LU={L2,…,Lm}\mathcal{L}_U=\{L_2,\ldots,L_m\} partitions the union of the cells internal to UU into m−1=∣U∣−1m-1=|U|-1 parts. By submodularity, f(Ai−1)+f(Svi)≥f(Ai)+f(Li)f(A_{i-1})+f(S_{v_i})\ge f(A_i)+f(L_i) for i=2,…,mi=2,\ldots,m. Summing over i=2,…,mi=2,\ldots,m and using A1=Sv1A_1=S_{v_1} and Am=U∗A_m=U^{*} gives the desired inequality. □\square

Minimum Non-trivial 4-Partitions

Lemma 3.1. For a submodular function f:2V→Rf:2^{V}\to\mathbb{R} with ∣V∣≥6|V|\ge6 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 Y={Y1,Y2,Y3,Y4}\mathcal{Y} = \{Y_1,Y_2,Y_3,Y_4\} and a minimum 5-non-trivial 3-partition X={X1,X2,X3}\mathcal{X} = \{X_1,X_2,X_3\}. We show that X⊲Y′\mathcal{X} \lhd\mathcal{Y}' for some minimum non-trivial 4-partition Y′\mathcal{Y}'.

Let MM be the configuration of X\mathcal{X} and Y\mathcal{Y}, with X\mathcal{X} as rows and Y\mathcal{Y} as columns, and consider vertex degrees in G(M)G(M). 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 13>3⋅413 > 3 \cdot4. At least two rows have size at least 5. The cited exchanges, obtained by Lemma 2.2, satisfy f(X′)+f(Y′)≤f(X)+f(Y)f(\mathcal{X}') + f(\mathcal{Y}') \leq f(\mathcal{X}) + f(\mathcal{Y}). Whenever X′\mathcal{X}' is 5-non-trivial and Y′\mathcal{Y}' is non-trivial, both are optimal [3 Proposition 4.1]. Thus it suffices that X⊲Y′\mathcal{X} \lhd\mathcal{Y}', or that Y′\mathcal{Y}' has a part of size at most 12, contradicting the hypothesis.

Call the configuration a cross at column YjY_j if, after relabeling the rows and setting {j,k,l,m}={1,2,3,4}\{j,k,l,m\} = \{1,2,3,4\}, the cells Z1j,Z2jZ_{1j},Z_{2j} are nonempty with Z1jZ_{1j} heavy, and Z3k,Z3l,Z3mZ_{3k},Z_{3l},Z_{3m} are nonempty with ∣Z3k∣≥2|Z_{3k}| \geq2 (Figure 3.1). The cross exchange of [3 Lemma 4.1] sets X′={Z1j,Z2j,X3∪⋃t≠jYt}\mathcal{X}' = \{Z_{1j},Z_{2j},X_3 \cup\bigcup_{t\ne j}Y_t\} and Y′={X1∪X2∪Yj,Z3k,Z3l,Z3m}\mathcal{Y}' = \{X_1 \cup X_2 \cup Y_j,Z_{3k},Z_{3l},Z_{3m}\}. The heavy cell Z1jZ_{1j} and X3∪⋃t≠jYtX_3 \cup\bigcup_{t\ne j}Y_t ensure that X′\mathcal{X}' is 5-non-trivial, while Z3kZ_{3k} and X1∪X2∪YjX_1 \cup X_2 \cup Y_j make Y′\mathcal{Y}' non-trivial. The rows X1X_1 and X2X_2 are noncrossing with Y′\mathcal{Y}', giving compatibility. Hence assume that no cross exists.

The cross exchange

Figure 3.1. The cross exchange, where {j,k,l,m}={1,2,3,4}\{j,k,l,m\} = \{1,2,3,4\}. Here a+a^{+} denotes an entry at least aa, and ? denotes an arbitrary entry. Colors mark the parts of Y′={X1∪X2∪Yj,Z3k,Z3l,Z3m}\mathcal{Y}' = \{X_1 \cup X_2 \cup Y_j,Z_{3k},Z_{3l},Z_{3m}\} and X′={Z1j,Z2j,X3∪⋃t≠jYt}\mathcal{X}' = \{Z_{1j},Z_{2j},X_3 \cup\bigcup_{t\ne j}Y_t\}. After relabeling, ∣Z1j∣≥5|Z_{1j}| \geq5 and ∣Z3k∣≥2|Z_{3k}| \geq2. If all columns have size at least 13, then X′\mathcal{X}' is 5-non-trivial and Y′\mathcal{Y}' is non-trivial.

If two rows have degree 1, compatibility already holds. If a row has degree 2, relabel it as X1X_1. If it meets columns YjY_j and YkY_k, use the exchange of [3 Lemma 4.2]:

X′={X1∪Yj∪Yk,Yl,Ym},Y′={Z1j,Z1k,X2,X3}.\mathcal{X}' = \{X_1 \cup Y_j \cup Y_k,Y_l,Y_m\}, \qquad\mathcal{Y}' = \{Z_{1j},Z_{1k},X_2,X_3\}.

where {j,k,l,m}={1,2,3,4}\{j,k,l,m\} = \{1,2,3,4\}. The parts YlY_l and YmY_m ensure that X′\mathcal{X}' is 5-non-trivial. If ∣X1∣<5|X_1| < 5, both X2X_2 and X3X_3 have size at least 5. Otherwise ∣X1∣≥5|X_1| \geq5, so one of Z1j,Z1kZ_{1j},Z_{1k} has size at least 3, while at least one of X2,X3X_2,X_3 has size at least 5. Thus Y′\mathcal{Y}' is non-trivial, and X⊲Y′\mathcal{X} \lhd\mathcal{Y}' since X2,X3∈Y′X_2,X_3 \in\mathcal{Y}'. 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 YtY_t has no empty cell. Relabel the rows so that Z1tZ_{1t} is heavy and X2X_2 is another row of size at least 5. If X2X_2 has a cell of size at least 2 outside YtY_t, there is a cross at YtY_t. Otherwise, its three cells outside YtY_t are singletons, so ∣Z2t∣≥2|Z_{2t}| \geq2. Choose u≠tu \ne t such that Z3uZ_{3u} is nonempty. Column YuY_u has a heavy cell in X1X_1 or X3X_3, giving a cross at YuY_u with X2X_2.

When some column has degree 1, after relabeling, say Y1⊆X1Y_1 \subseteq X_1, where X2X_2 and X3X_3 meet all of Y2,Y3,Y4Y_2,Y_3,Y_4. The absence of a cross forces X1X_1 to be full and all cells in X2X_2 and X3X_3 to have size at most 4. Consequently every cell in X1X_1 is heavy. Use the exchange of [3 Theorem 4.1, Case 3]:

X′={X2∪X3∪Y2∪Y3,Y1,Z14},Y′={Z22,Z23,Z32∪Z33,X1∪Y4}.\mathcal{X}' = \{X_2 \cup X_3 \cup Y_2 \cup Y_3, Y_1, Z_{14}\}, \qquad\mathcal{Y}' = \{Z_{22}, Z_{23}, Z_{32} \cup Z_{33}, X_1 \cup Y_4\}.

The parts Y1Y_1 and Z14Z_{14} ensure that X′\mathcal{X}' is 5-non-trivial. The unions Z32∪Z33Z_{32}\cup Z_{33} and X1∪Y4X_1\cup Y_4 make Y′\mathcal{Y}' non-trivial, but ∣Z22∣≤4|Z_{22}| \le4, a contradiction.

Case 2: exactly one row has degree 1. After relabeling, say X1⊆Y1X_1 \subseteq Y_1, where each of X2X_2 and X3X_3 meets at least two of Y2,Y3,Y4Y_2,Y_3,Y_4. We adapt the exchanges of [3 Theorem 4.2].

When either Z21Z_{21} or Z31Z_{31} is empty, after relabeling, say Z31=∅Z_{31}=\varnothing. Choose {j,k,l}={2,3,4}\{j,k,l\}=\{2,3,4\} with Z2j≠∅Z_{2j}\ne\varnothing so that one of X1,Z3k,Z3lX_1,Z_{3k},Z_{3l} has size at least 2. Such a choice exists: if ∣X1∣=1|X_1|=1, then ∣X3∣≥5|X_3|\ge5, so some cell of X3X_3 outside Y1Y_1 has size at least 2, while X2X_2 has degree at least 3. Use the exchange

X′={X3∪Yk∪Yl,Y1,Z2j},Y′={X2∪Yj,X1,Z3k,Z3l}.\mathcal{X}' = \{X_3 \cup Y_k \cup Y_l, Y_1, Z_{2j}\}, \qquad\mathcal{Y}' = \{X_2 \cup Y_j, X_1, Z_{3k}, Z_{3l}\}.

The parts X3∪Yk∪YlX_3 \cup Y_k \cup Y_l and Y1Y_1 ensure that X′\mathcal{X}' is 5-non-trivial. Together with X2∪YjX_2 \cup Y_j, the part among X1,Z3k,Z3lX_1,Z_{3k},Z_{3l} of size at least 2 makes Y′\mathcal{Y}' non-trivial. The rows X1X_1 and X2X_2 are noncrossing with Y′\mathcal{Y}', giving compatibility.

When Z21,Z31≠∅Z_{21},Z_{31}\ne\varnothing, relabel X2X_2 and X3X_3 and choose {j,k,l}={2,3,4}\{j,k,l\}=\{2,3,4\} so that the cells Z2j,Z2k,Z3lZ_{2j},Z_{2k},Z_{3l} are nonempty, one of Z2j,Z2kZ_{2j},Z_{2k} is heavy, and one of X1,Z31,Z3lX_1,Z_{31},Z_{3l} has size at least 2. Such a choice exists: each of Y2,Y3,Y4Y_2,Y_3,Y_4 has a heavy cell in X2X_2 or X3X_3, so after relabeling X2X_2 and X3X_3 the row X2X_2 has at least two heavy cells Z2jZ_{2j} and Z2kZ_{2k} among Y2,Y3,Y4Y_2,Y_3,Y_4. If Z3lZ_{3l} is heavy, all conditions hold. Otherwise Z2lZ_{2l} is also heavy, and relabeling j,k,lj,k,l so that ∣Z3l∣≥max⁡(∣Z3j∣,∣Z3k∣)|Z_{3l}| \ge\max(|Z_{3j}|,|Z_{3k}|) ensures that max⁡(∣Z31∣,∣Z3l∣)≥2\max(|Z_{31}|,|Z_{3l}|)\ge2 whenever ∣X1∣=1|X_1|=1. Use the exchange

X′={X3∪Y1∪Yl,Z2j,Z2k},Y′={X2∪Yj∪Yk,X1,Z31,Z3l}.\mathcal{X}' = \{X_3 \cup Y_1 \cup Y_l, Z_{2j}, Z_{2k}\}, \qquad\mathcal{Y}' = \{X_2 \cup Y_j \cup Y_k, X_1, Z_{31}, Z_{3l}\}.

Then X′\mathcal{X}' is 5-non-trivial, Y′\mathcal{Y}' is non-trivial, and X1X_1 and X2X_2 are noncrossing with Y′\mathcal{Y}'.

For the algorithm, let n=∣V∣n=|V|. If n<6n<6, return infeasible, and if $6\le n\le 51$, solve by enumeration. Otherwise enumerate each nonempty SS of size at most 12, combining {S}\{S\} with a minimum non-trivial 3-partition of f∖Sf\setminus S when ∣S∣=1|S|=1 and with a minimum 3-partition of f∖Sf\setminus S when 2≤∣S∣≤12(xref‘Section2.1‘).Since2\le|S|\le12 ({xref}`Section 2.1`). Sincen-|S|\ge 40$ when ∣S∣≥2|S|\ge2, every resulting 4-partition is non-trivial. Also compute a minimum 5-non-trivial 3-partition X={X1,X2,X3}\mathcal{X}=\{X_1,X_2,X_3\} (§ 2.1), recurse on f/{Xj,Xk}f/\{X_j,X_k\} for each pair {Xj,Xk}⊆X\{X_j,X_k\}\subseteq\mathcal{X}, lift each returned 4-partition to VV, and return a candidate of minimum value.

If every minimum non-trivial 4-partition is 13-size, some such Y\mathcal{Y} satisfies X⪯Y\mathcal{X}\preceq\mathcal{Y}. For the two parts Xj,XkX_j,X_k of X\mathcal{X} noncrossing with Y\mathcal{Y}, contracting XjX_j and XkX_k changes at most two parts of Y\mathcal{Y} and leaves at least two parts of size at least 13, so Y\mathcal{Y} corresponds to a non-trivial 4-partition of f/{Xj,Xk}f/\{X_j,X_k\} of the same value. Conversely, every non-trivial 4-partition of f/{Xj,Xk}f/\{X_j,X_k\} lifts to a non-trivial 4-partition of VV. For ai=∣Xi∣a_i=|X_i|, each recursive call has size ai+2<na_i+2<n, and the measure m−3m-3 on instances of size m≥6m\ge6 satisfies ∑i=13(ai−1)=n−3\sum_{i=1}^{3}(a_i-1)=n-3 with ai−1≥0a_i-1\ge0, at least two positive terms, and immediate termination when ai+2<6a_i+2<6. Thus the recursion tree has O(n)O(n) nodes, each taking polynomial time.

Configurations of 4- and 5-Partitions

Throughout this section, consider a bipartite graph on rows X1,…,X4X_1,\ldots,X_4 and columns Y1,…,Y5Y_1,\ldots,Y_5. Call a row of degree 1 a leaf row and its unique incident edge a leaf edge. Let F={1,2,3,4,5}F=\{1,2,3,4,5\}, and write N(Xi)=FN(X_i)=F for the set of indices jj such that XiYjX_iY_j is an edge. A connected 4/5 split is a partition of the vertices into sets U,WU,W of sizes 4 and 5, respectively, each inducing a connected subgraph. When the graph is the configuration graph G(M)G(M) of a 4-partition X\mathcal{X} and a 5-partition Y\mathcal{Y}, applying Lemma 2.2 to a connected 4/5 split (U,W)(U,W) gives partitions

X′={W∗}∪U,Y′={U∗}∪W,f(X′)+f(Y′)≤f(X)+f(Y),\mathcal{X}' = \{W^*\}\cup\mathcal{U}, \qquad\mathcal{Y}' = \{U^*\}\cup\mathcal{W}, \qquad f(\mathcal{X}')+f(\mathcal{Y}')\le f(\mathcal{X})+f(\mathcal{Y}),

where LU\mathcal{L}_U and LW\mathcal{L}_W have three and four parts, respectively. If a cell internal to UU has size at least 2, or if G(M)[U]G(M)[U] contains a 4-cycle, then some part of LU\mathcal{L}_U has size at least 2: in the latter case at least four nonempty cells internal to UU are distributed among three parts. Together with a column of size at least 5 in WW, this makes X′X' non-trivial. Placing any leaf rows belonging to WW last in the vertex ordering in the proof of Lemma 2.2 retains each such leaf row as a part of LW\mathcal{L}_W.

Lemma 4.1 Let GG be a connected bipartite graph with rows X1,…,X4X_1,\ldots,X_4 and columns Y1,…,Y5Y_1,\ldots,Y_5. Assume that no row has degree 2.

(i) Suppose that GG 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 (U,W)(U,W) in which UU contains both endpoints of the edge and exactly two rows.

(b) There is a connected 4/5 split (U,W)(U,W) such that G[U]G[U] contains a 4-cycle.

(ii) Suppose that GG has exactly two leaf rows with distinct neighbors and is not, up to relabeling, the graph with leaf edges X1Y1X_1Y_1 and X2Y2X_2Y_2 and neighborhoods N(X3)={3,4,5}N(X_3)=\{3,4,5\} and N(X4)=FN(X_4)=F. Then some column has, for each incident edge, a connected 4/5 split (U,W)(U,W) in which UU 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 GG has no leaf rows, every row has degree at least 3. We find a connected 4/5 split (U,W)(U,W) such that G[U]G[U] 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 YjY_j is uncovered, replace a retained edge XiYkX_iY_k by an unretained edge XiYjX_iY_j, where YkY_k is also covered by another row, as any two rows cover at least one common column. Let Ki=F∖N(Xi)K_i=F\setminus N(X_i) be the missing pair of XiX_i in this subgraph. We need a 2-element set AA of row indices, its complement B={1,2,3,4}∖AB=\{1,2,3,4\}\setminus A, and a 2-element set LL of column indices such that

L⊆F∖⋃i∈AKi,⋂i∈BKi⊆L,F∖⋃i∈BKi⊈L.L\subseteq F\setminus\bigcup_{i\in A}K_i,\qquad\bigcap_{i\in B}K_i\subseteq L,\qquad F\setminus\bigcup_{i\in B}K_i\nsubseteq L.

The first condition makes U={Xi:i∈A}∪{Yj:j∈L}U=\{X_i:i\in A\}\cup\{Y_j:j\in L\} a 4-cycle. The last two conditions ensure that the rows indexed by BB cover all columns outside UU and share at least one such column. Thus the complement WW is connected. When two missing pairs coincide, choose their row indices for AA. The rows indexed by AA cover the same three columns, including those indexed by J=⋂i∈BKiJ=\bigcap_{i\in B}K_i. If ∣J∣=2|J|=2, take L=JL=J. If ∣J∣=1|J|=1, add any other common neighbor index of the rows indexed by AA. If J=∅J=\varnothing, avoid the unique common neighbor index of the rows indexed by BB. These choices satisfy all three conditions. When the four missing pairs are distinct, view them as four edges on FF. The star with four edges is excluded because every column is covered. With ijij denoting {i,j}\{i,j\}, each row of the table below satisfies the three conditions, covering the remaining cases up to relabeling.

Missing pairsMissing pairs indexed by AALL
12,23,34,4512,23,34,4512,2312,234,54,5
12,13,14,4512,13,14,4512,1312,134,54,5
12,23,34,1412,23,34,1412,2312,234,54,5
12,23,13,1412,23,13,1412,1412,143,53,5
12,23,13,4512,23,13,4512,2312,234,54,5

Table 1.

When GG has a single leaf row X1X_1 adjacent to Y1Y_1, let T=F∖{1}T=F\setminus\{1\} and write Ti=N(Xi)∩TT_i=N(X_i)\cap T for i=2,3,4i=2,3,4. Since X2,X3,X4X_2,X_3,X_4 each have degree at least 3, we have ∣Ti∣≥2|T_i|\geq2. Consider an arbitrary non-leaf edge at Y1Y_1, say X2Y1X_{2}Y_{1}. For t∈T2t \in T_{2}, try U={X1,X2,Y1,Yt}U = \{X_{1},X_{2},Y_{1},Y_{t}\} and W={X3,X4}∪{Yj:j∈T∖{t}}W = \{X_{3},X_{4}\} \cup\{Y_{j}: j \in T \setminus\{t\}\}. If ∣T3∪T4∣=3|T_{3} \cup T_{4}| = 3, take the unique index t∈T∖(T3∪T4)t \in T \setminus(T_{3} \cup T_{4}), which lies in T2T_{2} because YtY_{t} is covered. If T3∪T4=TT_{3} \cup T_{4} = T and T3∩T4≠∅T_{3} \cap T_{4} \ne\varnothing, choose t∈T2t \in T_{2} avoiding the unique element of T3∩T4T_{3} \cap T_{4} when ∣T3∩T4∣=1|T_{3} \cap T_{4}| = 1. Connectedness gives at least one non-leaf edge at Y1Y_{1}, and any such split also covers X1Y1X_{1}Y_{1}, so Y1Y_{1} is the required column whenever this construction works for every non-leaf edge at Y1Y_{1}. Otherwise, assume that it fails for X2Y1X_{2}Y_{1}. Then T3T_{3} and T4T_{4} are equal or disjoint 2-element sets. If T3=T4T_{3} = T_{4}, then G[U]G[U] is a 4-cycle for U={X3,X4}∪{Yj:j∈T3}U = \{X_{3},X_{4}\} \cup\{Y_{j}: j \in T_{3}\}, and its complement is connected because X2X_{2} is adjacent to Y1Y_{1} and to both columns indexed by T∖T3T \setminus T_{3}. If T3∩T4=∅T_{3} \cap T_{4} = \varnothing, both X3X_{3} and X4X_{4} are adjacent to Y1Y_{1}. Interchange X3X_{3} and X4X_{4} if needed, choose c∈T2∩T3c \in T_{2} \cap T_{3}, and use U={X2,X3}∪{Yj:j∈T3}U = \{X_{2},X_{3}\} \cup\{Y_{j}: j \in T_{3}\}. Its complement is connected through X4X_{4} and Y1Y_{1}. The only edges incident with YcY_{c} are X2YcX_{2}Y_{c} and X3YcX_{3}Y_{c}, both inside G[U]G[U]. Thus YcY_{c} is the required column.

When the leaf edges are X1Y1X_{1}Y_{1} and X2Y2X_{2}Y_{2}, let T={3,4,5}T = \{3,4,5\}. Write Hi=N(Xi)∩{1,2}H_{i} = N(X_{i}) \cap\{1,2\} and Ti=N(Xi)∩TT_{i} = N(X_{i}) \cap T for i=3,4i = 3,4. Connectedness gives H3∪H4={1,2}H_{3} \cup H_{4} = \{1,2\} and T3∪T4=TT_{3} \cup T_{4} = T. Figure 4.1 gives the two split templates. Write I3(t)I_{3}(t) for template (a), and II3II_{3} for template (b). The templates with subscript 4 are obtained by interchanging X3,X4X_{3},X_{4} and, for template (a), also X1,X2X_{1},X_{2} and Y1,Y2Y_{1},Y_{2}.

Two-leaf split templates

Figure 4.1. The two-leaf case of Lemma 4.1. In (a), {t,u,v}={3,4,5}\{t,u,v\} = \{3,4,5\}. The blue and green blocks mark the row-column pairs with both vertices in UU and in WW, respectively, and the entries marked 1+1^{+} ensure that G[U]G[U] and G[W]G[W] are connected. In (c), GG is the excluded graph in Lemma 4.1(ii). The symbols 1+1^{+} and ? have the meanings in Figure 3.1.

Up to these interchanges, (H3,H4)(H_{3},H_{4}) has the four types below. Each row gives a column index tt and splits covering all edges at YtY_{t}, allowing different splits per edge.

(H3,H4)(H_{3},H_{4})(T3,T4)(T_{3},T_{4})Column index ttSplits
(∅,{1,2})(\varnothing,\{1,2\})T4≠TT_{4} \ne Tt∈T∖T4t \in T \setminus T_{4}II3II_{3}
T4=TT_{4} = Tthe exception in Figure 4.1(c)
({1},{2})(\{1\},\{2\})T3≠TT_{3} \ne Tt∈T∖T3t \in T \setminus T_{3}I4(t)I_{4}(t)
T3=T4=TT_{3} = T_{4} = Tany t∈Tt \in TI3(t),I4(t)I_{3}(t), I_{4}(t)
({1},{1,2})(\{1\},\{1,2\})T3≠TT_{3} \ne Tt∈T∖T3t \in T \setminus T_{3}I4(t)I_{4}(t)
T3=TT_{3} = Tt∈T4t \in T_{4}II3,I4(t)II_{3}, I_{4}(t)
({1,2},{1,2})(\{1,2\},\{1,2\})T3=TT_{3} = Tt∈T4t \in T_{4}II3,I4(t)II_{3}, I_{4}(t)
T3,T4≠TT_{3},T_{4} \ne T and ∣T3∣=2|T_{3}| = 2t∈T∖T3t \in T \setminus T_{3}I4(t)I_{4}(t)

Table 4.1.

In the second type, interchange (X1,X3,Y1)(X_{1},X_{3},Y_{1}) with (X2,X4,Y2)(X_{2},X_{4},Y_{2}) if needed. In the fourth, interchange X3,X4X_{3},X_{4} if needed. A proper subset T3⊂TT_{3} \subset T used in the table has size 2, so T∖{t}=T3T \setminus\{t\} = T_{3} makes I4(t)I_{4}(t) valid. In the last two types, when T3=TT_{3} = T, template II3II_{3} covers X3YtX_{3}Y_{t} and I4(t)I_{4}(t) covers X4YtX_{4}Y_{t} at any t∈T4t \in T_{4}. The first type has T3=TT_{3} = T by the degree bound, giving either II3II_{3} or the stated exception. □\square

Lemma 4.2 Let f:2V→Rf : 2^{V} \to\mathbb{R} be submodular, let X\mathcal{X} be a minimum non-trivial 4-partition of VV, and let Y\mathcal{Y} be the unique minimum 5-partition of VV. If Y\mathcal{Y} is 5-size and X\mathcal{X} is incompatible with Y\mathcal{Y}, their configuration has the nonempty cells in Figure 4.2, up to relabeling.

Configuration of the 4- and 5-partitions

Figure 4.2. The configuration in Lemma 4.2. Rows are parts of X\mathcal{X} and columns are parts of Y\mathcal{Y}. Named cells are nonempty, and 0 denotes an empty cell. Thus X3=Z31∪Y2∪Y3X_3 = Z_{31} \cup Y_2 \cup Y_3 and X4=Z41∪Y4∪Y5X_4 = Z_{41} \cup Y_4 \cup Y_5, with Y1=X1∪X2∪Z31∪Z41Y_1 = X_1 \cup X_2 \cup Z_{31} \cup Z_{41}. This is the obstruction in [3 Section 7].

Proof: If a row XiX_i has degree 2, apply Lemma 2.2 to the vertex set consisting of XiX_i and its two neighboring columns, which induces a connected subgraph. The new 5-partition consists of the two nonempty cells of XiX_i 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 X\mathcal{X} is minimum among non-trivial 4-partitions, the new 5-partition is also minimum and X\mathcal{X} is compatible with it, contradicting the uniqueness of Y\mathcal{Y}. 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 G(M)G(M) 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 X′\mathcal{X}' and a minimum 5-partition Y′={U∗}∪LW\mathcal{Y}' = \{U^*\} \cup\mathcal{L}_W. Either UU contains two rows, so the part U∗U^* of Y′\mathcal{Y}' contains two rows of X\mathcal{X}, or UU contains one row and WW contains both leaf rows, which remain separate parts of LW\mathcal{L}_W while the row in UU lies in U∗U^*, giving X≺Y′\mathcal{X} \prec\mathcal{Y}'. Since no two leaf rows share a column, no part of Y\mathcal{Y} contains two rows of X\mathcal{X}, and X\mathcal{X} is incompatible with Y\mathcal{Y}. Thus Y′≠Y\mathcal{Y}' \ne\mathcal{Y} in both cases, contradicting the uniqueness of Y\mathcal{Y}. For the exception, with X3=Z33∪Z34∪Z35X_3 = Z_{33} \cup Z_{34} \cup Z_{35} and X4=Z41∪⋯∪Z45X_4 = Z_{41} \cup\cdots\cup Z_{45}, uncrossing X3X_3 successively with Y3Y_3 and Y5Y_5, and X4X_4 with Y4Y_4, gives

X′={Y1,Y2,X3∪Z43∪Z45,Z44},Y′={X1,X2,Z33,X4∪Z34,Z35},\mathcal{X}' = \{Y_1,Y_2,X_3 \cup Z_{43} \cup Z_{45},Z_{44}\}, \qquad\mathcal{Y}' = \{X_1,X_2,Z_{33},X_4 \cup Z_{34},Z_{35}\},

again with non-trivial X′\mathcal{X}' and X≺Y′\mathcal{X} \prec\mathcal{Y}'.

If G(M)G(M) 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 X1=YjX_1 = Y_j. For f∖X1f\setminus X_1, the partition Y∖{Yj}\mathcal{Y} \setminus\{Y_j\} 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 X1X_1 gives a non-trivial 4-partition. Thus the three remaining rows of X\mathcal{X} form a minimum 3-partition of f∖X1f\setminus X_1. Either they are non-trivial, or their two singletons together with X1X_1 already make X\mathcal{X} compatible with Y\mathcal{Y}. In the former case, [3 Theorem 4.3] implies that two of the remaining rows are noncrossing with Y∖{Yj}\mathcal{Y} \setminus\{Y_j\}, hence with Y\mathcal{Y}, contradicting incompatibility. This proves the claim.

Relabel so that the leaf rows are X1X_1 and X2X_2, both adjacent to Y1Y_1. The rows X3X_3 and X4X_4 both have degree at least 3, and Yt=Z3t∪Z4tY_t = Z_{3t} \cup Z_{4t} for every t∈F∖{1}t \in F \setminus\{1\}. For any 2-element set S⊆N(X3)S \subseteq N(X_3) such that T=N(X3)∖ST = N(X_3) \setminus S satisfies 1∉T1 \notin T and T⊆N(X4)T \subseteq N(X_4), applying Lemma 2.2 to {X3}∪{Yj:j∈S}\{X_3\} \cup\{Y_j : j \in S\} and to {X4}∪{Yt:t∈T}\{X_4\} \cup\{Y_t : t \in T\} gives

X′={X3∪⋃j∈SYj∪⋃t∈TZ4t∪{Yj:j∈F∖N(X3)},\mathcal{X}' = \{X_3 \cup\bigcup_{j \in S} Y_j \cup\bigcup_{t \in T} Z_{4t} \cup\{Y_j : j \in F \setminus N(X_3)\},
Y′={X1,X2}∪{Z3j:j∈S}∪{X4∪⋃t∈TYt},\mathcal{Y}' = \{X_1,X_2\} \cup\{Z_{3j} : j \in S\} \cup\{X_4 \cup\bigcup_{t \in T} Y_t\},

@page 8/11 starts_mid=1 ends_mid=1

Configuration of the 4- and 5-partitions

Figure 4.2 (PDF p. 8). The configuration in Lemma 4.2. Rows are parts of X\mathcal{X} and columns are parts of Y\mathcal{Y}. Named cells are nonempty, and 0 denotes an empty cell. Thus X3=Z31∪Y2∪Y3X_3 = Z_{31} \cup Y_2 \cup Y_3 and X4=Z41∪Y4∪Y5X_4 = Z_{41} \cup Y_4 \cup Y_5, with Y1=X1∪X2∪Z31∪Z41Y_1 = X_1 \cup X_2 \cup Z_{31} \cup Z_{41}. This is the obstruction in [3 Section 7].

Proof: If a row XiX_i has degree 2, apply Lemma 2.2 to the vertex set consisting of XiX_i and its two neighboring columns, which induces a connected subgraph. The new 5-partition consists of the two nonempty cells of XiX_i 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 X\mathcal{X} is minimum among non-trivial 4-partitions, the new 5-partition is also minimum and X\mathcal{X} is compatible with it, contradicting the uniqueness of Y\mathcal{Y}. 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 G(M)G(M) 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 X′\mathcal{X}' and a minimum 5-partition Y′={U∗}∪LW\mathcal{Y}' = \{U^*\} \cup\mathcal{L}_W. Either UU contains two rows, so the part U∗U^* of Y′\mathcal{Y}' contains two rows of X\mathcal{X}, or UU contains one row and WW contains both leaf rows, which remain separate parts of LW\mathcal{L}_W while the row in UU lies in U∗U^*, giving X≺Y′\mathcal{X} \prec\mathcal{Y}'. Since no two leaf rows share a column, no part of Y\mathcal{Y} contains two rows of X\mathcal{X}, and X\mathcal{X} is incompatible with Y\mathcal{Y}. Thus Y′≠Y\mathcal{Y}' \ne\mathcal{Y} in both cases, contradicting the uniqueness of Y\mathcal{Y}. For the exception, with X3=Z33∪Z34∪Z35X_3 = Z_{33} \cup Z_{34} \cup Z_{35} and X4=Z41∪⋯∪Z45X_4 = Z_{41} \cup\cdots\cup Z_{45}, uncrossing X3X_3 successively with Y3Y_3 and Y5Y_5, and X4X_4 with Y4Y_4, gives

X′={Y1,Y2,X3∪Z43∪Z45,Z44},Y′={X1,X2,Z33,X4∪Z34,Z35},\mathcal{X}' = \{Y_1,Y_2,X_3 \cup Z_{43} \cup Z_{45},Z_{44}\}, \qquad\mathcal{Y}' = \{X_1,X_2,Z_{33},X_4 \cup Z_{34},Z_{35}\},

again with non-trivial X′\mathcal{X}' and X≺Y′\mathcal{X} \prec\mathcal{Y}'.

If G(M)G(M) 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 X1=YjX_1 = Y_j. For f∖X1f\setminus X_1, the partition Y∖{Yj}\mathcal{Y} \setminus\{Y_j\} 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 X1X_1 gives a non-trivial 4-partition. Thus the three remaining rows of X\mathcal{X} form a minimum 3-partition of f∖X1f\setminus X_1. Either they are non-trivial, or their two singletons together with X1X_1 already make X\mathcal{X} compatible with Y\mathcal{Y}. In the former case, [3 Theorem 4.3] implies that two of the remaining rows are noncrossing with Y∖{Yj}\mathcal{Y} \setminus\{Y_j\}, hence with Y\mathcal{Y}, contradicting incompatibility. This proves the claim.

Relabel so that the leaf rows are X1X_1 and X2X_2, both adjacent to Y1Y_1. The rows X3X_3 and X4X_4 both have degree at least 3, and Yt=Z3t∪Z4tY_t = Z_{3t} \cup Z_{4t} for every t∈F∖{1}t \in F \setminus\{1\}. For any 2-element set S⊆N(X3)S \subseteq N(X_3) such that T=N(X3)∖ST = N(X_3) \setminus S satisfies 1∉T1 \notin T and T⊆N(X4)T \subseteq N(X_4), applying Lemma 2.2 to {X3}∪{Yj:j∈S}\{X_3\} \cup\{Y_j : j \in S\} and to {X4}∪{Yt:t∈T}\{X_4\} \cup\{Y_t : t \in T\} gives

X′={X3∪⋃j∈SYj∪⋃t∈TZ4t∪{Yj:j∈F∖N(X3)},\mathcal{X}' = \{X_3 \cup\bigcup_{j \in S} Y_j \cup\bigcup_{t \in T} Z_{4t} \cup\{Y_j : j \in F \setminus N(X_3)\},
Y′={X1,X2}∪{Z3j:j∈S}∪{X4∪⋃t∈TYt},\mathcal{Y}' = \{X_1,X_2\} \cup\{Z_{3j} : j \in S\} \cup\{X_4 \cup\bigcup_{t \in T} Y_t\},

which have four and five parts, respectively. Whenever X′\mathcal{X}' is non-trivial, Y′\mathcal{Y}' is also a minimum 5-partition and satisfies X≺Y′\mathcal{X} \prec\mathcal{Y}', contradicting the uniqueness of Y\mathcal{Y}. If 1∉N(X3)1 \notin N(X_3), choose TT to consist of one index in N(X3)∩(N(X4)∖{1})N(X_3) \cap(N(X_4) \setminus\{1\}) when ∣N(X3)∣=3|N(X_3)| = 3, or two indices in N(X4)∖{1}N(X_4) \setminus\{1\} when N(X3)=F∖{1}N(X_3) = F \setminus\{1\}. In both cases the untouched column Y1Y_1 makes X′\mathcal{X}' non-trivial. By symmetry, 1∈N(X3)∩N(X4)1 \in N(X_3) \cap N(X_4). The sets A3=N(X3)∖{1}A_3 = N(X_3) \setminus\{1\} and A4=N(X4)∖{1}A_4 = N(X_4) \setminus\{1\} each have size at least 2 and satisfy A3∪A4=F∖{1}A_3 \cup A_4 = F \setminus\{1\}. Unless ∣A3∣=∣A4∣=2|A_3| = |A_4| = 2, relabel X3,X4X_3,X_4 so that ∣A3∣≤∣A4∣|A_3| \le|A_4|, giving ∣A4∣≥3|A_4| \ge3 and ∣A3∖A4∣≤1|A_3 \setminus A_4| \le1, and choose c∈A3c \in A_3 with A3∖A4⊆{c}A_3 \setminus A_4 \subseteq\{c\}. Setting S={1,c}S = \{1,c\} gives 1∉T1 \notin T and T⊆A4T \subseteq A_4. If ∣A3∣<4|A_3| < 4, an untouched column in F∖N(X3)F \setminus N(X_3) makes X′\mathcal{X}' non-trivial. If ∣A3∣=∣A4∣=4|A_3| = |A_4| = 4, each column YtY_t with t∈F∖{1}t \in F \setminus\{1\} has size at least 5, so relabeling X3,X4X_3,X_4 gives ∣Z4t∣≥2|Z_{4t}| \ge2 for some t∈F∖{1}t \in F \setminus\{1\}, and choosing c∈F∖{1,t}c \in F \setminus\{1,t\} gives t∈Tt \in T so that X3∪Y1∪YcX_3 \cup Y_1 \cup Y_c and Z4tZ_{4t} make X′\mathcal{X}' non-trivial. Hence ∣A3∣=∣A4∣=2|A_3| = |A_4| = 2, and A3∪A4=F∖{1}A_3 \cup A_4 = F \setminus\{1\} makes A3A_3 and A4A_4 disjoint, as asserted. □

Lemma 4.3 Let f:2V→Rf : 2^V \to\mathbb{R} be submodular, let X\mathcal{X} be a minimum non-trivial 4-partition of VV, and let Y\mathcal{Y} be the unique minimum 5-partition of VV. Suppose Y\mathcal{Y} is 5-size and X\mathcal{X} is incompatible with Y\mathcal{Y}, and let Z={P,Q,R}\mathcal{Z} = \{P,Q,R\} minimize ff over FX\mathcal{F}_{\mathcal{X}} with P∪QP \cup Q in one part of X\mathcal{X}. Then PP and QQ are noncrossing with Y\mathcal{Y}.

Proof. Suppose otherwise and, by symmetry, assume that PP crosses Y\mathcal{Y}. By Lemma 4.2, X1∪X2⊆Y1X_1 \cup X_2 \subseteq Y_1, so P∪QP \cup Q is contained in X3X_3 or X4X_4. Interchanging X3X_3 and X4X_4 and the column pairs (Y2,Y3)(Y_2,Y_3) and (Y4,Y5)(Y_4,Y_5) if needed, assume P∪Q⊆X3P \cup Q \subseteq X_3, so that Y2=Z32Y_2 = Z_{32} and Y3=Z33Y_3 = Z_{33}, while Y4∪Y5⊆X4Y_4 \cup Y_5 \subseteq X_4. Let Pi=P∩Z3i=P∩YiP_i = P \cap Z_{3i} = P \cap Y_i for i=1,2,3i = 1,2,3. Since PP crosses Y\mathcal{Y}, at least two of the three sets PiP_i are nonempty.

If all three PiP_i are nonempty, Lemma 2.2 gives

f(P)+f(Y1)+f(Y2)+f(Y3)≥f(X3∪Y1)+∑i=13f(Pi),f(P)+f(Y_1)+f(Y_2)+f(Y_3) \ge f(X_3\cup Y_1)+\sum_{i=1}^{3}f(P_i),

so Z′={X3∪Y1,Y4,Y5}\mathcal{Z}' = \{X_3 \cup Y_1,Y_4,Y_5\} and Y′={P1,P2,P3,Q,R}\mathcal{Y}' = \{P_1,P_2,P_3,Q,R\} satisfy f(Z′)+f(Y′)≤f(Z)+f(Y)f(\mathcal{Z}')+f(\mathcal{Y}') \le f(\mathcal{Z})+f(\mathcal{Y}). Here Z′∈FX\mathcal{Z}' \in\mathcal{F}_{\mathcal{X}} since Y4,Y5⊆X4Y_4,Y_5 \subseteq X_4 have size at least 5, making Y′\mathcal{Y}' a minimum 5-partition with ∅⊂P1⊂Y1\varnothing\subset P_1 \subset Y_1, a contradiction.

Otherwise, exactly two of P1,P2,P3P_1,P_2,P_3 are nonempty, say PiP_i and PjP_j, with {i,j,k}={1,2,3}\{i,j,k\} = \{1,2,3\}. Consider

X′={Pi,Pj,Q,R},Y′={X1,X2,Z3i∪Z3j,Z3k,X4},Z′={X3∪Y1,Y4,Y5}.\mathcal{X}' = \{P_i,P_j,Q,R\}, \qquad\mathcal{Y}' = \{X_1,X_2,Z_{3i}\cup Z_{3j},Z_{3k},X_4\}, \qquad\mathcal{Z}' = \{X_3\cup Y_1,Y_4,Y_5\}.

The 4-partition X′\mathcal{X}' is non-trivial because Z\mathcal{Z} has at least two parts of size at least 3, and splitting PP into PiP_i and PjP_j produces a part of size at least 2 whenever ∣P∣≥3|P| \ge3. Moreover, Y′\mathcal{Y}' is a 5-partition and Z′∈FX\mathcal{Z}' \in\mathcal{F}_{\mathcal{X}}. Submodularity gives

f(X3)+f(Y1)≥f(Z3i)+f(X3∪Y1),f(X_3)+f(Y_1) \ge f(Z_{3i})+f(X_3\cup Y_1),
f(Z3i)+f(Z3j)+f(P)≥f(Pi)+f(Pj)+f(Z3i∪Z3j),f(Z_{3i})+f(Z_{3j})+f(P) \ge f(P_i)+f(P_j)+f(Z_{3i}\cup Z_{3j}),

where the second inequality applies submodularity to Z3iZ_{3i} and P=Pi∪PjP = P_i \cup P_j and then to Z3j∪PiZ_{3j} \cup P_i and Z3iZ_{3i}. Adding the remaining part values gives f(X′)+f(Y′)+f(Z′)≤f(X)+f(Y)+f(Z)f(\mathcal{X}')+f(\mathcal{Y}')+f(\mathcal{Z}') \le f(\mathcal{X})+f(\mathcal{Y})+f(\mathcal{Z}), using Y2=Z32Y_2 = Z_{32} and Y3=Z33Y_3 = Z_{33} together with f(Z3i)+f(Z3j)+f(Z3k)=f(Z31)+f(Z32)+f(Z33)f(Z_{3i})+f(Z_{3j})+f(Z_{3k}) = f(Z_{31})+f(Z_{32})+f(Z_{33}). Since the partitions X,Y,Z\mathcal{X},\mathcal{Y},\mathcal{Z} are optimal in their respective families, Y′\mathcal{Y}' is also a minimum 5-partition. But X1X_1 and X2X_2 are separate in Y′\mathcal{Y}' and together in Y\mathcal{Y}, contradicting the uniqueness of Y\mathcal{Y}. □

The Algorithm

For a submodular function gg on a current ground set WW with ∣W∣≥5|W| \ge5, let B(g)\mathcal{B}(g) be a minimum 5-partition of WW among those having a part of size at most 4. Enumerate each nonempty S⊆WS \subseteq W with ∣S∣≤min⁡(4,∣W∣−4)|S| \le\min(4,|W|-4) and combine {S}\{S\} with a minimum 4-partition of g∣Sg_{|S}. This computes B(g)\mathcal{B}(g) in polynomial time by § 2.1 (see [3 Theorem 6.1]), and for 5≤∣W∣≤245 \le|W| \le24 it returns a minimum 5-partition of gg.

Given f:2V0→Rf : 2^{V_0} \to\mathbb{R}, pass to the lexicographic pair (f,ψ)(f,\psi) from § 2.1, which we still write as ff. By § 2.1, B(g)\mathcal{B}(g) and Lemmas 2.1 and 3.1 apply directly to ff and its contractions, and every instance has a unique minimum 5-partition. Figure 5.1 gives the recursive procedure MIN5PARTITION⁡(f)\operatorname{MIN5PARTITION}(f), where VV is the ground set of the current call and every lift⁡(⋅)\operatorname{lift}(\cdot) is to VV.

Compute a minimum 5-partition

Figure 5.1. Compute a minimum 5-partition.

Whenever an iteration reaches the minimization over FX\mathcal{F}_{\mathcal{X}}, the current ground set of gg has at least 25 elements, so some part of X\mathcal{X} has at least 7 elements. Taking three of them as PP, one as QQ, and the rest of the ground set as RR shows that FX\mathcal{F}_{\mathcal{X}} is nonempty. At least one of PP and QQ has size at least 3, so contracting PP and QQ reduces the ground-set size of gg by at least 2. Moreover, the updated 4-partition X\mathcal{X} has {uP,uQ}\{u_P,u_Q\} in one part and three other nonempty parts, so the ground set of gg always has at least 5 elements.

Proof (Theorem 1.1): Run MIN5PARTITION⁡\operatorname{MIN5PARTITION} on (f,ψ)(f,\psi) (still written ff) and induct on ∣V∣|V|. For ∣V∣≤24|V| \le24, the call returns B(f)\mathcal{B}(f), which is optimal. Assume ∣V∣≥25|V| \ge25 and let Y∗Y^* be the unique minimum 5-partition of ff. Every candidate placed in C\mathcal{C} or compared with U\mathcal{U} lifts a 5-partition to VV, so f(U)≥f(Y∗)f(\mathcal{U}) \ge f(Y^*) throughout. If X≺Y∗\mathcal{X} \prec Y^*, then for some Xi∈XX_i \in\mathcal{X} the parts in X∖{Xi}\mathcal{X} \setminus\{X_i\} are noncrossing with Y∗Y^*, so Y∗Y^* lifts from a minimum 5-partition of f/(X∖{Xi})f/(\mathcal{X}\setminus\{X_i\}). That contracted ground set has size ∣Xi∣+3≥5|X_i|+3 \ge5, so ∣Xi∣≥2|X_i| \ge2 and the recursive call for XiX_i sets U=Y∗\mathcal{U}=Y^* before the loop.

Suppose X\mathcal{X} is incompatible with Y∗Y^*. At the start of each iteration, either U=Y∗\mathcal{U}=Y^*, or gg has a unique minimum 5-partition YY lifting to Y∗Y^* and X\mathcal{X} is a minimum non-trivial 4-partition of gg incompatible with YY. If U≠Y∗\mathcal{U}\ne Y^* after comparing with lift⁡(B(g))\operatorname{lift}(\mathcal{B}(g)), then YY is 5-size, gg has at least 25 elements, and X\mathcal{X} is non-trivial, so the iteration continues. By Lemmas 4.2 and 4.3, PP and QQ each lie in a cell of X\mathcal{X} and YY. Contracting PP and QQ maps YY to a 5-partition Y′Y' of g/{P,Q}g/\{P,Q\} that has the same configuration graph with the updated X\mathcal{X}, so the updated X\mathcal{X} remains incompatible with Y′Y' and its two crossing rows still have degree 3, keeping X\mathcal{X} non-trivial. Since lifting preserves values, is injective, and maps non-trivial 4-partitions to non-trivial 4-partitions, Y′Y' is the unique minimum 5-partition of g/{P,Q}g/\{P,Q\} and the updated X\mathcal{X} remains a minimum non-trivial 4-partition. Each iteration removes at least 2 elements, so the loop terminates and returns Y∗Y^*.

For the running time, let n=∣V0∣n=|V_0|. On an mm-element instance with m≥25m\ge25 and ai=∣Xi∣a_i=|X_i|, each recursive call has ai≥2a_i\ge2, size ai+3<ma_i+3<m, and positive measure (ai+3)−4=ai−1(a_i+3)-4=a_i-1. Since ∑i=1n(ai−1)=m−4\sum_{i=1}^{n}(a_i-1)=m-4 has at least two positive terms, there are O(n)O(n) invocations. Each invocation acts on a contraction of (f,ψ)(f,\psi) at at most nn elements with second coordinates of bit length polynomial in nn (in § 2.1), calls Lemma 3.1 once before the loop, and runs O(n)O(n) iterations that each compute B(g)\mathcal{B}(g) and a minimum partition in FX\mathcal{F}_{\mathcal{X}} (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. [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. [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. [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. [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. [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. [6]Queyranne, M.: Minimizing symmetric submodular functions. Mathematical Programming 82(1–2), 3–12 (1998). https://doi.org/10.1007/BF01585863

Paper details

vlnc:W_ssr49jn9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents