Bidirectional Edges Problem: Part I - A Simple Algorithm

The "bidirectional edges problem" is to find an edge-labeling of an undirected network, G = (V, E), with a source and a sink, such that an edge [u, v] ∈ E is labeled 〈u, v〉 or 〈v, u〉 (or both) depending on the existence of a (simple) path from the source to sink that visits the vertices u and v, in the order u v or v, u, respectively. We provide several algorithms for this problem in the current paper and the sequel. In this paper we show the relation between this problem and the classical two-vertex-disjoint-paths problem and then devise a simple algorithm with a time complexity of O(\E\ · |V|²). In the sequel we improve the time complexity to O(\E\ · |V|). The main technique exploits a clever partition of the graph into a set of paths and bridges which are then analyzed recursively. The bidirectional edges problem arises naturally in the context of the simulation of an MOS transistor network, in which a transistor may operate as a unilateral or a bilateral device, depending on the voltages at its source and drain nodes. For efficient simulation, it is required to detect the set of transistors that may operate as bilateral devices. Also, sometimes it is intended to propagate information in one direction only, and propagation in the wrong direction (resulting in a sneak path) can cause functional error. Our algorithms can be used to detect all the sneak paths.