According to Handshaking Lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem).
PPA ( Christos Papadimitriou in 1994 [1]) is defined as follows. Suppose we have a graph on whose vertices are n-bit binary strings, and the graph is represented by a polynomial-sized circuit that takes a vertex as input and outputs its neighbors. (Note that this allows us to represent an exponentially-large graph on which we can efficiently perform local exploration.) Suppose furthermore that a specific vertex (say the all-zeroes vector) has an odd number of neighbors. We are required to find another odd-degree vertex. The corresponding class of parity arguments for directed graphs is belong to PPAD.
My question: What is the complexity of counting odd nodes in directed and undirected graph?
[1] Papadimitriou, Christos H. "On the complexity of the parity argument and other inefficient proofs of existence." Journal of Computer and system Sciences 48.3 (1994): 498-532.
