Why are these two definitions of PPAD equivalent? The complexity class PPAD is usually defined by stating that End-Of-The-Line is PPAD-complete.


  End-Of-The-Line is a search problem. The input consists of a directed graph in which each node has in-degree and out-degree at most 1. The graph is given by a polynomial-time computable function $f(x)$ that returns the predecessor and successor of $x$. In addition, one is given a node $v$ with a successor but no predecessor. Find a node $t\ne v$ that has no successor or no predecessor.


Recently, I heard a different definition of PPAD. As far as I recall, it was based on the following problem.


  A directed graph (again specified by a polynomial-time computable function) and a node whose in-degree is not equal its out-degree is given. Find another node with this property.




Clearly, End-Of-The-Line is a special case of the latter problem but is the latter problem really more difficult to solve? My question is this:


  Are both problems complete for the same complexity class PPAD? If yes, why? If not, what is the complexity class resulting from the second problem?
For issues with the cited paper, (and hence this answer) see Does PPAD really capture the notion of finding another unbalanced vertex?

Yes. These two problems are equivalent and hence PPAD-complete. The reduction is given on page 505 of Papadimitriou's original 1994 paper (pdf) introducing End of the Line. This is valid even if the degree of the graph is exponential, provided we are given an "edge-recognition algorithm" and a "pairing function". This is also mentioned on the same page. The reduction is given for PPA (the undirected version of PPAD). It can be extended to PPAD as well.