Sorting Under 1-$\infty$ Cost Model

Abstract

In this paper we study the problem of sorting under non-uniform comparison costs, where costs are either 1 or $\infty$. If comparing a pair has an associated cost of $\infty$ then we say that such a pair cannot be compared (forbidden pairs). Along with the set of elements $V$ the input to our problem is a graph $G(V,E)$, whose edges represents the pairs that we can compare incurring an unit of cost. Given a graph with $n$ vertices and $q$ forbidden edges we propose the first non-trivial deterministic algorithm which makes $O((q+n)\log n)$ comparisons with a total complexity of $O(n^2+q^{\omega /2})$, where $\omega$ is the exponent in the complexity of matrix multiplication. We also propose a simple randomized algorithm for the problem which makes $\tilde{O}(n^2/\sqrt{q+n}+n\sqrt{q})$ probes with high probability. When the input graph is random we show that $\tilde{O}(\min (n^{3/2},p{n}^2))$ probes suffice, where $p$ is the edge probability.

12 pages, 1 figure, submitted to STOC 2016