Acyclically pushable bipartite permutation digraphs: An algorithm Original Research Article

Given a digraph D=(V,A)D=(V,A) and an X⊆VX⊆V, DXDX denotes the digraph obtained from D by reversing those arcs with exactly one end in X. A digraph D is called acyclically pushable when there exists an X⊆VX⊆V such that DXDX is acyclic. Huang, MacGillivray and Yeo have recently characterized, in terms of two excluded induced subgraphs on 7 and 8 nodes, those bipartite permutation digraphs which are acyclically pushable. We give an algorithmic proof of their result. Our proof delivers an O(m2)O(m2) time algorithm to decide whether a bipartite permutation digraph is acyclically pushable and, if yes, to find a set X such that DXDX is acyclic. (Huang, MacGillivray and Yeoʹs result clearly implies an O(n8)O(n8) time algorithm to decide but the polynomiality of constructing X was still open.)