Efficiently Realizing Interval Sequences
Amotz Bar-Noy, Keerti Choudhary, David Peleg, Dror Rawitz · SIAM Journal on Discrete Mathematics · 2020
We consider the problem of realizable interval sequences. An interval sequence is comprised of $n$ integer intervals $[a_i,b_i]$ such that $0\le a_i\leq b_i \le n-1$ and is said to be graphic/realizable if there exists a graph with degree sequence, say, $D=(d_1,\ldots,d_n),$ satisfying the condition $a_i\leq d_i\leq b_i$ for each $i\in[1,n]$. There is a characterization (also implying an $O(n)$ verifying algorithm) known for realizability of interval sequences, which is a generalization of the Erdös--Gallai characterization for graphic sequences. However, given any realizable interval sequence, there is no known algorithm for computing a corresponding graphic certificate in $o(n^2)$ time. In this paper, we provide an $O(n \log n)$ time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is nonrealizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence in the same time. Finally, we consider variants of the problem, such as computing the most-regular graphic sequence and computing a minimum extension of a length $p$ nongraphic sequence to a graphic one.