<p>The problems have been proved to be equivalent (and thus PPAD-complete), see Section 8 in <a href="https://arxiv.org/abs/1902.07657" rel="noreferrer">The Hairy Ball Problem is PPAD-Complete by Paul W. Goldberg and Alexandros Hollender</a>.</p>

CC BY-SA 4.0
2019-05-11T06:06:06.647Z
Thanks. It turns out that the proof appeared in an earlier technical report by the same authors: [The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard](http://eccc.weizmann.ac.il/report/2018/120/)
Daniil Musatov
CC BY-SA 4.0
2019-02-21T11:02:44.033Z
2019-02-21T11:02:44.033Z
domotorp
<p>This is an interesting question, and I can only give a partial answer.</p>

<p>It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of <strong>AUV</strong> with its special case</p>

<blockquote>
  <p><strong>MANY ENDS OF THE LINE (MEOL):</strong> Given a directed graph $G$ with in-degree and out-degree at most $1$ (represented by circuits as above), and a nonempty set $X$ of sources of $G$, find a sink or a source $v\notin X$.</p>
</blockquote>

<p>On the one hand, I find it hard to imagine a transformation of such graphs that could reduce a larger number of sources to one.</p>

<p>However, on the other hand, <strong>MEOL</strong> belongs to all commonly studied classes containing <strong>PPAD</strong> except possibly <strong>PPAD</strong> itself:</p>

<p>First, obviously, </p>

<blockquote>
  <p><strong>MEOL</strong> is in <strong>PPADS</strong>.</p>
</blockquote>

<p>I will sketch below an argument that </p>

<blockquote>
  <p><strong>MEOL</strong> is in <strong>PPA</strong></p>
</blockquote>

<p>by reduction to the standard <strong>PPA</strong>-complete problem (the undirected version of <strong>AEOL</strong>). Assume we are given $G=(V,E)$ and $X$ as in the definition of MEOL.</p>

<p>If $|X|$ is odd, we can just make the graph undirected, include a matching on all but one vertex from $X$ (as in the argument on p. 505), and pass the result along with the remaining source from $X$ to the <strong>PPA</strong> oracle.</p>

<p>In general, let $s=|X|$, and $2^k$ be the largest power of $2$ that divides $s$. We define a new graph $G'=(V',E')$ whose vertices are $2^k$-element subsets of $V$. If $A,B\in V'$ are such sets, we put the edge $(A,B)$ in $E'$ if we can enumerate the sets as $A=\{a_0,\dots,a_{2^k-1}\}$, $B=\{b_0,\dots,b_{2^k-1}\}$ in such a way that $(a_i,b_i)\in E$ for each $i&lt;2^k$.</p>

<p>Clearly, $G'$ is a directed graph with in-degree and out-degree at most $1$. An $A\in V'$ is a source (sink) iff it contains a source (sink, resp.) of $G$. (That is, if it contains both, it is an isolated vertex.) So, any such vertex would lead to a solution of the <strong>MEOL</strong> instance, unless $A$ is a “known source”: that is, $A\cap X\ne\varnothing$. We intend to make the graph undirected, and manipulate it so that the number of known sources is reduced to $1$ by including a matching on the remaining ones.</p>

<p>So, if $A$ is a known source, let $t=|A\cap X|$, which satisfies $0&lt;t\le2^k$. If $t=2^k=|A|$, then simply $A\subseteq X$. The number of such sets is $\binom{s}{2^k}$. Recall that the multiplicity of a prime $p$ in $\binom ab$ equals the number of carries in the addition $b+(a-b)=a$ performed in base $p$. By the choice of $k$, it follows that $\binom{s}{2^k}$ is odd. Moreover, there are polynomial-time bijections between $[0,\binom ab)$, and $b$-element subsets of $[0,a)$. Using this, we can define a polynomial-time matching on all but one of $2^k$-element subsets of $X$. We include it in the graph, which reduces the number of known sources with $t=2^k$ to $1$.</p>

<p>For $0&lt;t&lt;2^k$, the carry-counting formula shows that $\binom st$ is even. Again, we can find an explicit matching on $t$-element subsets of $X$. We extend it to known sources $A$ with $|A\cap X|=t$ by applying the matching to $A\cap X$, and leaving $A\smallsetminus X$ fixed.</p>

<p>In this way, we produce an undirected graph with one known leaf vertex. We ask the <strong>PPA</strong> oracle for another leaf, and by construction, we can extract from it an answer for the <strong>MEOL</strong> instance.</p>

<hr>

<p>As briefly mentioned by Papadimitriou, we can generalize <strong>PPA</strong> to classes <strong>PPA</strong>-$p$ for any prime $p$. An example of a <strong>PPA</strong>-$p$ complete problem is</p>

<blockquote>
  <p><strong>AUV</strong>-$p$: Given a directed graph $G$, and a vertex whose degree balance is ${}\not\equiv0\pmod p$, find another such vertex.</p>
</blockquote>

<p>(See <a href="https://cstheory.stackexchange.com/a/37794">this answer</a> for the equivalence of <strong>AUV</strong>-$p$ with Papadimitriou’s definition of <strong>PPA</strong>-$p$.) </p>

<p><strong>PPA</strong>-$2$ is just <strong>PPA</strong>. The classes <strong>PPA</strong>-$p$ are assumed to be pairwise incomparable, and incomparable with <strong>PPADS</strong>. They all include <strong>PPAD</strong>.</p>

<p>There was nothing particularly special about $p=2$ in the argument I outlined above, and it can be easily modified to yield</p>

<blockquote>
  <p><strong>MEOL</strong> is in <strong>PPA</strong>-$p$ for every prime $p$.</p>
</blockquote>

CC BY-SA 3.0
2017-02-15T09:03:21.100Z
I like the answer very much and have decided accept it (of course, more complete answers are still welcomed). I only think that the class represented by **AUV**-$p$ should be called **PPAD**-$p$. Papadimitriou writes about undirected bipartite graphs and just degrees, not balances.
Daniil Musatov
CC BY-SA 3.0
2017-02-15T09:38:37.873Z
The classes are generalizations of PPA, not PPAD, for $p=2$. Papadimitriou gives a different complete problem than AUV-$p$ (note that his graphs are bipartite), but it is equivalent to my definition. The whole naming scheme is terribly confusing; the usage of directed vs. undirected graphs for a particular class is just an accident, many of the classes have complete problems concerning both directed and undirected graphs (as in the case of PPA-$p$).  Also, despite their names, most of the classes are *not* based on parity arguments, but other counting principles. Only PPA is about parity.
Emil Jeřábek
CC BY-SA 3.0
2017-02-16T11:51:24.363Z
Thanks, got it. It is indeed the same class. I have heard a speculation that Papadimitriou has chosen the name PPAD because it resembles his own surname.
Daniil Musatov
CC BY-SA 3.0
2018-02-28T14:04:06.470Z
Do you have a reference for PPAD being in PPA-p?
domotorp
CC BY-SA 3.0
2018-02-28T15:25:47.107Z
Not an explicit one, but for instance, the defining PPAD-complete problem is literally a special case of AUV-$p$.
Emil Jeřábek
CC BY-SA 3.0
2017-02-13T19:44:21.847Z
2017-03-20T18:59:17.690Z
2017-04-13T12:32:28.743Z
Emil Jeřábek
<p>Complexity class <strong>PPAD</strong> was invented by Christos Papadimitriou in his seminal 1994 <a href="http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" rel="nofollow noreferrer">paper</a>. The class is designed to capture the complexity of search problems where the existence of a solution is guaranteed by "Parity argument in directed graphs": if there is an unbalanced vertex in a directed graph then there must exist another one. But usually the class is formally defined in terms of the $\mathsf{ANOTHER\ END\ OF\ THE\ LINE}$ ($\mathsf{AEOL}$) problem, where the argument is applied only to graphs with both in- and outdegrees $\le 1$. My question is: why are these notions equivalent? </p>

<p>Up to this point it is a duplicate of <a href="https://cstheory.stackexchange.com/questions/2254/why-are-these-two-definitions-of-ppad-equivalent">this question</a>. Now I want to state the problem formally and to clarify why I am not satisfied with the answer there.</p>

<p>Search problem $\mathsf{ANOTHER\ UNBALANCED\ VERTEX}$ ($\mathsf{AUV}$): we are given two polynomial-sized circuits $S$ and $P$ that get $x\in\{0,1\}^n$ and return a polynomial list of other elements in $\{0,1\}^n$. These circuits define a directed graph $G=(V,E)$ where $V=\{0,1\}^n$ and $(x,y)\in E\Leftrightarrow (y\in S(x)\land x\in P(y))$. The search problem is the following: given $S$, $P$ and $z\in V$ such that $indegree(z)\ne outdegree(z)$, find another vertex with the same property. </p>

<p>Search problem $\mathsf{AEOL}$: the same, but both $S$ and $P$ return either an empty list or one element.</p>

<p>The notion of reducibility (corrected according to Ricky's suggestion): total search problem $A$ is reducible to total search problem $B$ via polynomial functions $f$ and $g$ if $y$ is a solution to $f(x)$ in problem $B$ implies $g(x,y)$ is a solution to $x$ in problem $A$.  </p>

<p><strong>Formal question</strong>: why is $\mathsf{AUV}$ reducible to $\mathsf{AEOL}$? Or should we use another notion of reducibility?</p>

<p>Christos Papadimitriou proves analogous theorem about <strong>PPA</strong> (Theorem 1, page 505) but the argument seems not to work for <strong>PPAD</strong>. The reason is that a vertex with degree balance $\pm k$ will be transformed into $k$ vertices with degree balance $\pm1$. Then the algorithm for $\mathsf{AEOL}$ may get one of these vertices and return another one. This would not yield a new vertex for $\mathsf{AUV}$.</p>

<p>Things are getting worse because in $\mathsf{AEOL}$ there is always an even number of unbalanced vertices but in $\mathsf{AUV}$ there might be an odd number of them. This is why one cannot build a bijection between these two sets and $g$ could not be always equal to $f^{-1}$. If $g(x,f(x))\ne x$ then we obtain a method for solving $\mathsf{AUV}$ in polynomial time at least for some instances. If $g$ does not depend on $x$ and $g(y_1)=g(y_2)$ for $y_1\ne y_2$ then $y_2$ may be returned as an answer for $y_1$. That would not give a solution for $\mathsf{AUV}$.</p>

<p><strong>Final question</strong>: can the obstacles listed above be somehow overcome? Can one employ possible dependence of $g$ on $x$?</p>

CC BY-SA 3.0
2017-02-06T19:07:36.517Z
I think that undirected parity means that every edge contributes 1 to two vertices' degree, and directed parity means that every edge contributes +1 to one vertex balance and -1 to another vertex balance. The construction for PPA works for my definition, and what is the right one? Your last point is indeed very interesting!
Daniil Musatov
CC BY-SA 3.0
2017-02-07T15:25:14.337Z
@Ricky I have changed the definition of reduction but I think that my obstacles persist.
Daniil Musatov
CC BY-SA 3.0
2017-02-08T08:58:33.830Z
At least the reduction shows that AUV is equivalent to its case where all vertices have indegree and outdegree at most 1 except possibly for the given vertex z, which has indegree 0, but may have large outdegree.
Emil Jeřábek
CC BY-SA 3.0
2017-03-21T04:44:27.910Z
Wow, what an observation! It is surprising how errors are discovered after more than 20 years in that paper (see also https://eccc.weizmann.ac.il/report/2015/163). Let me contribute with a Sperner-lemma type complete problem for AUV: Given a triangulated $3k$-gon whose vertices are colored with 3 colors such that the boundary vertices are colored cyclically, find a rainbow triangle. (Here $k$ is part of the input.)
domotorp
CC BY-SA 3.0
2017-03-22T12:45:23.807Z
To be fair, Papadimitriou’s paper does *not* actually claim that AUV is in PPAD (though the vague wording somewhat suggests it). It is, however, claimed (without proof) in the Beame–Cook–Edmonds–Impagliazzo–Pitassi paper.
Emil Jeřábek
CC BY-SA 3.0
2017-03-23T05:32:48.753Z
Yes, it is also claimed in several surveys and lecture notes.
Daniil Musatov
CC BY-SA 3.0
2017-04-10T21:29:04.470Z
I've just heard from Frederic Meunier that he has also observed this problem five years ago and Papadimitriou agreed.
domotorp
<cc.complexity-theory><reductions><search-problem><ppad>
Does PPAD really capture the notion of finding another unbalanced vertex?
Daniil Musatov
# Does PPAD really capture the notion of finding another unbalanced vertex?

(Asked by: username_0 on 2017-02-06)

Complexity class **PPAD** was invented by Christos Papadimitriou in his seminal 1994 [paper](http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf). The class is designed to capture the complexity of search problems where the existence of a solution is guaranteed by "Parity argument in directed graphs": if there is an unbalanced vertex in a directed graph then there must exist another one. But usually the class is formally defined in terms of the $\mathsf{ANOTHER\ END\ OF\ THE\ LINE}$ ($\mathsf{AEOL}$) problem, where the argument is applied only to graphs with both in- and outdegrees $\le 1$. My question is: why are these notions equivalent?

Up to this point it is a duplicate of [this question](https://cstheory.stackexchange.com/questions/2254/why-are-these-two-definitions-of-ppad-equivalent). Now I want to state the problem formally and to clarify why I am not satisfied with the answer there.

Search problem $\mathsf{ANOTHER\ UNBALANCED\ VERTEX}$ ($\mathsf{AUV}$): we are given two polynomial-sized circuits $S$ and $P$ that get $x\in\{0,1\}^n$ and return a polynomial list of other elements in $\{0,1\}^n$. These circuits define a directed graph $G=(V,E)$ where $V=\{0,1\}^n$ and $(x,y)\in E\Leftrightarrow (y\in S(x)\land x\in P(y))$. The search problem is the following: given $S$, $P$ and $z\in V$ such that $indegree(z)\ne outdegree(z)$, find another vertex with the same property.

Search problem $\mathsf{AEOL}$: the same, but both $S$ and $P$ return either an empty list or one element.

The notion of reducibility (corrected according to Ricky's suggestion): total search problem $A$ is reducible to total search problem $B$ via polynomial functions $f$ and $g$ if $y$ is a solution to $f(x)$ in problem $B$ implies $g(x,y)$ is a solution to $x$ in problem $A$.

**Formal question**: why is $\mathsf{AUV}$ reducible to $\mathsf{AEOL}$? Or should we use another notion of reducibility?

Christos Papadimitriou proves analogous theorem about **PPA** (Theorem 1, page 505) but the argument seems not to work for **PPAD**. The reason is that a vertex with degree balance $\pm k$ will be transformed into $k$ vertices with degree balance $\pm1$. Then the algorithm for $\mathsf{AEOL}$ may get one of these vertices and return another one. This would not yield a new vertex for $\mathsf{AUV}$.

Things are getting worse because in $\mathsf{AEOL}$ there is always an even number of unbalanced vertices but in $\mathsf{AUV}$ there might be an odd number of them. This is why one cannot build a bijection between these two sets and $g$ could not be always equal to $f^{-1}$. If $g(x,f(x))\ne x$ then we obtain a method for solving $\mathsf{AUV}$ in polynomial time at least for some instances. If $g$ does not depend on $x$ and $g(y\_1)=g(y\_2)$ for $y\_1\ne y\_2$ then $y\_2$ may be returned as an answer for $y\_1$. That would not give a solution for $\mathsf{AUV}$.

**Final question**: can the obstacles listed above be somehow overcome? Can one employ possible dependence of $g$ on $x$?

**Tags:** cc.complexity-theory, reductions, search-problem, ppad

> **Comments:**
> **username_0**: I think that undirected parity means that every edge contributes 1 to two vertices' degree, and directed parity means that every edge contributes +1 to one vertex balance and -1 to another vertex balance. The construction for PPA works for my definition, and what is the right one? Your last point is indeed very interesting!  
> **username_0**: @Ricky I have changed the definition of reduction but I think that my obstacles persist.  
> **username_1**: At least the reduction shows that AUV is equivalent to its case where all vertices have indegree and outdegree at most 1 except possibly for the given vertex z, which has indegree 0, but may have large outdegree.  
> **username_2**: Wow, what an observation! It is surprising how errors are discovered after more than 20 years in that paper (see also https://eccc.weizmann.ac.il/report/2015/163). Let me contribute with a Sperner-lemma type complete problem for AUV: Given a triangulated $3k$-gon whose vertices are colored with 3 colors such that the boundary vertices are colored cyclically, find a rainbow triangle. (Here $k$ is part of the input.)  
> **username_1**: To be fair, Papadimitriou’s paper does *not* actually claim that AUV is in PPAD (though the vague wording somewhat suggests it). It is, however, claimed (without proof) in the Beame–Cook–Edmonds–Impagliazzo–Pitassi paper.  
> **username_0**: Yes, it is also claimed in several surveys and lecture notes.  
> **username_2**: I've just heard from Frederic Meunier that he has also observed this problem five years ago and Papadimitriou agreed.  

---

## 2 answers

### Answer by username_2 on 2019-02-21. Score: 4 | Accepted answer

The problems have been proved to be equivalent (and thus PPAD-complete), see Section 8 in [The Hairy Ball Problem is PPAD-Complete by Paul W. Goldberg and Alexandros Hollender](https://arxiv.org/abs/1902.07657).

> **Comments:**
> **username_0**: Thanks. It turns out that the proof appeared in an earlier technical report by the same authors: [The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard](http://eccc.weizmann.ac.il/report/2018/120/)  

---

### Answer by username_1 on 2017-02-13. Score: 4

This is an interesting question, and I can only give a partial answer.

It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of **AUV** with its special case

> **MANY ENDS OF THE LINE (MEOL):** Given a directed graph $G$ with in-degree and out-degree at most $1$ (represented by circuits as above), and a nonempty set $X$ of sources of $G$, find a sink or a source $v\notin X$.

On the one hand, I find it hard to imagine a transformation of such graphs that could reduce a larger number of sources to one.

However, on the other hand, **MEOL** belongs to all commonly studied classes containing **PPAD** except possibly **PPAD** itself:

First, obviously,

> **MEOL** is in **PPADS**.

I will sketch below an argument that

> **MEOL** is in **PPA**

by reduction to the standard **PPA**-complete problem (the undirected version of **AEOL**). Assume we are given $G=(V,E)$ and $X$ as in the definition of MEOL.

If $|X|$ is odd, we can just make the graph undirected, include a matching on all but one vertex from $X$ (as in the argument on p. 505), and pass the result along with the remaining source from $X$ to the **PPA** oracle.

In general, let $s=|X|$, and $2^k$ be the largest power of $2$ that divides $s$. We define a new graph $G'=(V',E')$ whose vertices are $2^k$-element subsets of $V$. If $A,B\in V'$ are such sets, we put the edge $(A,B)$ in $E'$ if we can enumerate the sets as $A=\{a\_0,\dots,a\_{2^k-1}\}$, $B=\{b\_0,\dots,b\_{2^k-1}\}$ in such a way that $(a\_i,b\_i)\in E$ for each $i<2^k$.

Clearly, $G'$ is a directed graph with in-degree and out-degree at most $1$. An $A\in V'$ is a source (sink) iff it contains a source (sink, resp.) of $G$. (That is, if it contains both, it is an isolated vertex.) So, any such vertex would lead to a solution of the **MEOL** instance, unless $A$ is a “known source”: that is, $A\cap X\ne\varnothing$. We intend to make the graph undirected, and manipulate it so that the number of known sources is reduced to $1$ by including a matching on the remaining ones.

So, if $A$ is a known source, let $t=|A\cap X|$, which satisfies $0

For $0

In this way, we produce an undirected graph with one known leaf vertex. We ask the **PPA** oracle for another leaf, and by construction, we can extract from it an answer for the **MEOL** instance.

---

As briefly mentioned by Papadimitriou, we can generalize **PPA** to classes **PPA**-$p$ for any prime $p$. An example of a **PPA**-$p$ complete problem is

> **AUV**-$p$: Given a directed graph $G$, and a vertex whose degree balance is ${}\not\equiv0\pmod p$, find another such vertex.

(See [this answer](https://cstheory.stackexchange.com/a/37794) for the equivalence of **AUV**-$p$ with Papadimitriou’s definition of **PPA**-$p$.)

**PPA**-$2$ is just **PPA**. The classes **PPA**-$p$ are assumed to be pairwise incomparable, and incomparable with **PPADS**. They all include **PPAD**.

There was nothing particularly special about $p=2$ in the argument I outlined above, and it can be easily modified to yield

> **MEOL** is in **PPA**-$p$ for every prime $p$.

> **Comments:**
> **username_0**: I like the answer very much and have decided accept it (of course, more complete answers are still welcomed). I only think that the class represented by **AUV**-$p$ should be called **PPAD**-$p$. Papadimitriou writes about undirected bipartite graphs and just degrees, not balances.  
> **username_1**: The classes are generalizations of PPA, not PPAD, for $p=2$. Papadimitriou gives a different complete problem than AUV-$p$ (note that his graphs are bipartite), but it is equivalent to my definition. The whole naming scheme is terribly confusing; the usage of directed vs. undirected graphs for a particular class is just an accident, many of the classes have complete problems concerning both directed and undirected graphs (as in the case of PPA-$p$).  Also, despite their names, most of the classes are *not* based on parity arguments, but other counting principles. Only PPA is about parity.  
> **username_0**: Thanks, got it. It is indeed the same class. I have heard a speculation that Papadimitriou has chosen the name PPAD because it resembles his own surname.  
> **username_2**: Do you have a reference for PPAD being in PPA-p?  
> **username_1**: Not an explicit one, but for instance, the defining PPAD-complete problem is literally a special case of AUV-$p$.  

---

