pith. sign in

arxiv: 2606.08412 · v1 · pith:WLAVDIANnew · submitted 2026-06-07 · 💻 cs.DS · cs.CC

Complexity and Algorithms for Unary Translocation Distance

Maria Constantin , Adrian Micl\u{a}u\c{s} , Alexandru Popa , Andrei Popa This is my paper

Pith reviewed 2026-06-27 18:10 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords unary translocation distanceNP-hardnessapproximation algorithmsparameterized algorithmsinteger linear programmingset expansion
0
0 comments X

The pith

Computing the unary translocation distance is strongly NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that finding the fewest unary translocations to turn set A into a superset of target set B is strongly NP-hard. This resolves an open question on whether the problem admits an efficient algorithm in the general case. The authors complement the hardness result with a pseudo-polynomial exact algorithm when the target set has fixed size, a 2-approximation, an additive approximation that also gives a 3-approximation, and several parameterized algorithms plus an integer linear programming model. These outcomes matter because the operation generates new numbers while preserving pairwise sums, so the distance measures the cost of expanding a number set under this additive constraint.

Core claim

The authors prove that computing the unary translocation distance is strongly NP-hard. They also present an exact pseudo-polynomial algorithm for every fixed constant value of the target set size, a 2-approximation algorithm, an additive approximation of |B| minus 1 that additionally yields a 3-approximation, parameterized algorithms by maximum value combined with distance or target size, and an integer linear programming formulation whose LP relaxation has integrality gap at least 4/3.

What carries the argument

Unary translocation: the operation that adds a new pair of nonnegative integers u and v to the current set whenever u plus v equals the sum of some existing pair.

If this is right

  • No polynomial-time algorithm exists for arbitrary input and target sets unless P equals NP.
  • The distance can be computed exactly in pseudo-polynomial time whenever the target set has constant size.
  • Solutions guaranteed to be within a factor of 2 or 3 of the optimum can be produced in polynomial time.
  • The problem admits an integer linear programming model whose relaxation gap is at least 4/3.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique may establish hardness for closely related sum-preserving operations on sets.
  • The 2-approximation could serve as a fast practical solver even when the target set grows moderately.
  • Parameterized algorithms by maximum element value suggest tractability for instances drawn from bounded integer ranges.

Load-bearing premise

The polynomial-time reduction used to establish strong NP-hardness correctly encodes the unary translocation operation and the superset requirement without hidden restrictions on the input sets that would invalidate the hardness for the general case.

What would settle it

A polynomial-time algorithm that computes the unary translocation distance for arbitrary input and target sets, or an explicit instance where the reduction fails to preserve the exact distance value.

read the original abstract

Given a finite set of integers $A$, a \emph{unary translocation} produces a new set $A' = A \cup \{u,v\}$, where $u$ and $v$ are nonnegative integers satisfying $x+y=u+v$ for some $x,y\in A$. For an input set $A$ and a target set $B$, the \emph{unary translocation distance} is the minimum number of unary translocations required to obtain a superset containing $B$. In this paper, we study this problem from both theoretical and computational perspectives. We prove that computing the unary translocation distance is strongly NP-hard, thereby answering an open question raised by \citet{ConstantinMiclausPopa2026UnaryTranslocation}. On the positive side, we give an exact pseudo-polynomial algorithm for every fixed constant value of $|B|$, extending our previous results for $|B|\leq 2$. For arbitrary target sets, we present a $2$-approximation algorithm, an additive $(|B|-1)$-approximation algorithm, and show that the additive algorithm also yields a $3$-approximation. We also propose parameterized algorithms, including algorithms parameterized by the maximum value in the input set together with the optimum distance, and by the maximum value in the target set together with $|B|$. In addition, we propose an integer linear programming formulation that gives an exact mathematical model for the problem, analyze its size, and show that the LP relaxation has integrality gap at least $\frac{4}{3}$. Finally, we report computational experiments comparing the $2$-approximation algorithm, beam search, and simulated annealing. The results show that the approximation algorithm is highly effective in practice and often outperforms the heuristic baselines.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The manuscript proves that computing the unary translocation distance is strongly NP-hard (answering an open question), gives a pseudo-polynomial exact algorithm for every fixed constant |B|, presents a 2-approximation, an additive (|B|-1)-approximation (also yielding a 3-approximation), parameterized algorithms (by max input value + optimum, and by max target value + |B|), an ILP formulation whose LP relaxation has integrality gap at least 4/3, and reports experiments comparing the 2-approximation against beam search and simulated annealing.

