<p>Your problem is equivalent to End-of-Metered-Line. </p>

<p>This can be shown by reducing your problem to End-of-Potential-Line (see <a href="https://arxiv.org/abs/1702.06017" rel="noreferrer">https://arxiv.org/abs/1702.06017</a>). 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.</p>

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

<p>It was shown in <a href="https://arxiv.org/abs/1702.06017" rel="noreferrer">https://arxiv.org/abs/1702.06017</a> that EOPL is equivalent to EOML, under polynomial-time reductions, and thus is in CLS. </p>

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

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

CC BY-SA 3.0
2018-04-04T20:43:18.150Z
Wow, I find it quite surprising that this problem seemingly without any potential turned out to be CLS-complete.
domotorp
CC BY-SA 3.0
2018-04-04T20:58:26.533Z
@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.
Rahul Savani
CC BY-SA 3.0
2018-04-04T11:23:51.693Z
2018-04-04T11:55:53.743Z
2018-04-04T11:55:53.743Z
jfearnley
<p>Consider the following problem from TFNP that is somewhere between End-of-the-Line (PPAD) and End-of-Metered-Line (CLS).</p>

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

<p>Output: Either a $v\ne 0$ for which $deg(v)=1$, OR {four vertices, $a&lt;b&lt;c&lt;d$, such that $ac$ and $bd$ are edges OR $ad$ and $bc$ are edges} OR {three vertices, $a&lt;b&lt;c$, such that $ab$ and $ac$ are edges} OR {three vertices, $a&lt;b&lt;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.)</p>

<p>How hard is this problem?</p>

CC BY-SA 3.0
2018-04-02T22:51:26.743Z
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.
usul
CC BY-SA 3.0
2018-04-03T08:19:30.543Z
@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: https://en.wikipedia.org/wiki/PPA_(complexity)
domotorp
CC BY-SA 3.0
2018-04-03T08:48:33.320Z
The "graph of function" parenthesis seems wrong: the conditions do not exclude 3-cycles.
Emil Jeřábek
<cc.complexity-theory><ppad>
Is End-of-Monotone-Line PPAD-complete?
domotorp
# Is End-of-Monotone-Line PPAD-complete?

(Asked by: username_0 on 2018-04-01)

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

How hard is this problem?

**Tags:** cc.complexity-theory, ppad
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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: https://en.wikipedia.org/wiki/PPA_(complexity)  
> **username_2**: The "graph of function" parenthesis seems wrong: the conditions do not exclude 3-cycles.  

---

## 1 answers

### Answer by username_3 on 2018-04-04. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: Wow, I find it quite surprising that this problem seemingly without any potential turned out to be CLS-complete.  
> **username_4**: @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.  

---

