2025/10/07 by Mishal Assif P K, K, Mishal Assif P, Yuliy Baryshnikov +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #Algorithms and Data Compression #Constraint Satisfaction and Optimization
paper · pdf · doi:10.48550/arxiv.2510.05944
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 ≥ 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.