15

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

Elle Najt
  • 1,439
  • 8
  • 19
  • 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 Apr 12 '19 at 05:22
  • 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 Apr 12 '19 at 05:27
  • @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 Apr 12 '19 at 05:39
  • 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 Apr 12 '19 at 05:54
  • 5
    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 Apr 13 '19 at 14:34
  • 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 Apr 15 '19 at 21:08
  • @Chandra: there may be exponentially many neighbors of $v$, if the polytope constraints are not in generic positions. – Peter Shor Apr 16 '19 at 00:47
  • @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 Apr 17 '19 at 21:31
  • @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 Apr 19 '19 at 21:35
  • @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 Nov 13 '19 at 15:32
  • @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 Nov 13 '19 at 15:48

1 Answers1

4

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.)

Elle Najt
  • 1,439
  • 8
  • 19
  • 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 Apr 22 '19 at 14:06
  • @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 Apr 22 '19 at 16:20
  • 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 Apr 25 '19 at 11:13
  • @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 Apr 25 '19 at 17:12
  • @PeterShor I added a proof that the 'number of edges' function cannot be linear, see the picture at the bottom. – Elle Najt Apr 25 '19 at 22:54