Significance. The strong NP-hardness result resolves a stated open question and is obtained via reduction from a known NP-hard problem. The pseudo-polynomial and parameterized algorithms, together with the approximation guarantees and ILP model, supply both theoretical and practical tools; the experiments indicate that the 2-approximation performs well in practice relative to the tested heuristics.

minor comments (4)
  1. [theoretical results] § on theoretical results: the reduction establishing strong NP-hardness should explicitly verify that the constructed instances satisfy the superset requirement and unary translocation operation without additional restrictions that would weaken the result for general inputs.
  2. [approximation algorithms] The statement that the additive (|B|-1)-approximation also yields a 3-approximation requires a short proof or reference to the relevant inequality relating the two ratios.
  3. [ILP formulation] The ILP formulation section should state the number of variables and constraints explicitly as a function of the input size parameters (e.g., max value, |A|, |B|).
  4. [computational experiments] In the experimental section, report the precise parameter settings used for beam search and simulated annealing, and include instance-generation details (distribution of set sizes and values) to allow reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, accurate summary of our contributions, and recommendation of minor revision. The report correctly notes that our strong NP-hardness result resolves the open question from Constantin et al., and that we provide pseudo-polynomial, approximation, parameterized, and ILP results along with experiments.

Circularity Check

0 steps flagged

Minor self-citation for open question only; hardness via external reduction

full rationale

The central result is a strong NP-hardness proof obtained by polynomial-time reduction from a known NP-hard problem. The sole self-citation (Constantin et al. 2026) is used only to credit the source of the open question being answered; it does not supply any part of the reduction, the problem definition used in the reduction, or any load-bearing lemma. No fitted parameters, self-definitional steps, or ansatz smuggling appear in the provided text. The derivation chain therefore remains independent of the authors' prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definition of strong NP-hardness and the problem definition introduced in the authors' earlier paper; no free parameters or invented entities are introduced.

axioms (2)
  • standard math Standard definition of strong NP-hardness via polynomial-time many-one reduction from a known strongly NP-hard problem.
    Invoked for the main hardness theorem stated in the abstract.
  • domain assumption The unary translocation operation and superset requirement are exactly as defined in the problem statement.
    Basis for all algorithmic results and the open-question reference.

pith-pipeline@v0.9.1-grok · 5857 in / 1430 out tokens · 31686 ms · 2026-06-27T18:10:25.325971+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

