CS Paper Radar

A Polynomial Time Algorithm for Finding a Minimum 5-Partition of a Submodular Function

Yuhao Liu, Ke Shi, Chao Xu

cs.DS math.CO ·submitted 2026-11-16 14:42 UTC · v1

Abstract

Given a real-valued submodular function on a finite ground set, the minimum $k$-partition problem asks for a partition into $k$ nonempty parts minimizing the sum of their function values. We give a polynomial-time algorithm for $k=5$. The idea follows directly from the previous $k=4$ result, where there is precisely one obstruction for generalizing it to $k=5$. We show the special case can be handled by reasoning about a restricted family of $3$-partitions.

Comment
11 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint

cs.DS ·2026-10-05 ·Moran Feldman, Alan Kuhnle
similarity 0.60
Abstract · 13 pages. This version adds a remark about the relationship between this work and the results of arXiv:2610.00545

Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.401$-approximation~\cite{buchbinder2024constrained}, and the state-of-the-art hardness result shows that no polynomial time algorithm can obtain better than $0.478$-approximation for this problem~\cite{oveisgharan2011submodular}. In this work, we present the first improvement in $15$ years for the hardness result, showing that no polynomial time algorithm in the value-oracle model can obtain better than $8/17 \approx 0.471$-approximation, even for the special case of a cardinality or (simplified) partition matroid constraint.

0.40

All minimum cuts of symmetric submodular functions

cs.DS math.COmath.OC ·2026-11-05 ·Chao Xu
hot direction similarity 0.59
Abstract

We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time. The decomposition represents all minimum cuts in linear space. For the pair $s,t$ produced by Queyranne's algorithm, we construct in $O(n^2)$ time a digraph representing exactly the minimum $st$-cuts of the function. Using this construction in Chekuri and Xu's decomposition algorithm gives the cubic bound.

0.26

Multiway Partition is FPT for Connectivity Functions

cs.DM math.CO ·2026-08-11 ·Tony Huynh, Eun Jung Kim, Sang-il Oum, Roohani Sharma, Marek Sokołowski
theory similarity 0.59
Abstract · New title and strengthened main theorem that only needs posimodularity. Application to Hypergraph Multiway Partition is also added. 9 Pages,…

Let $E$ be a set of $n$ elements, $f\colon2^E\to\mathbb Z_{\ge0}$ be submodular, $t_1,\ldots,t_r\in E$ be distinct, and $k\in\mathbb N$. The Submodular Multiway Partition problem asks whether $E$ has a partition $(P_1,\ldots,P_r)$ with $t_i\in P_i$ for all $i$ and $\sum_i f(P_i)\le k$. We prove that this problem can be solved in $r^{O(k)}n^{O(1)}$ time whenever $f$ is posimodular. This covers monotone submodular functions, matroid rank functions, and nonnegative combinations of monotone and symmetric submodular functions. When $f$ is a connectivity function, we remove the dependence on the number of terminals and obtain a $k^{O(k)}n^{O(1)}$-time algorithm. The proof is entirely elementary, and is arguably the simplest proof that Edge Multiway Cut is fixed-parameter tractable. As a new consequence, our main result immediately implies that Hypergraph Multiway Partition is fixed-parameter tractable.

0.10

Symmetric Submodular Minimization from Comparisons

cs.DS ·2026-10-07 ·James Fox, David P. Woodruff
theory similarity 0.58
Abstract

