An $O(n^2)$ time algorithm for the minimal permutation completion problem

Abstract In the Minimal Permutation Completion problem, one is given an arbitrary graph G = ( V , E ) and the aim is to find a permutation super-graph H = ( V , F ) defined on the same vertex set and such that F ⊇ E is inclusion-minimal among all possibilities. The graph H is then called a minimal permutation completion of G . We provide an O ( n 2 ) incremental algorithm computing such a minimal permutation completion. To the best of our knowledge, this result leads to the first polynomial algorithm for this problem. A preliminary extended abstract of this paper appeared as [ 4 ] in the Proceedings of WG 2015.