Acyclically pushable bipartite permutation digraphs: An algorithm

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.)We define a strongly acyclic digraph as a digraph D   such that DXDX is acyclic for every X. We show how a result of Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1–3) (1999) 27–33] can be essentially regarded as a characterization of strongly acyclic digraphs and also provides linear time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists. Besides revealing this connection, we add simplicity to the structural and algorithmic results first given in Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1–3) (1999) 27–33]. In particular, we avoid decomposing the graph into triconnected components.We give an alternate proof of a theorem of Huang, MacGillivray and Wood characterizing acyclically pushable bipartite tournaments. Our proof leads to a linear time algorithm which, given a bipartite tournament as input, either returns a set X   such that DXDX is acyclic or a proof that D is not acyclically pushable.