  We formulate and study the thinnest path problem in wireless ad hoc networks.
The objective is to find a path from a source to its destination that results
in the minimum number of nodes overhearing the message by a judicious choice of
relaying nodes and their corresponding transmission power. We adopt a directed
hypergraph model of the problem and establish the NP-completeness of the
problem in 2-D networks. We then develop two polynomial-time approximation
algorithms that offer $\sqrt{\frac{n}{2}}$ and $\frac{n}{2\sqrt{n-1}}$
approximation ratios for general directed hypergraphs (which can model
non-isomorphic signal propagation in space) and constant approximation ratios
for ring hypergraphs (which result from isomorphic signal propagation). We also
consider the thinnest path problem in 1-D networks and 1-D networks embedded in
2-D field of eavesdroppers with arbitrary unknown locations (the so-called
1.5-D networks). We propose a linear-complexity algorithm based on nested
backward induction that obtains the optimal solution to both 1-D and 1.5-D
networks. This algorithm does not require the knowledge of eavesdropper
locations and achieves the best performance offered by any algorithm that
assumes complete location information of the eavesdroppers.
