<p>Edit 2: Embarrassingly, there is a two line proof of the <span class="math-container">$NP$</span>-hardness, if one starts with the right polytope.</p>

<p>First, recall the circulation polytope of a graph on the bottom of page 4 of <a href="http://dimacs.rutgers.edu/archive/TechnicalReports/TechReports/2005/2005-21.pdf" rel="nofollow noreferrer">Generating all vertices of a polyhedron is hard</a>.</p>

<p>It's vertices are in bijective correspondence with the directed simple cycles. Therefore, they are hard to sample or count by <a href="http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/ConvergeRates/RandomizedAlgs/JerrumValiantVaziraniTCS1986.pdf" rel="nofollow noreferrer">JVV Proposition 5.1</a>. :-D</p>

<p>Equipped with these keywords, I was able to find the hardness of sampling result as theorem 1 of <a href="https://link.springer.com/chapter/10.1007/978-1-4613-0279-7_5" rel="nofollow noreferrer">Transversal Hypergraphs and Families of Polyhedral Cones</a> by Khachiyan.</p>

<hr>

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

<p>a) By <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.579.9132&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Analysis of backtrack algorithms for listing all vertices and all faces
of a convex polyhedron</a> (Fukuda et al.) it is strongly NP-hard to solve the following problem on polytopes:</p>

<p>Input: A polytope <span class="math-container">$Ax = b , x \geq 0$</span> in <span class="math-container">$\mathbb{R}^n$</span> a subset <span class="math-container">$S \subseteq n$</span></p>

<p>Output: Whether there is a vertex <span class="math-container">$v$</span> of <span class="math-container">$P$</span> that is nonzero on each of the coordinates in <span class="math-container">$S$</span>.</p>

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

<p>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 <span class="math-container">$2^{d | supp(x) \cap S|}$</span>, where <span class="math-container">$supp$</span> is the function that sends a vertex to the coordinates where it is nonzero.</p>

<p>d) By a usual chain of bigons type argument it follows that by taking <span class="math-container">$d$</span> sufficiently large, a uniform sample from the vertices of <span class="math-container">$P_{S,d}$</span> would (with high probability) give a sample from the vertices maximizing the size of their intersection with <span class="math-container">$S$</span>.</p>

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

<hr>

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

CC BY-SA 4.0
2019-04-22T14:06:39.707Z
This is a very interesting argument! I didn't fully check all details in part 3) (what are the functions $H_1$, $H_0$, $leaves$?), but in principle, any non-spanning structure can only incur a super exponential blowup, which thus can be controlled by taking $d$ polynomial large.
Heng Guo
CC BY-SA 4.0
2019-04-22T16:20:06.960Z
@HengGuo Thanks for reading! By $|H_0|$ I mean the number of components, and $|H_1|$ the dimension of the cycle space (circuit rank), and "leaves" the number of degree 1 vertices. I'll add those definitions.
Elle Najt
CC BY-SA 4.0
2019-04-25T11:13:26.040Z
There must be something wrong with this. If there is a polytope whose vertices are lassos and simple cycles, can't we use linear programming to maximize any linear function we want over this polytope? And wouldn't that let us find a spanning lasso in polynomial time?
Peter Shor 
CC BY-SA 4.0
2019-04-25T17:12:53.953Z
@PeterShor I think this doesn't happen because the polytope lives inside the hyperplane defined by setting the sum of the edge variables to one. So that functional is constant over the polytope. The function that represents the number of edges is the size of the support of the vector, which is non linear on this polytope.
Elle Najt
CC BY-SA 4.0
2019-04-25T22:54:53.133Z
@PeterShor I added a proof that the 'number of edges' function cannot be linear, see the picture at the bottom.
Elle Najt
CC BY-SA 4.0
2019-04-19T21:26:55.560Z
2019-11-13T00:13:37.523Z
2019-11-13T00:13:37.523Z
Elle Najt
<p>I have a polytope <span class="math-container">$P$</span> defined by <span class="math-container">$\{ x : Ax \leq b, x \geq 0\}$</span> .</p>

<p><strong>Question:</strong> Given a vertex <span class="math-container">$v$</span> of <span class="math-container">$P$</span>, is there a polynomial time algorithm to uniformly sample from the neighbors of <span class="math-container">$v$</span> in the graph of <span class="math-container">$P$</span>? 
(Polynomial in the dimension, the number of equations, and the representation of <span class="math-container">$b$</span>. I can assume that the number of equations is polynomial in the dimension.)</p>

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

<p><strong>Update 2:</strong> There is a 2 line proof of <span class="math-container">$NP$</span>-hardness (given the right combinatorial polytope) and I was able to find it an article by Khachiyan. See answer for description and link. :-D </p>

<hr>

<p><em>An equivalent problem</em>:</p>

