arxiv: 2604.24237 · v2 · submitted 2026-04-27 · 💻 cs.DS

Recognition: unknown

Computational Complexity of the Interval Ordering Problem

Simeon Pawlowski , Vincent Froese

Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:25 UTC · model grok-4.3

classification 💻 cs.DS

keywords interval orderingdynamic programmingsubadditive functionssuperadditive functionsoracle complexityNP-hardnessbioinformatics applications

0 comments

The pith

Dynamic programming solves the interval ordering problem using O(2^n poly(n)) oracle calls to any cost function f.

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

The paper develops a dynamic programming method to order a set of n intervals so that the total cost, defined by applying a given function f to each interval's uncovered segments, is minimized. This yields a single-exponential algorithm that works for arbitrary f given only by oracle access. The same framework produces polynomial-time solutions whenever f minus its value at zero is subadditive or superadditive, which settles the complexity of the exponential function f(x) = 2^x that had been left open. Complementary lower bounds of 2^{n-1} oracle calls for general f and NP-hardness for certain simple functions show that the exponential dependence is essentially tight in the worst case.

Core claim

We develop a dynamic programming approach which solves the problem with O(2^n poly(n)) oracle calls to f and arithmetic operations. Moreover, our approach yields polynomial-time algorithms for all cost functions f such that f-f(0) is subadditive or superadditive. This answers an open question for the function f(x)=2^x. We contrast these results by proving a running time lower bound of 2^{n-1} for any algorithm that solves the problem for every function f (with oracle access only) and further proving NP-hardness for some classes of simple functions.

What carries the argument

Dynamic programming over subsets of intervals that tracks the minimum cost achievable for each subset while recording the last interval placed, using oracle evaluations of f on the lengths of newly exposed segments.

If this is right

Any cost function f given by oracle can be optimized over interval orderings in single-exponential time.
Polynomial-time algorithms exist for every f where f minus f(0) is subadditive or superadditive.
The specific function f(x) = 2^x admits a polynomial-time algorithm.
No algorithm can solve the problem for every f with fewer than 2^{n-1} oracle calls in the worst case.
The problem remains NP-hard for certain simple, explicitly described cost functions.

Where Pith is reading between the lines

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

The subadditive and superadditive classes likely cover many natural cost functions arising in sequence alignment or coverage problems.
The subset DP structure may extend directly to related problems such as interval scheduling with nonlinear costs.
The gap between the 2^n upper bound and 2^{n-1} lower bound leaves open whether a modest improvement such as 2^n / n or 1.9^n is possible for general f.
Practical implementations could exploit the fact that many real-world f are subadditive, turning the theoretical polynomial-time result into usable code.

Load-bearing premise

The cost function is accessible only through an oracle returning its value for any queried length, and the input consists of n intervals with explicit endpoints whose time cost is counted in oracle calls plus arithmetic steps.

What would settle it

An algorithm that computes an optimal ordering for every oracle-accessible f using fewer than 2^{n-1} calls in the worst case, or a subadditive cost function whose optimal ordering cannot be found in polynomial time.

read the original abstract

We study an interval ordering problem introduced by D\"urr et al. [Discrete Appl. Math. 2012] which is motivated by applications in bioinformatics. The task is to order a given set of n intervals with the goal of minimizing a certain objective which is defined via a given cost function $f$ which assigns a cost to the exposed part of each interval (that is, the pieces not covered by previous intervals). We develop a dynamic programming approach which solves the problem with $O(2^n\text{poly}(n))$ oracle calls to $f$ and arithmetic operations. Moreover, our approach yields polynomial-time algorithms for all cost functions $f$ such that $f-f(0)$ is subadditive or superadditive. This answers an open question for the function $f(x)=2^x$. We contrast these results by proving a running time lower bound of $2^{n-1}$ for any algorithm that solves the problem for every function $f$ (with oracle access only) and further proving NP-hardness for some classes of simple functions. Thus, we significantly narrow the gap regarding the computational complexity of the problem.

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.

Desk Editor's Note private letter to a colleague

This paper gives a subset DP for interval ordering that runs in O(2^n poly(n)) oracle time, identifies the sub- and superadditive cases that go polynomial, and supplies a matching 2^{n-1} lower bound.

read the letter

The main result is a dynamic programming algorithm over subsets that computes the minimum-cost ordering of n intervals under an oracle cost function f. The state DP[S] holds the min cost for the intervals in S, and the recurrence picks the last interval j, adds f of the length exposed by j after subtracting the union of the rest of S. Because exposure depends only on the predecessor set, not its order, the recurrence is valid and yields the stated O(2^n poly(n)) bound after sorting endpoints for each union check. The same DP immediately gives polynomial time whenever f minus f(0) is subadditive or superadditive, which settles the open case for f(x) = 2^x. They also prove a 2^{n-1} oracle lower bound for arbitrary f via an adversary argument and show NP-hardness for certain simple non-additive functions. These pieces are new relative to the cited prior work and rest on explicit construction rather than fitting or circular definitions. The recurrence and lower-bound argument are internally consistent with the interval-union model. The NP-hardness statement is narrower than the general case, applying only to some simple functions, so it leaves open whether other non-additive costs remain tractable. The model assumes oracle access to f and explicit endpoints, which is standard but limits direct applicability to implicit or continuous settings. This work is aimed at people working on exact algorithms for ordering problems or on complexity classifications for cost functions in bioinformatics. A reader who needs concrete exponential-time methods or who studies when subset DP collapses to polynomial time will find the bounds useful. It deserves a serious referee because the algorithmic contribution is checkable and the complexity gap is narrowed in a precise way.

