2024/05/09 by Susumu Kubo, Kubo, Susumu
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.2405.05544
openalex publication_date 2024/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The partition problem is a well-known NP-complete problem. We focus on its optimization version. We propose two partially ordered sets (posets) corresponding to the partition problem and develop an order-theoretic framework for solving it. The first poset is order-isomorphic to a well-known poset whose structure is related to solutions of the subset sum problem, while the second is a subposet of the first and plays a crucial role in this paper. The partial order characterizes the dominance relations between subsets that hold uniformly across all instances. We first show several properties of the two posets, such as size, height, and width (the size of the largest antichain, i.e., the largest set of pairwise incomparable elements). The two posets have the same width, which is Θ(2n / n3/2) for n congruent to 0 or 3 modulo 4; this exponential width indicates the hardness of the partition problem. We then prove that the initial candidate solutions are the elements of the second poset, whose size is 2n - 2 \binomn\lfloor n/2 \rfloor. Since a partition corresponds to two elements of the poset, the number of initial candidate partitions is half of that, i.e., 2n-1 - \binomn\lfloor n/2 \rfloor. We prove that the candidate solutions can be further reduced based on the partial order, and we establish a necessary and sufficient condition, phrased in terms of the second poset, for a subset to attain the optimal value. Building on this optimality criterion, we finally derive several polynomially solvable cases from the structure of the second poset. %considering the minimal and maximal elements of the second poset. Our approach offers a useful tool for structural analysis of the partition problem.