Sorting with constraints

Archit Manas · 2025

Read Sorting with constraints by Archit Manas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02616.txt.

Introduction

A. Manas wrote a 2025 solo theoretical computer science paper on sorting when only some pairwise comparisons are allowed. Forbidden pairs form a graph, and the question is how the graph's structure controls the cost of finding the true order.

Algorithms are parameterised by the forbidden graph's clique number and chromatic number, two measures of its density and colouring needs. Results extend to inputs that may not be fully sortable, where only the partial order can be recovered. For random forbidden graphs of Erdős–Rényi type, a simple algorithm always finds the underlying partial order with a modest number of probes. The work links a classic task, comparison sorting, to graph parameters that decide how much information each allowed comparison can yield.

Catalog record

CREATORArchit Manas
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-02616

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sorting with constraints Archit Manas Abstract In this work, we study the generalized sorting problem, where we are given a set of n n elements to be sorted, but only a subset of all possible pairwise element comparisons is allowed. We look at the problem from the perspective of the graph formed by the “forbidden” pairs, and we parametrise algorithms using the clique number and the chromatic number of this graph. We also extend these results to the class of problems where the input graph is not necessarily sortable, and one is only interested in discovering the partial order. We use our results to develop a simple algorithm that always determines the underlying partial order in O ⁡ ( n 3 / 2 ​ log ⁡ n ) O(n^{3/2}\log n) probes, when the input graph is an Erdős–Rényi graph. 1 Introduction Comparison-based sorting has been extensively studied in computer science, and its complexity is well understood. However, in many practical settings, the cost of comparing a pair of objects can be non-uniform. Non-uniform cost models can render even basic data processing tasks, such as finding the minimum or searching a key, surprisingly complex (see e.g. [ CFG+02 ] ). This motivates the exploration of structured comparison cost models. One such model is the monotone cost model: each element has an inherent numeric value, and the comparison costs are monotone functions of these values (see [ GK01 ] , [ KK03 ] ). A different line of work assumes that comparison costs satisfy the triangle inequality, and [ GK05 ] gave poly-log competitive algorithms for sorting and max-finding under this framework. In the non-uniform setting, restricted models with a small number of distinct comparison costs are also of interest. Recently, [ JWZZ24 ] made significant progress for such settings. They have an \widetilde{O}{\left(n^{1-1/(2W)}\right)} -competitive algorithm when the input has W distinct comparison costs. A special case of this model, known as the 1 - \infty cost model, occurs when certain pairs are forbidden from being compared, while all other pairs incur a unit cost. This work focuses on this model, termed the generalized sorting problem, along with some related variants. The input to the generalized sorting problem is an undirected graph G(V,E) on n=|V| vertices with m=|E| edges, where an edge (u,v)\in E indicates that the vertices u and v are comparable (these are the pairs with unit-cost for comparison). By probing the edge, we reveal a directed edge (u,v) or (v,u) depending on u\prec v or v\prec u . Let \mathchoice{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\displaystyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\displaystyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\displaystyle G\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\textstyle G\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptstyle G\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptscriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptscriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptscriptstyle G\hfil$\crcr}}}(V,\mathchoice{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\displaystyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\displaystyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\displaystyle E\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\textstyle E\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptstyle E\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptscriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptscriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptscriptstyle E\hfil$\crcr}}}) be the underlying directed graph. Given the promise that \mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr \hfil\textstyle G\hfil is an acylic graph with a Hamiltonian path, the objective is to find this path by adaptively probing the smallest number of edges in E . We let probe ( u,v ) denote the oracle function (over edges (u,v)\in E ) that returns 1 if u\prec v and 0 otherwise. When G=K_{n} , this becomes regular comparison-based sorting , and it is well-known that \Theta(n\log n) probes are both necessary and sufficient. When G=K_{\frac{n}{2},\frac{n}{2}} , this becomes the nuts and bolts sorting problem. Here too, it is known that \Theta(n\log n) probes are both necessary and sufficient, as shown in [ ABF+94 ] . In a breakthrough in [ HKK11 ] , an algorithm with probe complexity \widetilde{O}{(n^{1.5})} was presented for worst-case generalized sorting, which was later improved to \widetilde{O}{\left(\sqrt{nm}\right)} in [ KN21 ] . This remains state-of-the-art for arbitrary G . A closely related problem is one where the guarantee of \mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr \hfil\textstyle G\hfil being Hamiltonian is removed, and the objective is to determine the direction of all edges \in E by adaptively probing as few of them as possible. Yet another version is the so-called Generalized Poset Sorting Problem (GPS), in which along with G(V,E) we are additionally given an unknown poset \mathcal{P}(V,\prec) , where each probe (u,v) returns the relation between u,v , that is, u\prec v,v\prec u or u\nsim v . This has been studied in [ JWZZ24 ] . As mentioned above, we term the edges (u,v) not present in G as forbidden , denoting that these pairs of vertices cannot be compared. Let H denote the (undirected) graph on V formed by the forbidden edges. It is natural to expect that if |H| is small, one can find the total order with a few probes. This is indeed the case, as shown in [ BR16 ] , where the path is found in O((|H|+n)\log n) probes. In fact, the algorithm works even if the guarantee that \mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr \hfil\textstyle G\hfil is Hamiltonian is removed. 2 Preliminaries In this work, we obtain algorithms for the generalized sorting problem, as well as in the scenario when the promise of a total order is removed, through two metrics of H that can estimate how “locally” small the latter is. In particular, we show the following: 1. Let \chi(H) denote the chromatic number of H , that is, the least positive integer d so that there exists a function f:V\mapsto[d] with f(x)\neq f(y) for all (x,y)\in H . Then, O(n\log n+n\chi(H)) probes are sufficient to determine all edges of \mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr \hfil\textstyle G\hfil . We call this algorithm ColorSolve . 2. Let \omega(H) denote the clique number of H , that is, the size of the largest complete subgraph in H . Then, O(n\omega(H)\log n) probes are sufficient to determine all the edges of \mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr \hfil\textstyle G\hfil . We call this algorithm CliqueSolve . Both the above algorithms work even without the guarantee of \mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr \hfil\textstyle G\hfil containing a hamiltonian path. Due to \omega(H)\leq\chi(H) , it can be seen that CliqueSolve is more optimal (up to logarithmic factors). Although the time complexities of the algorithms are not of immediate concern to us, it can be seen that • Given the coloring of H in \chi(H) colors, ColorSolve runs in polynomial time. • CliqueSolve runs in polynomial time. A way to speed up the algorithm presented is briefly described at the end of Section 4.4 , after an analysis of the algorithm’s probe complexity. Section 3 and Section 4 are dedicated to proving these results. In Section 5 , we show that CliqueSolve can be used to design a algorithm that correctly sorts G while using O(n\log^{2}n) probes with high probability, when G is generated randomly with edge probability p=\Omega(1) . When p is arbitrary, we design an algorithm that makes \tilde{O}(n^{3/2}) probes, depending on whether p exceeds the threshold \frac{\log n}{\sqrt{n}} or not. It was also shown in [ BR16 ] that \tilde{O}(n^{3/2}) comparisons suffice for general G(n,p) , but we mention our algorithm since the techniques we use are different. As remarked earlier, these algorithms do not require the guarantee of the input graph having a hamiltonian path. When the existence of a hamiltonian path is guaranteed, i.e., in the so called stochastic generalised sorting problem , where edges other than the hamiltonian path are added

Read the complete text