Path problems in skew-symmetric graphs (Q2563512)

This paper concerns path problems in skew-symmetric graphs. A skew-symmetric graph is a digraph \(G=(V,E)\) together with a mapping \(\sigma\) of \(V\cup E\) onto itself such that (i) \(\sigma\) is an involution \((\sigma(x)\neq x\) and \(\sigma(\sigma(x))=x)\); (ii) \(\sigma(v)\in V\) for every \(v\in V\); (iii) \(\sigma(e)=(\sigma(v),\sigma(u))\) for every \(e=(u,v)\in E\). Generalizations of the standard graph reachability and shortest path problems are studied. The authors establish combinatorial solvability criteria and duality relations for skew-symmetric path problems and use these to design efficient algorithms for these problems. The algorithms are competitive with the fastest algorithms for the standard problems.