6
$\begingroup$

Consider the following problem from TFNP that is somewhere between End-of-the-Line (PPAD) and End-of-Metered-Line (CLS).

Input (via polynomial circuit): Graph on vertex set $0$ to $2^n-1$ such that querying any vertex returns its neighbors (at most two), and $deg(0)=1$.

Output: Either a $v\ne 0$ for which $deg(v)=1$, OR {four vertices, $a<b<c<d$, such that $ac$ and $bd$ are edges OR $ad$ and $bc$ are edges} OR {three vertices, $a<b<c$, such that $ab$ and $ac$ are edges} OR {three vertices, $a<b<c$, such that $ac$ and $bc$ are edges}. (So this practically says that the graph when drawn naturally behaves like a 'graph of a function', i.e., it intersects every vertical line at most once.)

How hard is this problem?

$\endgroup$
  • $\begingroup$ It would help me out, for one, to make the question more precise. Directed graph? If so, does "neighbors" include in-edges or only out edges, i.e. can there be any number of in-edges? Can you maybe explain what you mean by "drawn naturally"? Finally, it would be a nice bonus to include a proof of existence of solution. $\endgroup$ – usul Apr 2 '18 at 22:51
  • $\begingroup$ @usul The graph is undirected (although the problem could be equivalently formulated by directing all edges left-to-right). By natural, I mean that $v$ is mapped to $(v,0)$ and the edge $uv$ to a semicircle connecting $(u,0)$ and $(v,0)$ in the $y>0$ halfplane. The proof of existence of a solution follows from that my problem is a subclass of PPA, about which (and other background) you can read here: en.wikipedia.org/wiki/PPA_(complexity) $\endgroup$ – domotorp Apr 3 '18 at 8:19
  • 1
    $\begingroup$ The "graph of function" parenthesis seems wrong: the conditions do not exclude 3-cycles. $\endgroup$ – Emil Jeřábek Apr 3 '18 at 8:48
7
$\begingroup$

Your problem is equivalent to End-of-Metered-Line.

This can be shown by reducing your problem to End-of-Potential-Line (see https://arxiv.org/abs/1702.06017). This is a version of End-of-the-Line where the line is equipped with a potential function, and a solution is either the end of a line, or a vertex on the line at which the potential function decreases. This differs from EOML, since the potential is not required to increase by exactly one at each vertex.

We can reduce your problem to EOPL by taking the successor of each vertex to be the neighbor with the larger index, and the predecessor of each vertex to be the neighbor with the smaller index. Any vertex that has two neighbors with smaller indices is the end of a line, and any vertex that has two larger neighbors is also the end of a line. The potential function of a vertex is just its index, which is monotonically increasing along each line.

It was shown in https://arxiv.org/abs/1702.06017 that EOPL is equivalent to EOML, under polynomial-time reductions, and thus is in CLS.

For the other direction, EOML can be reduced to your problem by embedding the potential space into the vertex space using the higher-order bits. In other words, each vertex $v$ in the EOML instance is mapped to the integer $K \cdot p(v) + v$, where $p(v)$ is the potential of $v$, and $K$ is some constant that is larger than the total number of vertices in the EOML instance.

So to answer your question, the problem is unlikely to be PPAD-complete since that would imply PPAD $\subseteq$ CLS.

$\endgroup$
  • $\begingroup$ Wow, I find it quite surprising that this problem seemingly without any potential turned out to be CLS-complete. $\endgroup$ – domotorp Apr 4 '18 at 20:43
  • 2
    $\begingroup$ @domotorp: actually EOML and EOPL are not known to be CLS-hard, though we do conjecture that that is rather plausible. We'll be posting a new version of our paper soon with some more results. $\endgroup$ – Rahul Savani Apr 4 '18 at 20:58

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.