Bisimplicial edges in bipartite graphs

Bisimplicial edges in bipartite graphs are closely related to pivots in Gaussian elimination that avoid turning zeroes into non-zeroes. We present a new deterministic algorithm to find such edges in bipartite graphs. Our algorithm is very simple and easy to implement. Its running-time is O(nm)O(nm), where nn is the number of vertices and mm is the number of edges. Furthermore, for any fixed pp and random bipartite graphs in the Gn,n,pGn,n,p model, the expected running-time of our algorithm is O(n2)O(n2), which is linear in the input size.