A recognition algorithm for adjusted interval digraphs (Q2656971)

Adjusted interval digraphs, being a generalization of interval graphs, are characterized by the existence of a min ordering and by the absence of invertible pairs. It can be shown that for a given graph with \(n\) nodes and \(m\) edges, the characterizations of adjusted interval digraphs yield a recognition algorithm with running time \(O(m^2+n^2)\), as opposed to a known \(O(n^4)\)-time recognition algorithm. The question of finding a linear-time recognition algorithm remains open. The purpose of this paper is to present an \(O(n^3)\)-time recognition algorithm for adjusted interval digraphs, thereby producing a min ordering or finding an invertible pair of the given graph if one exists. As a result, it also gives an alternative proof to show that a reflexive digraph has a min ordering if and only if it has no invertible pairs.