Does PPAD really capture the notion of finding another unbalanced vertex?

Question

Complexity class PPAD was invented by Christos Papadimitriou in his seminal 1994 paper. 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. 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$?

Answer 1

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.

Answer 2

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<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$.

For $0<t<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.

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 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$.