Pushing vertices in digraphs without long induced cycles (Q1613399): Difference between revisions

For a given digraph and a subset \(X\) of its vertex set, pushing \(X\) in the digraph means reversing the orientation of all arcs with exactly one end in \(X\). The problem is to determine whether a digraph can be made acyclic using the push operation. It is shown that the problem remains NP-complete even when restricted to the class of oriented bipartite graph. The paper characterizes the acyclically pushable chordal digraphs in terms of two forbidden subdigraphs, and shows that there is no similar characterization for the family of chordal bipartite digraphs. In addition, a polynomial algorithm for solving the problem for a subclass of the class of chordal bipartite digraphs is given. Finally, the paper gives a characterization of the acyclically pushable bipartite permutation digraphs in terms of a finite number of forbidden subdigraphs.