<p>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 <span class="math-container">$P$</span> with a vertex <span class="math-container">$v$</span> to the vertex figure at <span class="math-container">$v$</span>, <span class="math-container">$P/v$</span>, and sampling the vertices of <span class="math-container">$P/v$</span> is equivalent to sampling the neighbors of <span class="math-container">$v$</span> on <span class="math-container">$P$</span>. In the other direction, we can go from a polytope <span class="math-container">$P$</span> to a polytope <span class="math-container">$Q$</span> of one higher dimension by adding a cone with apex <span class="math-container">$v$</span> and base <span class="math-container">$P$</span>. Then sampling the neighbors of <span class="math-container">$v$</span> in <span class="math-container">$Q$</span> is equivalent to sampling the vertices of <span class="math-container">$P$</span>.)</p>

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

<hr>

CC BY-SA 4.0
2019-04-12T05:22:00.160Z
I don't know the answer to your question, but to my knowledge, there is no known NP-hardness to uniformly sample a vertex of a polytope given explicitly. For example, approximately sampling cycles is NP-hard. However, if there were some linear program whose vertices encode cycles, then very likely you can optimize the length of the cycle, and thus solve Hamiltonian-Cycle.
Heng Guo
CC BY-SA 4.0
2019-04-12T05:27:13.210Z
Another remark is that even if your question has a positive answer, it does not yield a uniform sampler for the vertices (assuming the 0-1 polytope conjecture). The skeleton of the polytope in most interesting cases is not regular, and the degrees can vary exponentially.
Heng Guo
CC BY-SA 4.0
2019-04-12T05:39:21.643Z
@HengGuo Thanks for the comments again, they're very helpful. Do you happen to know a good example where the degrees vary exponentially? (I'm not surprised that this can happen for general polytopes; it would be nice to have a combinatorial example if know of one off the top of your head.)
Elle Najt
CC BY-SA 4.0
2019-04-12T05:54:26.017Z
Consider the independent set polytope of a bipartite graph. Two vertices (two independent sets) are connected if their symmetric difference induces a connected subgraph. Now, take a bipartite graph whose one side has only two vertices, $v_1$ connects to every vertex on the other side and $v_2$ only one. Consider independent sets $\{v_1\}$ and $\{v_2\}$.
Heng Guo
CC BY-SA 4.0
2019-04-13T14:34:08.097Z
Uniformly sampling the neighboring vertices of a given vertex of a polytope is the same problem as sampling a random vertex of a polytope uniformly. Chop off a cone infinitesimally close to the vertex. One then has a new polytope, and if you can sample a vertex of this new polytope, one can sample a neighboring vertex of the original polytope. I would guess doing this approximately is in BPP, but I can't find any paper that proves this.
Peter Shor 
CC BY-SA 4.0
2019-04-15T21:08:44.650Z
I may be confused about the question. If we are given $v$ and the polytope constraints explicitly, can't we simply compute all the neighbors of $v$ explicitly in polynomial time?
Chandra Chekuri
CC BY-SA 4.0
2019-04-16T00:47:08.217Z
@Chandra: there may be exponentially many neighbors of $v$, if the polytope constraints are not in generic positions.
Peter Shor 
CC BY-SA 4.0
2019-04-17T21:31:04.867Z
@ChandraChekuri For an explicit example, you can take { 0 <= x <= 1 - z, 0 <= z <= 1}, where x is in R^n, and z is a scalar. This is a hypercube that has been extended with a cone pointing in the z direction. The cone point v = (0,...,0,1) has 2^n neighbors - the vertex figure at v is the n dimensional hypercube, and the vertices of the vertex figure correspond bijectively to edges of v. You can construct a cone over any polytope in a similar way.
Elle Najt
CC BY-SA 4.0
2019-04-19T21:35:56.627Z
@HengGuo I think I was able to show that this uniform sampling problem is NP-hard. If you are interested and have the time, I would really appreciate it if you took a look at my answer below and let me know if anything is unclear.
Elle Najt
CC BY-SA 4.0
2019-11-13T15:32:01.907Z
@PeterShor Your argument makes it clear that sampling arbitrary vertices allows sampling neighbors, but I don't understand why the reverse is true. All that's obvious to me is that it sampling neighbors yields a uniform random walk on vertices. Can you elaborate on why the neighbor and arbitrary vertex sampling problems are actually the same?
S Huntsman
CC BY-SA 4.0
2019-11-13T15:48:20.680Z
@S Huntsman: Suppose you have a polytope in dimension $n$. If you chop off a vertex with a hyperplane that passes through all the edges adjacent to that vertex, you get a new polytope in dimension $n$. The face opposite the vertex is a polytope in dimension $n-1$. Sampling a random vertex from that face is equivalent to sampling a random neighbor of that vertex. And you can arrange the points so that face is isomorphic to an arbitrary polytope in dimension $n-1$.
Peter Shor 
<reference-request><np-hardness><counting-complexity><linear-programming><polytope>
Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?
Elle Najt
# Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

(Asked by: username_0 on 2019-04-12)

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>

---

