Acyclically pushable bipartite permutation digraphs: an algorithm (Q2497498)

Let \(D(X)\) denote the digraph obtained from a given digraph \(D\) by reversing those arcs with exactly one end in a vertex subset \(X\). The digraph \(D\) is said to be acyclically pushable when there is an \(X\) such that \(D(X)\) is acyclic. The paper gives an algorithmic proof of an early result on characterizing those bipartite permutation digraphs that are acyclically pushable in terms of two excluded induced subgraphs on 7 and 8 vertices. It is claimed that the algorithm can be accomplished in \(O(mm)\) time. A strongly acyclic digraph is a digraph \(D\) such that \(D(X)\) is acyclic for every \(X\). It is shown that another early result can be essentially regarded as a characterization of strongly acyclic digraphs. It also provides linear-time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists. Finally, the paper presents an alternate proof of a theorem on characterizing acyclically pushable bipartite tournaments, leading 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.