[mvanotti]

Once you have a mixed graph (One-way streets and two-way streets), the problem is known as the Mixed Chinese Postman Problem and is NP.