Pushing vertices and orienting edges (Q2761044)

Pushing a vertex \(v\) of a digraph \(G=(V,E)\) is an edge operation which reverses the orientation of all edges incident with \(v\). It is proved that the problems to decide whether vertices of an arbitrary digraph can be pushed so as to produce strongly connected digraphs, semi-connected digraphs, acyclic digraphs or Hamiltonian digraphs are all NP-complete. It is also shown that almost any tournament can be transformed into a strongly connected digraph using the push operation and that a broad class of digraphs which include outerplanar digraphs can be transformed into directed acyclic graphs using the push operation. Necessary conditions for transforming a digraph using the push operation into one having a directed Hamiltonian cycle are also discussed.