Referee Report

0 major / 2 minor

Summary. The paper claims the development of a dynamic programming approach for the interval ordering problem that solves it with O(2^n poly(n)) oracle calls to the cost function f and arithmetic operations. It also provides polynomial-time algorithms when f - f(0) is subadditive or superadditive, answering an open question for f(x)=2^x. The paper contrasts this with a 2^{n-1} lower bound for general f and NP-hardness for some simple functions.

Significance. This result is significant as it narrows the gap in the computational complexity of the interval ordering problem. The polynomial time algorithms for sub- and superadditive cost functions, including the case f(x)=2^x, are particularly valuable. The explicit DP construction and the lower bound via adversary argument are strengths of the work.

minor comments (2)

[Abstract] The abstract could briefly reference the specific open question from Durr et al. to better highlight the contribution.
[Section 3] In the DP section, the time for computing union lengths in each transition (O(n log n) via endpoint sorting) contributes to the poly(n) factor; explicitly stating the overall polynomial degree would improve precision.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. The referee's summary accurately reflects our contributions, including the O(2^n poly(n)) DP algorithm, the polynomial-time results for subadditive and superadditive functions (resolving the open question for f(x)=2^x), the 2^{n-1} lower bound, and the NP-hardness results.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained algorithmic construction

full rationale

The paper's central results consist of an explicit dynamic programming recurrence over subsets (DP[S] defined via min over last interval j of DP[S-j] plus f applied to the exposed measure of j after the union of predecessors), which follows directly from the set-based definition of exposed length without any fitting, renaming, or self-referential closure. Subadditivity/superadditivity properties are used to collapse the DP to polynomial time via standard optimization arguments, and the 2^{n-1} lower bound is obtained from an adversary argument on oracle responses. NP-hardness reductions are standard and independent. No load-bearing step reduces to a self-citation, fitted input, or ansatz smuggled from prior work; the derivation is fully constructive and verifiable from the problem statement alone.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard dynamic programming over subsets and classical complexity theory; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Standard model of computation in which oracle calls to f and arithmetic operations each take unit time.
Used to bound the running time by O(2^n poly(n)).

pith-pipeline@v0.9.0 · 5493 in / 1250 out tokens · 23044 ms · 2026-05-08T03:25:55.007892+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

[1]

Distance geometry and related methods for protein structure determination from NMR data

Werner Braun. Distance geometry and related methods for protein structure determination from NMR data. Quarterly Reviews of Biophysics , 19(3-4):115--157, 1987. https://doi.org/10.1017/S0033583500004108 doi:10.1017/S0033583500004108

work page doi:10.1017/s0033583500004108 1987
[2]

Fundamentals of Parameterized Complexity

Rodney G. Downey and Michael R. Fellows. Fundamentals of parameterized complexity , volume 4. Springer, 2013. https://doi.org/10.1007/978-1-4471-5559-1 doi:10.1007/978-1-4471-5559-1

work page doi:10.1007/978-1-4471-5559-1 2013
[3]

Duxbury, L

Phillip M. Duxbury, L. Granlund, SR Gujarathi, Pavol Juhas, and Simon JL Billinge. The unassigned distance geometry problem. Discrete Applied Mathematics , 204:117--132, 2016. https://doi.org/10.1016/j.dam.2015.10.029 doi:10.1016/j.dam.2015.10.029

work page doi:10.1016/j.dam.2015.10.029 2016
[4]

Spieksma, Fabrice Talla Nobibon, and Gerhard J

Christoph Dürr, Maurice Queyranne, Frits C.R. Spieksma, Fabrice Talla Nobibon, and Gerhard J. Woeginger. The interval ordering problem. Discrete Applied Mathematics , 160(7):1094--1103, 2012. https://doi.org/10.1016/j.dam.2011.12.020 doi:10.1016/j.dam.2011.12.020

work page doi:10.1016/j.dam.2011.12.020 2012
[5]

Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations , pages 85--103. Springer US, 1972. https://doi.org/10.1007/978-1-4684-2001-2_9 doi:10.1007/978-1-4684-2001-2_9

work page doi:10.1007/978-1-4684-2001-2_9 1972
[6]

Recent advances on the discretizable molecular distance geometry problem

Carlile Lavor, Leo Liberti, Nelson Maculan, and Antonio Mucherino. Recent advances on the discretizable molecular distance geometry problem. European Journal of Operational Research , 219(3):698--706, 2012. https://doi.org/10.1016/j.ejor.2011.11.007 doi:10.1016/j.ejor.2011.11.007

work page doi:10.1016/j.ejor.2011.11.007 2012
[7]

A cycle-based formulation for the distance geometry problem

Leo Liberti, Gabriele Iommazzo, Carlile Lavor, and Nelson Maculan. A cycle-based formulation for the distance geometry problem. Graphs and Combinatorial Optimization: from Theory to Applications: CTW2020 Proceedings , pages 93--106, 2021. https://doi.org/10.1007/978-3-030-63072-0_8 doi:10.1007/978-3-030-63072-0_8

work page doi:10.1007/978-3-030-63072-0_8 2021
[8]

Mor \'e and Zhijun Wu

Jorge J. Mor \'e and Zhijun Wu. Global continuation for distance geometry problems. SIAM Journal on Optimization , 7(3):814--836, 1997. https://doi.org/10.1137/S1052623495283024 doi:10.1137/S1052623495283024

work page doi:10.1137/s1052623495283024 1997