Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?
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.)