13
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ I have a trouble with extending the argument to PPAD. In the original proof new vertices are produced by combining pairs of edges of the same old vertex. For PPAD it seems natural to combine incoming and outcoming edges. But then it is no longer guaranteed that each unbalanced old vertex produces only one unbalanced new vertex. And if there are many of them then a search in the new graph may return another new vertex produced by the same old vertex. This does not give an answer for the original problem. How can one overcome this trouble? $\endgroup$
    – Daniil Musatov
    Feb 2, 2017 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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