8
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

Well, at least $\#\mathsf{P}$-hard. Given a SAT formula, construct a graph with two vertices, $v_x$ and $v_x'$, for every possible assignment of variables $\vec{x}$. If $x$ is a satisfying assignment for the formula, draw an edge between $v_x$ and $v_x'$; these are the only edges. It is easy to construct the circuit for this graph from the SAT formula, and the number of odd vertices is exactly twice the number of satisfying assignments.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.