Submodular decompositions: a bounded-variation counterexample and an exact planar cut formula
Abstract
Bérczi, Gehér, Imolay, Lovász, and Schwarcz (SIAM J. Discrete Math. 40(2026), 308--335) asked whether every set function of bounded variation is a difference of two bounded submodular functions, and how to determine the optimum in a monotonic sum-decomposition of a planar graph cut function. In this paper, we answer both questions and obtain quantitative extensions. For the first question, we characterize the continuous profiles f:[0,1]→R for which A↦ f(m(A)) is a bounded submodular difference on an atomless probability space. More precisely, we express the minimum oscillation of the subtracted component through the positive part of the distributional second derivative. We also characterize admissible discontinuous profiles and give an exact summability criterion for countable block functions. In particular, the first question has a negative answer even for increasing functions of variation one whose scalar profiles have log-Lipschitz derivatives and belong to every C1,α, 0<α<1. Turning to graph cuts, we prove that the optimum equals the total edge weight minus the maximum fractional triangle-packing weight for every nonnegative weighting if and only if the graph is K5-free. Moreover, maximum packings parametrize the symmetrized optimal components, while on K4-free graphs we describe all optimal components and characterize uniqueness. Consequently, the formula applies to weighted planar graphs and implies edge-weight monotonicity on K5-free graphs. For rational weights, it also yields polynomial-time constructions.
Related
- Decompositions of homomorphisms of abelian p-groups with p2-bounded target
- A counterexample concerning the coefficient formula for de Branges-Rovnyak norms
- A counterexample to Yau's bounded-mean-curvature embedding question
- A BMO-type representation formula for the total variation of SBV functions in Heisenberg groups
- Stochastic Subgradient Descent at Sharply Repulsive Points: A Bounded Noise Counterexample and Gaussian Noise Avoidance
BibTeX
@misc{wang2026submodular,
title = {{Submodular decompositions: a bounded-variation counterexample and an exact planar cut formula}},
author = {Guoqing Wang and Linlin Wang and Jun Yue},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40032},
eprint = {2610.40032},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40032},
}
RIS
TY - UNPB
TI - Submodular decompositions: a bounded-variation counterexample and an exact planar cut formula
AU - Guoqing Wang
AU - Linlin Wang
AU - Jun Yue
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40032
UR - https://arxiv.org/abs/2610.40032
AB - Bérczi, Gehér, Imolay, Lovász, and Schwarcz (SIAM J. Discrete Math. 40(2026), 308--335) asked whether every set function of bounded variation is a difference of two bounded submodular functions, and how to determine the optimum in a monotonic sum-decomposition of a planar graph cut function. In this paper, we answer both questions and obtain quantitative extensions. For the first question, we characterize the continuous profiles f:[0,1]→R for which A↦ f(m(A)) is a bounded submodular difference on an atomless probability space. More precisely, we express the minimum oscillation of the subtracted component through the positive part of the distributional second derivative. We also characterize admissible discontinuous profiles and give an exact summability criterion for countable block functions. In particular, the first question has a negative answer even for increasing functions of variation one whose scalar profiles have log-Lipschitz derivatives and belong to every C^1,α, 0<α<1. Turning to graph cuts, we prove that the optimum equals the total edge weight minus the maximum fractional triangle-packing weight for every nonnegative weighting if and only if the graph is K_5-free. Moreover, maximum packings parametrize the symmetrized optimal components, while on K_4-free graphs we describe all optimal components and characterize uniqueness. Consequently, the formula applies to weighted planar graphs and implies edge-weight monotonicity on K_5-free graphs. For rational weights, it also yields polynomial-time constructions.
ER -