Hello, I know how chinese postman algorithm works. But my confusion is on complexity. Is it possible to solve this on polynomial time?? because, if there are n odd vertices , then they can be paired (n-1)*(n-3)*(n-5)*.....1 So , to generate all possible pairing we need massive time if n is big.

So, My first question is , Is it possible to calculate pairing with any algorithm in polynomial time??

And, Is there another approach where pairing is not needed and can be solved on polynomial time??

Please answer.