Abstract. In submodular [Formula: see text]-partition, the input is a submodular function [Formula: see text] (given by an evaluation oracle) along with a positive integer [Formula: see text], and the goal is to find a partition of the ground set [Formula: see text] into [Formula: see text] nonempty parts [Formula: see text] in order to minimize [Formula: see text]. Narayanan, Roy, and Patkar [ J. Algorithms, 21 (1996), pp. 306–330] designed an algorithm for submodular [Formula: see text]-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is 2 for the special case of graph cut functions (which was subsequently rediscovered by Ravi and Sinha [ European J. Oper. Res., 186 (2008), pp. 77–90]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions—namely monotone, symmetric, and posimodular—and show the following results: (1) The approximation factor of their algorithm for monotone submodular [Formula: see text]-partition is [Formula: see text]. This result improves on the 2-factor that was known to be achievable for monotone submodular [Formula: see text]-partition via other algorithms. Moreover, our upper bound of [Formula: see text] matches the recently shown lower bound under polynomial number of function evaluation queries [R. Santiago, Proceedings of the International Workshop on Combinatorial Algorithms, IWOCA, 2021, pp. 516–530]. Our upper bound of [Formula: see text] is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular [Formula: see text]-partition. (2) The approximation factor of their algorithm for symmetric submodular [Formula: see text]-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. (3) The approximation factor of their algorithm for posimodular submodular [Formula: see text]-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is [Formula: see text].

In submodular k-partition, the input is a submodular function f:2^V → ℝ_{≥ 0} (given by an evaluation oracle) along with a positive integer k and the goal is to find a partition of the ground set V into k non-empty parts V_1, V_2, …, V_k in order to minimize ∑_{i=1}^k f(V_i). Narayanan, Roy, and Patkar [Narayanan et al., 1996] designed an algorithm for submodular k-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is 2 for the special case of graph cut functions (which was subsequently rediscovered by Ravi and Sinha [R. Ravi and A. Sinha, 2008]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions - namely monotone, symmetric, and posimodular and show the following results: 1) The approximation factor of their algorithm for monotone submodular k-partition is 4/3. This result improves on the 2-factor that was known to be achievable for monotone submodular k-partition via other algorithms. Moreover, our upper bound of 4/3 matches the recently shown lower bound under polynomial number of function evaluation queries [Santiago, 2021]. Our upper bound of 4/3 is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular k-partition. 2) The approximation factor of their algorithm for symmetric submodular k-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. 3) The approximation factor of their algorithm for posimodular submodular k-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is Ω(n/k).

We consider the problem of enumerating optimal solutions for two hypergraph $k$-partitioning problems -- namely, Hypergraph-$k$-Cut and Minmax-Hypergraph-$k$-Partition. The input in hypergraph $k$-partitioning problems is a hypergraph $G=(V, E)$ with positive hyperedge costs along with a fixed positive integer $k$. The goal is to find a partition of $V$ into $k$ non-empty parts $(V_1, V_2, \ldots, V_k)$ -- known as a $k$-partition -- so as to minimize an objective of interest. 1. If the objective of interest is the maximum cut value of the parts, then the problem is known as Minmax-Hypergraph-$k$-Partition. A subset of hyperedges is a minmax-$k$-cut-set if it is the subset of hyperedges crossing an optimum $k$-partition for Minmax-Hypergraph-$k$-Partition. 2. If the objective of interest is the total cost of hyperedges crossing the $k$-partition, then the problem is known as Hypergraph-$k$-Cut. A subset of hyperedges is a min-$k$-cut-set if it is the subset of hyperedges crossing an optimum $k$-partition for Hypergraph-$k$-Cut. We give the first polynomial bound on the number of minmax-$k$-cut-sets and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed $k$. Our technique is strong enough to also enable an $n^{O(k)}p$-time deterministic algorithm to enumerate all min-$k$-cut-sets in hypergraphs, thus improving on the previously known $n^{O(k^2)}p$-time deterministic algorithm, where $n$ is the number of vertices and $p$ is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for Hypergraph-$k$-Cut and Minmax-Hypergraph-$k$-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).

We consider the problem of deterministically enumerating all minimum k-cut-sets in a given hypergraph for any fixed k. The input here is a hypergraph G = (V, E) with non-negative hyperedge costs. A subset F ⊆ E of hyperedges is a k-cut-set if the number of connected components in G–F is at least k and it is a minimum k-cut-set if it has the least cost among all k-cut-sets. For fixed k, we call the problem of finding a minimum k-cut-set as Hypergraph-k-Cut and the problem of enumerating all minimum k-cut-sets as Enum-Hypergraph-k-Cut. The special cases of Hypergraph-k-Cut and Enum-Hypergraph-k-Cut restricted to graph inputs are well-known to be solvable in (randomized as well as deterministic) polynomial time [17,25,28,39]. In contrast, it is only recently that polynomial-time algorithms for Hypergraph-k-Cut were developed [2,3,12]. The randomized polynomial-time algorithm for Hypergraph-k-Cut that was designed in 2018 [3] showed that the number of minimum k-cut-sets in a hypergraph is O(n2k–2), where n is the number of vertices in the input hypergraph, and that they can all be enumerated in randomized polynomial time, thus resolving Enum-Hypergraph-k-Cut in randomized polynomial time. A deterministic polynomial-time algorithm for Hypergraph-k-Cut was subsequently designed in 2020 [2], but it is not guaranteed to enumerate all minimum k-cut-sets. In this work, we give the first deterministic polynomial-time algorithm to solve Enum-Hypergraph-k-Cut (this is non-trivial even for k = 2). Our algorithm is based on new structural results that allow for efficient recovery of all minimum k-cut-sets by solving minimum (S, T)-terminal cuts. Our techniques give new structural insights even for enumerating all minimum cut-sets (i.e., minimum 2-cut-sets) in a given hypergraph.

We introduce and study 𝓁_p-norm-multiway-cut: the input here is an undirected graph with non-negative edge weights along with k terminals and the goal is to find a partition of the vertex set into k parts each containing exactly one terminal so as to minimize the 𝓁_p-norm of the cut values of the parts. This is a unified generalization of min-sum multiway cut (when p = 1) and min-max multiway cut (when p = ∞), both of which are well-studied classic problems in the graph partitioning literature. We show that 𝓁_p-norm-multiway-cut is NP-hard for constant number of terminals and is NP-hard in planar graphs. On the algorithmic side, we design an O(log² n)-approximation for all p ≥ 1. We also show an integrality gap of Ω(k^{1-1/p}) for a natural convex program and an O(k^{1-1/p-ε})-inapproximability for any constant ε > 0 assuming the small set expansion hypothesis.