82 extracted references · 2 canonical work pages

  1. [1]

    and Khazan, R

    Cohn, M. and Khazan, R. , booktitle=. Parsing with suffix and prefix dictionaries , year=

  2. [2]

    Scott , title =

    Piotr Berman and Marek Karpinski and Alex D. Scott , title =. Electron. Colloquium Comput. Complex. , volume =. 2003 , eprinttype =. TR03-049 , timestamp =

    2003

  3. [3]

    Tovey , abstract =

    Craig A. Tovey , abstract =. A simplified NP-complete satisfiability problem , journal =. 1984 , issn =

    1984

  4. [4]

    and Kowalik, Lukasz and Lokshtanov, Daniel and Marx, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket , title =

    Cygan, Marek and Fomin, Fedor V. and Kowalik, Lukasz and Lokshtanov, Daniel and Marx, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket , title =. 2015 , isbn =

    2015

  5. [5]

    Genetics , volume=

    Inversions in the chromosomes of Drosophila pseudoobscura , author=. Genetics , volume=. 1938 , publisher=

    1938

  6. [6]

    Proceedings of the National Academy of Sciences , volume=

    Inversions in the third chromosome of wild races of Drosophila pseudoobscura, and their use in the study of the history of the species , author=. Proceedings of the National Academy of Sciences , volume=. 1936 , publisher=

    1936

  7. [7]

    2009 , publisher=

    Combinatorics of genome rearrangements , author=. 2009 , publisher=

    2009

  8. [8]

    Journal of Theoretical Biology , volume=

    The chromosome inversion problem , author=. Journal of Theoretical Biology , volume=. 1982 , publisher=

    1982

  9. [9]

    Bioinformatics and Phylogenetics , pages=

    Genome rearrangement problems with single and multiple gene copies: a review , author=. Bioinformatics and Phylogenetics , pages=. 2019 , publisher=

    2019

  10. [10]

    A New Uniform Translocation Distance , booktitle =

    Carlos Mart. A New Uniform Translocation Distance , booktitle =

  11. [11]

    Symposium on discrete algorithms , volume=

    Of mice and men: Algorithms for evolutionary distances between genomes with translocation , author=. Symposium on discrete algorithms , volume=

  12. [12]

    Discrete applied mathematics , volume=

    Polynomial-time algorithm for computing translocation distance between genomes , author=. Discrete applied mathematics , volume=. 1996 , publisher=

    1996

  13. [13]

    Journal of Computer and System Sciences , volume =

    Lusheng Wang and Daming Zhu and Xiaowen Liu and Shaohan Ma , title =. Journal of Computer and System Sciences , volume =

  14. [14]

    Pevzner , title =

    Sridhar Hannenhalli and Pavel A. Pevzner , title =. J

  15. [15]

    da Silveira and Jos

    Lucas A. da Silveira and Jos. Computing translocation distance by a genetic algorithm , booktitle =

  16. [16]

    Procedia Computer Science , volume=

    Some remarks on the translocation distance , author=. Procedia Computer Science , volume=. 2019 , publisher=

    2019

  17. [17]

    Annual Symposium on Combinatorial Pattern Matching , pages=

    Edit distance for genome comparison based on non-local operations , author=. Annual Symposium on Combinatorial Pattern Matching , pages=. 1992 , organization=

    1992

  18. [18]

    2011 , publisher=

    Essential Genetics: A Genomics Perspective , author=. 2011 , publisher=

    2011

  19. [19]

    Algorithmic approaches for genome rearrangement: a review , year=

    Zimao Li and Lusheng Wang and Kaizhong Zhang , journal=. Algorithmic approaches for genome rearrangement: a review , year=

  20. [20]

    Genetics , volume=

    The homologies of the chromosome elements in the genus Drosophila , author=. Genetics , volume=. 1941 , publisher=

    1941

  21. [21]

    Annual Symposium on Combinatorial Pattern Matching , year=

    Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes , author=. Annual Symposium on Combinatorial Pattern Matching , year=

  22. [22]

    Algorithmica , volume=

    Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement , author=. Algorithmica , volume=. 1995 , publisher=

    1995

  23. [23]

    Annual Symposium on Combinatorial Pattern Matching , pages=

    Efficient bounds for oriented chromosome inversion distance , author=. Annual Symposium on Combinatorial Pattern Matching , pages=. 1994 , organization=

    1994

  24. [24]

    , author=

    Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome. , author=. Proceedings of the National Academy of Sciences , volume=. 1992 , publisher=

    1992

  25. [25]

    Annual Symposium on Combinatorial Pattern Matching , pages=

    A linear-time algorithm for computing translocation distance between signed genomes , author=. Annual Symposium on Combinatorial Pattern Matching , pages=. 2004 , organization=

    2004

  26. [26]

    Journal of Computational Biology , volume=

    On sorting by translocations , author=. Journal of Computational Biology , volume=. 2006 , publisher=

    2006

  27. [27]

    On the complexity of unsigned translocation distance , journal =

    Daming Zhu and Lusheng Wang , keywords =. On the complexity of unsigned translocation distance , journal =. 2006 , issn =

    2006

  28. [28]

    IEEE/ACM Transactions on Computational Biology and Bioinformatics , volume=

    A (1.5+ )-approximation algorithm for unsigned translocation distance , author=. IEEE/ACM Transactions on Computational Biology and Bioinformatics , volume=. 2008 , publisher=

    2008

  29. [29]

    Journal of Computer and System Sciences , volume=

    A 1.75-approximation algorithm for unsigned translocation distance , author=. Journal of Computer and System Sciences , volume=. 2007 , publisher=

    2007

  30. [30]

    International Workshop on Frontiers in Algorithmics , pages=

    A (1.408+ )-approximation algorithm for sorting unsigned genomes by reciprocal translocations , author=. International Workshop on Frontiers in Algorithmics , pages=. 2014 , organization=

    2014

  31. [31]

    Journal of Computer and System Sciences , volume=

    A 1.375-approximation algorithm for unsigned translocation sorting , author=. Journal of Computer and System Sciences , volume=. 2020 , publisher=

    2020

  32. [32]

    Bioinformatics , volume=

    Efficient sorting of genomic permutations by translocation, inversion and block interchange , author=. Bioinformatics , volume=. 2005 , publisher=

    2005

  33. [33]

    Proceedings of IEEE 36th Annual Foundations of Computer Science , pages=

    Transforming men into mice (polynomial algorithm for genomic distance problem) , author=. Proceedings of IEEE 36th Annual Foundations of Computer Science , pages=. 1995 , organization=

    1995

  34. [34]

    Constantin, Maria and Popa, Alexandru , title =

  35. [35]

    and Corasick, Margaret J

    Aho, Alfred V. and Corasick, Margaret J. , title =. Communications of the ACM , month =. 1975 , issue_date =

    1975

  36. [36]

    Papers Presented at the the March 3-5, 1959, Western Joint Computer Conference , pages =

    De La Briandais, Rene , title =. Papers Presented at the the March 3-5, 1959, Western Joint Computer Conference , pages =. 1959 , isbn =. doi:10.1145/1457838.1457895 , abstract =

    work page doi:10.1145/1457838.1457895 1959

  37. [37]

    , title =

    Farach, M. , title =. Proceedings of the 38th Annual Symposium on Foundations of Computer Science , pages =. 1997 , isbn =

    1997

  38. [38]

    Theoretical Computer Science , volume=

    Exact and approximation algorithms for the contiguous translocation distance problem , author=. Theoretical Computer Science , volume=. 2025 , publisher=

    2025

  39. [39]

    ACM Computing Surveys , volume=

    Rearrangement distance problems: an updated survey , author=. ACM Computing Surveys , volume=. 2024 , publisher=

    2024

  40. [40]

    European Symposium on Algorithms (ESA) , series =

    Berman, Piotr and Hannenhalli, Sridhar and Karpinski, Marek , title =. European Symposium on Algorithms (ESA) , series =. 2002 , publisher =

    2002

  41. [41]

    International Computing and Combinatorics Conference , pages=

    A Randomized FPT Approximation Algorithm for Sorting Unsigned Genomes by Translocations: Breaking the 1.375 Approximation Barrier , author=. International Computing and Combinatorics Conference , pages=. 2025 , organization=

    2025

  42. [42]

    Computing and Combinatorics (COCOON 2025) , series =

    Lai, Wenfeng and Jiang, Haitao and Zhu, Daming and Zhu, Binhai , title =. Computing and Combinatorics (COCOON 2025) , series =

    2025

  43. [43]

    IEEE/ACM Transactions on Computational Biology and Bioinformatics , volume =

    Li, Tiantian and Jiang, Haitao and Zhu, Binhai and Wang, Lusheng and Zhu, Daming , title =. IEEE/ACM Transactions on Computational Biology and Bioinformatics , volume =

  44. [44]

    WABI 2006 , series =

    Bergeron, Anne and Mixtacki, Julia and Stoye, Jens , title =. WABI 2006 , series =. 2006 , publisher =

    2006

  45. [45]

    Theoretical Computer Science , volume =

    Bergeron, Anne and Mixtacki, Julia and Stoye, Jens , title =. Theoretical Computer Science , volume =. 2009 , doi =

    2009

  46. [46]

    , title =

    Christie, David A. , title =. Information Processing Letters , volume =. 1996 , doi =

    1996

  47. [47]

    , title =

    Bafna, Vineet and Pevzner, Pavel A. , title =. SIAM Journal on Discrete Mathematics , volume =. 1998 , doi =

    1998

  48. [48]

    SIAM Journal on Discrete Mathematics , volume =

    Bulteau, Laurent and Fertin, Guillaume and Rusu, Irena , title =. SIAM Journal on Discrete Mathematics , volume =. 2012 , doi =

    2012

  49. [49]

    Silva, L. A. G. and Kowada, L. A. B. and Rocco, N. R. and Walter, M. E. M. T. , title =. arXiv preprint arXiv:2001.11570 , year =

    work page arXiv 2001

  50. [50]

    and Pevzner, Pavel A

    Alekseyev, Max A. and Pevzner, Pavel A. , title =. Theoretical Computer Science , volume =. 2008 , doi =

    2008

  51. [51]

    and Pevzner, Pavel A

    Alekseyev, Max A. and Pevzner, Pavel A. , title =. Genome Research , volume =. 2009 , doi =

    2009

  52. [52]

    Double Cut and Join with Insertions and Deletions , journal =

    Braga, Mar. Double Cut and Join with Insertions and Deletions , journal =. 2011 , doi =

    2011

  53. [53]

    da Silva, Pedro H. A. and Braga, Mar. DCJ-indel Distance with Distinct Operation Costs , booktitle =. 2012 , publisher =

    2012

  54. [54]

    da Silva, Pedro H. A. and Braga, Mar. DCJ-indel and DCJ-substitution Distances with Distinct Operation Costs , journal =. 2013 , doi =

    2013

  55. [55]

    , title =

    Chen, Di and et al. , title =. SODA 2006 , year =

    2006

  56. [56]

    Finding All Sorting Tandem Duplication Random Loss Scenarios , booktitle =

    Bernt, Matthias and T. Finding All Sorting Tandem Duplication Random Loss Scenarios , booktitle =. 2009 , publisher =

    2009

  57. [57]

    , title =

    Hartmann, Tabea and Moulton, Vincent and Stadler, Peter F. , title =. IEEE/ACM Transactions on Computational Biology and Bioinformatics , volume =. 2018 , doi =

    2018

  58. [58]

    and Stadler, Peter F

    Schmidt, Bruno J. and Stadler, Peter F. and Moulton, Vincent , title =. Discrete Applied Mathematics , year =

  59. [59]

    Knuth , title =

    Donald E. Knuth , title =

  60. [60]

    SIAM Journal on Computing , volume=

    Computing sequences with addition chains , author=. SIAM Journal on Computing , volume=. 1981 , publisher=

    1981

  61. [61]

    2005 , publisher=

    Handbook of elliptic and hyperelliptic curve cryptography , author=. 2005 , publisher=

    2005

  62. [62]

    Theoretical Computer Science , volume=

    A lower bound for the length of addition chains , author=. Theoretical Computer Science , volume=. 1975 , publisher=

    1975

  63. [63]

    Thurber , title =

    Edward G. Thurber , title =. SIAM Journal on Computing , volume =. 1999 , doi =

    1999

  64. [64]

    2018 , note =

    Thomas Schibler , title =. 2018 , note =

    2018

  65. [65]

    2025 , howpublished =

    Translocation Distance in Unary Encodings , author =. 2025 , howpublished =

    2025

  66. [66]

    Annual Symposium on Combinatorial Pattern Matching , pages=

    An algorithm for sorting by reciprocal translocations , author=. Annual Symposium on Combinatorial Pattern Matching , pages=. 2006 , organization=

    2006

  67. [67]

    Journal of Computational Biology , volume=

    Sorting by reciprocal translocations via reversals theory , author=. Journal of Computational Biology , volume=. 2007 , publisher=

    2007

  68. [68]

    Journal of Computational Biology , volume=

    Sorting genomes with centromeres by translocations , author=. Journal of Computational Biology , volume=. 2008 , publisher=

    2008

  69. [69]

    Procedia Computer Science , volume=

    Exploring the solution space of sorting by translocations , author=. Procedia Computer Science , volume=. 2012 , publisher=

    2012

  70. [70]

    Advances in Computers , volume=

    Translocation distance: Algorithms and complexity , author=. Advances in Computers , volume=. 2006 , publisher=

    2006

  71. [71]

    Bioinformatics , volume=

    CTRD: a fast applet for computing signed translocation distance between genomes , author=. Bioinformatics , volume=. 2004 , publisher=

    2004

  72. [72]

    2024 International Conference on INnovations in Intelligent SysTems and Applications (INISTA) , pages=

    Simulated Annealing and Genetic Algorithms based heuristics for computing the Non-Uniform Contiguous Translocation Distance , author=. 2024 International Conference on INnovations in Intelligent SysTems and Applications (INISTA) , pages=. 2024 , organization=

    2024

  73. [73]

    Contract , year=

    Theorems in the additive theory of numbers , author=. Contract , year=

  74. [74]

    The Electronic Journal of Combinatorics , pages=

    A Complete Annotated Bibliography of Work Related to Sidon Sequences , author=. The Electronic Journal of Combinatorics , pages=

  75. [75]

    Journal of algorithms , volume=

    A survey of fast exponentiation methods , author=. Journal of algorithms , volume=. 1998 , publisher=

    1998

  76. [76]

    Journal of algorithms , volume=

    On vectorial addition chains , author=. Journal of algorithms , volume=. 1981 , publisher=

    1981

  77. [77]

    Conference on the Theory and Application of Cryptology , pages=

    Addition chain heuristics , author=. Conference on the Theory and Application of Cryptology , pages=. 1989 , organization=

    1989

  78. [78]

    Workshop on the Theory and Application of of Cryptographic Techniques , pages=

    Efficient exponentiation using precomputation and vector addition chains , author=. Workshop on the Theory and Application of of Cryptographic Techniques , pages=. 1994 , organization=

    1994

  79. [79]

    RAIRO-Theoretical Informatics and Applications , volume=

    Speeding up the computations on an elliptic curve using addition-subtraction chains , author=. RAIRO-Theoretical Informatics and Applications , volume=. 1990 , publisher=

    1990

  80. [80]

    Translocation Distance in Unary Encodings , booktitle =

    Constantin, Maria and Micl. Translocation Distance in Unary Encodings , booktitle =. 2026 , note =

    2026

Showing first 80 references.