{"ID":2859359,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.05944","arxiv_id":"2510.05944","title":"Minimal Unimodal Decomposition is NP-Hard on Graphs","abstract":"A function on a topological space is called unimodal if all of its super-level sets are contractible. A minimal unimodal decomposition of a function $f$ is the smallest number of unimodal functions that sum up to $f$. The problem of decomposing a given density function into its minimal unimodal components is fundamental in topological statistics. We show that finding a minimal unimodal decomposition of an edge-linear function on a graph is NP-hard. Given any $k \\geq 2$, we establish the NP-hardness of finding a unimodal decomposition consisting of $k$ unimodal functions. We also extend the NP-hardness result to related variants of the problem, including restriction to planar graphs, inapproximability results, and generalizations to higher dimensions.","short_abstract":"A function on a topological space is called unimodal if all of its super-level sets are contractible. A minimal unimodal decomposition of a function $f$ is the smallest number of unimodal functions that sum up to $f$. The problem of decomposing a given density function into its minimal unimodal components is fundamenta...","url_abs":"https://arxiv.org/abs/2510.05944","url_pdf":"https://arxiv.org/pdf/2510.05944v1","authors":"[\"Mishal Assif P K\",\"Yuliy Baryshnikov\"]","published":"2025-10-07T13:53:24Z","proceeding":"math.AT","tasks":"[\"math.AT\",\"cs.CG\",\"math.ST\"]","methods":"[]","has_code":false}