<p><strong>For issues with the cited paper, (and hence this answer) see <a href="https://cstheory.stackexchange.com/questions/37481/does-ppad-really-capture-the-notion-of-finding-another-unbalanced-vertex">Does PPAD really capture the notion of finding another unbalanced vertex?</a></strong></p>

<p>Yes. These two problems are equivalent and hence PPAD-complete. The reduction is given on page 505 of Papadimitriou's original 1994 <a href="http://portal.acm.org/citation.cfm?id=183127" rel="nofollow noreferrer">paper</a> (<a href="http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" rel="nofollow noreferrer">pdf</a>) introducing <em>End of the Line</em>. 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.</p>

CC BY-SA 3.0
2017-02-02T16:41:03.227Z
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?
Daniil Musatov
CC BY-SA 3.0
2010-10-17T15:26:58.877Z
2017-03-23T09:48:28.770Z
2017-04-13T12:32:28.117Z
Shiva Kintali
<p>The complexity class <a href="http://en.wikipedia.org/wiki/PPAD_%28complexity%29">PPAD</a> is usually defined by stating that End-Of-The-Line is PPAD-complete.</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<blockquote>
  <p>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.</p>
</blockquote>

<hr>

<p>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:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<cc.complexity-theory><complexity-classes><ppad>
Why are these two definitions of PPAD equivalent?
Matthias
# Why are these two definitions of PPAD equivalent?

(Asked by: username_0 on 2010-10-17)

The complexity class [PPAD](http://en.wikipedia.org/wiki/PPAD_%28complexity%29) 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?

**Tags:** cc.complexity-theory, complexity-classes, ppad


---

## 1 answers

### Answer by username_1 on 2010-10-17. Score: 15 | Accepted answer

**For issues with the cited paper, (and hence this answer) see [Does PPAD really capture the notion of finding another unbalanced vertex?](https://cstheory.stackexchange.com/questions/37481/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](http://portal.acm.org/citation.cfm?id=183127) ([pdf](http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.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.

> **Comments:**
> **username_2**: 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?  

---