Given value-oracle access to a symmetric submodular function $f:2^V\to\mathbb{R}$ with $|V|=n$, a nontrivial minimizer can be found using $O(n^3)$ value queries. We study the weaker comparison model, in which a query on $S,T\subseteq V$ reveals only whether $f(S)$ is smaller than, equal to, or larger than $f(T)$. We give a deterministic polynomial-time algorithm that finds a nontrivial minimizer of any symmetric submodular function using $O(n^3)$ comparisons, matching the best-known deterministic value-oracle bound despite not knowing the function values. More generally, the same $O(n^3)$-comparison bound holds for minimization over the nonempty members of any downward-closed family. Our algorithm combines the minimum-capacity ordering recently introduced by Iwata and Konno with the contraction framework of Goemans and Soto. Applying this result to weighted graph cut functions resolves the main open question of Cohen-Addad et al., who gave an $\widetilde{O}(n^3)$-comparison algorithm that runs in exponential time and asked whether a weighted minimum cut can be found in polynomial time using comparisons. For graphs with $m$ edges of integer weight at most $B$, we also give a deterministic polynomial-time algorithm that finds a minimum cut using \[ \widetilde{O}\!\left(n^2+\min\!\left\{mB,\,nB^2\right\}\right) \] comparisons, improving on the $O(n^3)$ bound when $B$ is small. Finally, we show that every randomized algorithm that outputs a minimum cut with probability at least $2/3$ makes $Ω(n \log n)$ expected comparisons in the worst case. Under the stronger assumption that all edge weights are polynomially bounded integers, we obtain an $Ω(n \log \log n)$ expected comparison lower bound. These bounds contrast with the value-oracle model, where no $ω(n)$ lower bound is known even for deterministic algorithms.

0.33

A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization

cs.DS ·2026-10-18 ·Alina Ene, Huy L. Nguyen
similarity 0.57
Abstract

We give a strongly polynomial time algorithm for submodular function minimization with overall running time $\widetilde{O}(n^{2}\mathsf{EO}+n^{3})$ time, where $\mathsf{EO}$ is the running time of a single evaluation of the function. Our algorithm improves upon the previously fastest strongly polynomial algorithms of Lee et al. (FOCS 2015), Dadush et al. (SODA 2018), and Jiang et al. (SODA 2024) that run in time $\widetilde{O}(n^{3}\mathsf{EO}+n^{4})$. Similarly to prior works, our work combines a cutting plane algorithm with the combinatorial arc-finding framework of Fleischer et al. (JACM 2001). We achieve our faster running time by developing an algorithm that runs the cutting plane method end to end, without restarting after discovering arcs and contracting strongly connected components.

0.24

Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid

cs.DS ·2026-10-06 ·Adrian Calinescu, Gruia Calinescu
published similarity 0.57
Abstract

Let f:2^N --> \cZ^+ be a polymatroid (an integer-valued non-decreasing submodular set function with f(emptyset) = 0). A k-polymatroid satisfies that f(e) <= k for all e in N. We call a subset S of N independent if f(S) equals the sum of f(e) over the elements e of S and f(e) > 0 for all e in S. Finding a maximum-size independent set in a 2-polymatroid has been studied and polynomial-time algorithms are known for linear polymatroids. For k >= 3, the problem is NP-hard, and an approximation algorithm with ratio approaching 2/k is known and is obtained by swapping as long as possible a "large" subset from the current solution by a set with one more element. Here we give a simple analysis of the more particular two-for-one repeated swapping heuristic, obtaining a (weaker) 2/(k+1)-approximation.

0.24

k-Submodular Cover Problem with a Matroid Constraint

cs.GT ·2026-10-19 ·Xinru Li, Donglei Du, Qian Liu, Yang Zhou, Min Li
similarity 0.57
Abstract

We investigate k-submodular cover problem with a matroid constraint on an n-element ground set V , which seeks k disjoint subsets of V with minimal cost, where their union is an independent set for some matroid defined on V and the k-submodular utility function surpasses a specified threshold. This problem generalizes the k-submodular cover problem and has a wide range of applications in artificial intelligence and combinatorial optimization. In this paper, we propose a matroid extended greedy algorithm for this problem, analyze its bi-criteria approximation ratio, and further derive an improved approximation ratio under the special case of unit costs.

0.12

3SUM Is Really Hard: A Real-to-Integer Reduction

cs.DS ·2026-10-07 ·Nick Fischer, Adam Polak, Jonas Schmidt
top venuetheory similarity 0.56
Abstract · To appear in FOCS 2026

We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. This answers an open problem posed by Chan, Vassilevska Williams, and Xu [STOC 2022], and constitutes the first such tight real-to-integer self-reduction in fine-grained complexity. Our proof relies on a surprising combination of the Frank--Tardos theorem from optimization with Freiman-type theorems from additive combinatorics.

0.71