  An important tool in analyzing complex social and information networks is s-t
simple path counting, which is known to be #P-complete. In this paper, we study
efficient s-t simple path counting in directed graphs. For a given pair of
vertices s and t in a directed graph, first we propose a pruning technique that
can efficiently and considerably reduce the search space. Then, we discuss how
this technique can be adjusted with exact and approximate algorithms, to
improve their efficiency. In the end, by performing extensive experiments over
several networks from different domains, we show high empirical efficiency of
our proposed technique. Our algorithm is not a competitor of existing methods,
rather, it is a friend that can be used as a fast pre-processing step, before
applying any existing algorithm.