**Tags:** reference-request, np-hardness, counting-complexity, linear-programming, polytope
> **Comments:**
> **username_1**: I don't know the answer to your question, but to my knowledge, there is no known NP-hardness to uniformly sample a vertex of a polytope given explicitly. For example, approximately sampling cycles is NP-hard. However, if there were some linear program whose vertices encode cycles, then very likely you can optimize the length of the cycle, and thus solve Hamiltonian-Cycle.  
> **username_1**: Another remark is that even if your question has a positive answer, it does not yield a uniform sampler for the vertices (assuming the 0-1 polytope conjecture). The skeleton of the polytope in most interesting cases is not regular, and the degrees can vary exponentially.  
> **username_0**: @HengGuo Thanks for the comments again, they're very helpful. Do you happen to know a good example where the degrees vary exponentially? (I'm not surprised that this can happen for general polytopes; it would be nice to have a combinatorial example if know of one off the top of your head.)  
> **username_1**: Consider the independent set polytope of a bipartite graph. Two vertices (two independent sets) are connected if their symmetric difference induces a connected subgraph. Now, take a bipartite graph whose one side has only two vertices, $v_1$ connects to every vertex on the other side and $v_2$ only one. Consider independent sets $\{v_1\}$ and $\{v_2\}$.  
> **username_2**: Uniformly sampling the neighboring vertices of a given vertex of a polytope is the same problem as sampling a random vertex of a polytope uniformly. Chop off a cone infinitesimally close to the vertex. One then has a new polytope, and if you can sample a vertex of this new polytope, one can sample a neighboring vertex of the original polytope. I would guess doing this approximately is in BPP, but I can't find any paper that proves this.  
> **username_3**: I may be confused about the question. If we are given $v$ and the polytope constraints explicitly, can't we simply compute all the neighbors of $v$ explicitly in polynomial time?  
> **username_2**: @Chandra: there may be exponentially many neighbors of $v$, if the polytope constraints are not in generic positions.  
> **username_0**: @ChandraChekuri For an explicit example, you can take { 0 <= x <= 1 - z, 0 <= z <= 1}, where x is in R^n, and z is a scalar. This is a hypercube that has been extended with a cone pointing in the z direction. The cone point v = (0,...,0,1) has 2^n neighbors - the vertex figure at v is the n dimensional hypercube, and the vertices of the vertex figure correspond bijectively to edges of v. You can construct a cone over any polytope in a similar way.  
> **username_0**: @HengGuo I think I was able to show that this uniform sampling problem is NP-hard. If you are interested and have the time, I would really appreciate it if you took a look at my answer below and let me know if anything is unclear.  
> **username_4**: @PeterShor Your argument makes it clear that sampling arbitrary vertices allows sampling neighbors, but I don't understand why the reverse is true. All that's obvious to me is that it sampling neighbors yields a uniform random walk on vertices. Can you elaborate on why the neighbor and arbitrary vertex sampling problems are actually the same?  
> **username_2**: @S Huntsman: Suppose you have a polytope in dimension $n$. If you chop off a vertex with a hyperplane that passes through all the edges adjacent to that vertex, you get a new polytope in dimension $n$. The face opposite the vertex is a polytope in dimension $n-1$. Sampling a random vertex from that face is equivalent to sampling a random neighbor of that vertex. And you can arrange the points so that face is isomorphic to an arbitrary polytope in dimension $n-1$.  

---

## 1 answers

### Answer by username_0 on 2019-04-19. Score: 4 | Accepted answer

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](http://dimacs.rutgers.edu/archive/TechnicalReports/TechReports/2005/2005-21.pdf).

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](http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/ConvergeRates/RandomizedAlgs/JerrumValiantVaziraniTCS1986.pdf). :-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](https://link.springer.com/chapter/10.1007/978-1-4613-0279-7_5) 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.579.9132&rep=rep1&type=pdf) (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.)

> **Comments:**
> **username_1**: This is a very interesting argument! I didn't fully check all details in part 3) (what are the functions $H_1$, $H_0$, $leaves$?), but in principle, any non-spanning structure can only incur a super exponential blowup, which thus can be controlled by taking $d$ polynomial large.  
> **username_0**: @HengGuo Thanks for reading! By $|H_0|$ I mean the number of components, and $|H_1|$ the dimension of the cycle space (circuit rank), and "leaves" the number of degree 1 vertices. I'll add those definitions.  
> **username_2**: There must be something wrong with this. If there is a polytope whose vertices are lassos and simple cycles, can't we use linear programming to maximize any linear function we want over this polytope? And wouldn't that let us find a spanning lasso in polynomial time?  
> **username_0**: @PeterShor I think this doesn't happen because the polytope lives inside the hyperplane defined by setting the sum of the edge variables to one. So that functional is constant over the polytope. The function that represents the number of edges is the size of the support of the vector, which is non linear on this polytope.  
> **username_0**: @PeterShor I added a proof that the 'number of edges' function cannot be linear, see the picture at the bottom.  

---

