Acyclically pushable bipartite permutation digraphs: An algorithm

Given a digraph D=(V,A) and an X⊆V, D^X 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⊆V such that D^X 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(m²) time algorithm to decide whether a bipartite permutation digraph is acyclically pushable and, if yes, to find a set X such that D^X is acyclic. (Huang, MacGillivray and Yeo's result clearly implies an O(n⁸) 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 D^X 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 D^X is acyclic or a proof that D is not acyclically pushable.