On the Complexity of the Ordered Covering Problem in Distance Geometry
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911299144777728 |
|---|---|
| author | Souza, Michael Araújo, Júlio Costa, John Kesley Lavor, Carlile |
| author_facet | Souza, Michael Araújo, Júlio Costa, John Kesley Lavor, Carlile |
| contents | The Ordered Covering Problem (OCP) arises in the context of the Discretizable Molecular Distance Geometry Problem (DMDGP), where the ordering of pruning edges significantly impacts the performance of the SBBU algorithm for protein structure determination. In recent work, Souza et al. (2023) formalized OCP as a hypergraph covering problem with ordered, exponential costs, and proposed a greedy heuristic that outperforms the original SBBU ordering by orders of magnitude. However, the computational complexity of finding optimal solutions remained open. In this paper, we prove that OCP is NP-complete through a polynomial-time reduction from the strongly NP-complete 3-Partition problem. Our reduction constructs a tight budget that forces optimal solutions to correspond exactly to valid 3-partitions. This result establishes a computational barrier for optimal edge ordering and provides theoretical justification for the heuristic approaches currently used in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_03124 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Complexity of the Ordered Covering Problem in Distance Geometry Souza, Michael Araújo, Júlio Costa, John Kesley Lavor, Carlile Data Structures and Algorithms Computational Geometry The Ordered Covering Problem (OCP) arises in the context of the Discretizable Molecular Distance Geometry Problem (DMDGP), where the ordering of pruning edges significantly impacts the performance of the SBBU algorithm for protein structure determination. In recent work, Souza et al. (2023) formalized OCP as a hypergraph covering problem with ordered, exponential costs, and proposed a greedy heuristic that outperforms the original SBBU ordering by orders of magnitude. However, the computational complexity of finding optimal solutions remained open. In this paper, we prove that OCP is NP-complete through a polynomial-time reduction from the strongly NP-complete 3-Partition problem. Our reduction constructs a tight budget that forces optimal solutions to correspond exactly to valid 3-partitions. This result establishes a computational barrier for optimal edge ordering and provides theoretical justification for the heuristic approaches currently used in practice. |
| title | On the Complexity of the Ordered Covering Problem in Distance Geometry |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2512.03124 |