15
$\begingroup$

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


$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Heng Guo Apr 12 at 5:22
  • $\begingroup$ 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. $\endgroup$ – Heng Guo Apr 12 at 5:27
  • $\begingroup$ @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.) $\endgroup$ – Lorenzo Najt Apr 12 at 5:39
  • $\begingroup$ 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\}$. $\endgroup$ – Heng Guo Apr 12 at 5:54
  • 5
    $\begingroup$ 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. $\endgroup$ – Peter Shor Apr 13 at 14:34
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Heng Guo Apr 22 at 14:06
  • $\begingroup$ @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. $\endgroup$ – Lorenzo Najt Apr 22 at 16:20
  • $\begingroup$ 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? $\endgroup$ – Peter Shor Apr 25 at 11:13
  • $\begingroup$ @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. $\endgroup$ – Lorenzo Najt Apr 25 at 17:12
  • $\begingroup$ @PeterShor I added a proof that the 'number of edges' function cannot be linear, see the picture at the bottom. $\endgroup$ – Lorenzo Najt Apr 25 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.