Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

Question

I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ .

Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph of $P$? (Polynomial in the dimension, the number of equations, and the representation of $b$. I can assume that the number of equations is polynomial in the dimension.)

Update: I think I was able to show that this is NP-hard, see my answer that explains the argument. (And by $NP$-hard, I mean that an polynomial time algorithm would prove $RP = NP$... not sure what the correct terminology is here.)

Update 2: There is a 2 line proof of $NP$-hardness (given the right combinatorial polytope) and I was able to find it an article by Khachiyan. See answer for description and link. :-D

---

An equivalent problem:

In the comments Peter Shor pointed out that that this question is equivalent to the question of whether we can uniformly sample from the vertices of a given polytope. (I think the equivalence goes like this: In one direction, we can go from a polytope $P$ with a vertex $v$ to the vertex figure at $v$, $P/v$, and sampling the vertices of $P/v$ is equivalent to sampling the neighbors of $v$ on $P$. In the other direction, we can go from a polytope $P$ to a polytope $Q$ of one higher dimension by adding a cone with apex $v$ and base $P$. Then sampling the neighbors of $v$ in $Q$ is equivalent to sampling the vertices of $P$.)

This formulation of the question has been asked before: https://mathoverflow.net/questions/319930/sampling-uniformly-from-the-vertices-of-a-polytope

---

Answer 1

Edit 2: Embarrassingly, there is a two line proof of the $NP$-hardness, if one starts with the right polytope.

First, recall the circulation polytope of a graph on the bottom of page 4 of Generating all vertices of a polyhedron is hard.

It's vertices are in bijective correspondence with the directed simple cycles. Therefore, they are hard to sample or count by JVV Proposition 5.1. :-D

Equipped with these keywords, I was able to find the hardness of sampling result as theorem 1 of Transversal Hypergraphs and Families of Polyhedral Cones by Khachiyan.

---

Edit: I wrote up the argument below, and it appears correct. However, there is a much simpler argument, which I'll outline here:

a) By Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron (Fukuda et al.) it is strongly NP-hard to solve the following problem on polytopes:

Input: A polytope $Ax = b , x \geq 0$ in $\mathbb{R}^n$ a subset $S \subseteq n$

Output: Whether there is a vertex $v$ of $P$ that is nonzero on each of the coordinates in $S$.

b) Given this, one can make the following construction: introduce new variables $y_{ik}$ for $i \in S$ and $k = 1, \ldots, d$, and introduce the inequality $0 \leq y_{ik} \leq x_i$. Call the resulting polytope $P_{S,d}$. The point of this construction is to introduce a hypercube above each vertex, of dimension $d |supp(x) \cap S|$.

c) One can check that the vertices of this polytope all lie above the vertices of the old polytope, and that the number of vertices over a vertex is $2^{d | supp(x) \cap S|}$, where $supp$ is the function that sends a vertex to the coordinates where it is nonzero.

d) By a usual chain of bigons type argument it follows that by taking $d$ sufficiently large, a uniform sample from the vertices of $P_{S,d}$ would (with high probability) give a sample from the vertices maximizing the size of their intersection with $S$.

There appear to be various extensions of this. I will update with a link when the writing is done.

---

(The old argument used to be here -- it is in the edit history. I've removed it because it's very long and will interfere with finding the correct answer to the question.)