12
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ "why are these notions equivalent?" ​ For the reasons given in the proof of Theorem 1 on page 505 by Christos Papadimitriou. ​ (Otherwise, what do you think is a parity argument for the totality of AUV?) ​ Your definition of reducibility seems too strong - For example, under your definition, expanding the set of solutions can make a total search problem strictly harder. ​ ​ ​ ​ $\endgroup$ – user6973 Feb 6 '17 at 18:21
  • 2
    $\begingroup$ +1 and -1 have the same parity. ​ (That parity is "odd".) $\hspace{3.09 in}$ The right one has "implies $g(x,\hspace{-0.03 in}y)$" instead of "iff $g(\hspace{.04 in}y)$". ​ ​ $\endgroup$ – user6973 Feb 7 '17 at 9:33
  • 2
    $\begingroup$ Now, what we do have is that, I'll call it UnbalancedInOtherDirectionVertex, that problem reduces to PPADS, since one can flip the edges if necessary to make the given vertex have greater out-degree than in-degree, and then the $k$ total-degree-1 vertices the given vertex gets transformed into will all be sources rather than sinks. ​ I don't see any similar way of going from your problem to AEOL. ​ ​ ​ ​ $\endgroup$ – user6973 Feb 7 '17 at 15:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 8 '17 at 8:58
  • 2
    $\begingroup$ I've just heard from Frederic Meunier that he has also observed this problem five years ago and Papadimitriou agreed. $\endgroup$ – domotorp Apr 10 '17 at 21:29
3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniil Musatov Feb 15 '17 at 9:03
  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 15 '17 at 9:38
  • $\begingroup$ 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. $\endgroup$ – Daniil Musatov Feb 16 '17 at 11:51
  • $\begingroup$ Do you have a reference for PPAD being in PPA-p? $\endgroup$ – domotorp Feb 28 '18 at 14:04
  • 1
    $\begingroup$ Not an explicit one, but for instance, the defining PPAD-complete problem is literally a special case of AUV-$p$. $\endgroup$ – Emil Jeřábek Feb 28 '18 at 15:25

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.