Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914167161618432 |
|---|---|
| author | Tate, Elise Grochow, Joshua A. |
| author_facet | Tate, Elise Grochow, Joshua A. |
| contents | Graphs are a powerful tool for analyzing large data sets, but many real-world phenomena involve interactions that go beyond the simple pairwise relationships captured by a graph. In this paper we introduce and study a simple combinatorial model to capture higher order dependencies from an algorithms and computational complexity perspective. Specifically, we introduce the String Set Reconstruction problem, which asks when a set of strings can be reconstructed from seeing only the k-way projections of strings in the set. This problem is distinguished from genetic reconstruction problems in that we allow projections from any k indices and we maintain knowledge of those indices, but not which k-mer came from which string. We give several results on the complexity of this problem, including hardness results, inapproximability, and parametrized complexity.
Our main result is the introduction of a new algorithm for this problem using a modified version of overlap graphs from genetic reconstruction algorithms. A key difference we must overcome is that in our setting the k-mers need not be contiguous, unlike the setting of genetic reconstruction. We exhibit our algorithm's efficiency in a variety of experiments, and give high-level explanations for how its complexity is observed to scale with various parameters. We back up these explanation with analytic approximations. We also consider the related problems of: whether a single string can be reconstructed from the k-way projections of a given set of strings, and finding the largest k at which we get no information about the original data set from its k-way projections (i.e., the largest $k$ for which it is "k-wise independent"). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_17707 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity Tate, Elise Grochow, Joshua A. Data Structures and Algorithms Computational Complexity Graphs are a powerful tool for analyzing large data sets, but many real-world phenomena involve interactions that go beyond the simple pairwise relationships captured by a graph. In this paper we introduce and study a simple combinatorial model to capture higher order dependencies from an algorithms and computational complexity perspective. Specifically, we introduce the String Set Reconstruction problem, which asks when a set of strings can be reconstructed from seeing only the k-way projections of strings in the set. This problem is distinguished from genetic reconstruction problems in that we allow projections from any k indices and we maintain knowledge of those indices, but not which k-mer came from which string. We give several results on the complexity of this problem, including hardness results, inapproximability, and parametrized complexity. Our main result is the introduction of a new algorithm for this problem using a modified version of overlap graphs from genetic reconstruction algorithms. A key difference we must overcome is that in our setting the k-mers need not be contiguous, unlike the setting of genetic reconstruction. We exhibit our algorithm's efficiency in a variety of experiments, and give high-level explanations for how its complexity is observed to scale with various parameters. We back up these explanation with analytic approximations. We also consider the related problems of: whether a single string can be reconstructed from the k-way projections of a given set of strings, and finding the largest k at which we get no information about the original data set from its k-way projections (i.e., the largest $k$ for which it is "k-wise independent"). |
| title | Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2511.17707 |