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

My notes:

My feeling is that this sampling problem might be NP-hard, possibly by finding some polynomial size representation of the convex hull of the indicators of some set of objects that are hard to approximately uniformly sample, and then appealing to some known case of the Mihail-Vazirani conjecture on $0/1$ polytopes. (As Heng Guo points out below, this strategy is unlikely to be successful, because if we can describe the polytope (polynomially) we can optimize over it, and even then the degrees of the vertices can vary exponentially. Another strategy for hardness might be to engineer a polytope such that the neighbors of a vertex give a hard uniform sampling problem.)

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

I've started to feel that the problem of uniformly sampling from the vertices of a polytope is equivalent to approximately computing the vertex centroid (the average of all vertices).

(I will give a reference that it is hard to approximate the vertex centroid below. I misunderstood, the reference only proves this for unbounded polyhedra.)

If we could sample the vertices, then we could estimate the vertex centroid by averaging them. (I'm happy to assume that all the points are in $[0,1]^n$, so the empirical means concentrate rapidly by Hoeffding's.)

Via the trick in Theorem 1 from https://arxiv.org/pdf/0806.3456.pdf , one can turn an approximation for the vertex centroid into an approximation for the number of vertices. (I think that approximation needs to be extremely good to avoid blow-up in error, so this may not give a reduction.)

Is it known to be $\# P$ hard to approximate the vertices of a polytope?

This paper (from 2016) says:

To the best of our knowledge, the problem of estimating the number of vertices of a convex polytope does not have a FPRAS. That is, for this particular problem, an efficient randomized approximation algorithm is not known to exist.

In the other direction, here are a few ideas for going from the vertex centroid to sampling. None of these work efficiently in generality.

  1. Picking a good distribution over functionals:

This doesn't appear to generalize past the simplest cases, but maybe there is a way to save it.

For every polytope, define a point in it called the 'magic'-centroid.

Algorithm: Translate the polytope so the 'magic'-centroid is at the origin. Pick an approximately uniform point $p$ from the (translated polytope). Output the maximizer to $f_p(x) = p \cdot x$.

Call a point a magic centroid if this algorithm outputs an approximately uniform distribution over the vertices.

For simple shapes (e..g line segments, rectangles, anything with vertex transitive symmetry group...) the vertex centroid is a magic centroid. This doesn't appear to generalize past these simple cases -- irregular 2D polygons already provide examples where the vertex centroid isn't a magic centroid (and neither is the center of gravity). In fact, I think many irregular 2D polygons provide examples where there cannot be a magic centroid.

  1. If you can approximate the vertex centroid, you can use the trick in Theorem 1 of https://arxiv.org/pdf/0806.3456.pdf to approximate the number of vertices in the polytope, and then use the algorithm described here: https://pdfs.semanticscholar.org/3fff/d6a1f29e668448901ef07313f7a65495395a.pdf

On the other hand, in that article Pak writes:

Note that when faster approximation algorithms are available, one can use them in place of a counting oracle everywhere when determining which hyperplane to use. But the probabilities must be determined by the precise counting oracle since the errors will blow up otherwise.

I think his point is that while there only $d$ iterations, so the blow up in error per element is like $(1 - \epsilon)^d$, since there exponentially many elements, $\epsilon$ needs to be exponentially small in order to sample from an approximately uniform distribution.

  1. For polytopes defined as the convex hull of indicators of some collection $\mathscr{S}(E)$ of subsets of a set $E$, the vertex-centroid records the marginals: for a given $e \in E$, the probability that a uniformly chosen element of $\mathscr{S}(E)$ contains $e$. For a self-reducible structure $S$, describing the collection $\mathscr{S}$ over all input, this is enough to sample uniformly from $\mathscr{S}(E)$.

So, if you could prove that you could always compute the vertex centroid (for the class of polytopes arising from the problem $S$), then you could uniformly sample the vertexes.

I think any errors also blow up here the way they would for using an approximate count of $\mathscr{S}(E)$ in Pak's article.

  1. I also thought a bit about sampling random basis of the matrix $A$ (assuming the polytope is in equational form $Ax = b$, $x \geq 0$), using the basis exchange Markov chain (which is known to mix rapidly). This has two problems that make it unusable in many situations: 1) The probability that a basis gives a basic feasible solution is potentially extremely low 2) Basic feasible solutions (especially those with many zeros) correspond to lots of basis.

However for non-degenerate polytopes the second problem goes away, and I have some numerical evidence that 1) isn't always as big a problem as it could for some distributions over polytopes ... for random (say, absolute value of Gaussian) entries, this would amount to estimating the number vertices in a random polytope of the form $Ax = b$, $x \geq 0$ (since every set of columns of the right size is a basis). For the models I coded on my computer, this acceptance rate decays with the dimension, of course, but (for some models) not nearly as rapidly as one might expect...

(Most polytopes were it would be interesting to sample the vertices are highly degenerate, however...)

Notes on computational complexity of computing centroids:

There appear to be at least two kinds of centroid in higher dimensions: the center of gravity, and the vertex-centroid (which is the average of the vertices).

Exact computation of the center of gravity is $\sharp P$ hard (see this paper) , but it can be efficiently approximated because points in the polytope can be approximately sampled.

On the other hand, even approximating the vertex-centroid of a polyhedron is already hard -- see this paper.

The hardness of approximating the vertex-centroid may give an answer to this question - if you can uniformly sample the vertices then you can presumably approximate the centroid. However, the authors of that paper only prove their result for unbounded polyhedrons, and it's unclear if it extends to polytopes.

Even though we do not have any idea about the complexity of approximating the centroid of a polytope, now we show that for an arbitrary unbounded polyhedron the vertex centroid can not approximated ... unless P = NP.

On the other hand, *this appears to answer this question for general polyhedra, with some bound on the location of the vertices: it's $NP$ hard to approximately uniformly sample from the vertices of a polyhedra -- provided the vertices are bounded appropriately, so you can guarantee that the averages concentrate rapidly enough. (I not 100 percent sure about this - will have to go and understand their paper.)

  • $\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

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.

Old argument:

I believe it's NP-hard in general to $\epsilon$-almost uniformly sample the vertices of a given polytope given by inequalities in time polynomial in the description of the inequalities. As is explained in the body of the question, this problem is equivalent to the original one.

I'm by no means at all an expert in complexity theory (or anything), so I'd be interested to hear what some more experienced members of the community think of this argument. I've convinced myself that this argument is correct.

Convention: $\epsilon$-almost uniform will mean that we have fixed some $\epsilon < 1$ (for all instances), and we are considering a distributions $\nu_X$ such that $|| \nu_X - \text{Uniform}_{X} ||_{TV} < \epsilon$ over all instances $X$. (This definition could be weakened.)

There are two steps: 1) I'll recall a polytope easily derived from the paper that originally inspired this question, and point out that it's vertices are a natural correspondence with a set of combinatorial objects. 2) I'll show that uniformly sampling from those combinatorial objects is NP-hard.

In 3) I will carefully keep track of the computations in 2).

Notation: If $A \subset E$ is a subset, let $\chi_A$ denote the indicator function in $\mathbb{R}^E$. If $G$ is a graph, then $V(G)$ is the number of nodes, and $E(G)$ is the number of edges.

1) Let $W$ be some graph. Consider edge subgraphs of the form $C_1 \cup P \cup C_2$, where $C_1, C_2$ are non-empty, vertex disjoint simple cycles and $P$ is a non-empty path connecting them (but is otherwise vertex disjoint from both). For clarity, call such sets $C_1 \cup P \cup C_2$ "lassos." For $L = C_1 \cup P \cup C_2$ a lasso, denote $f_L := \chi_{C_1} + 2 \chi_P + \chi_{C_2}$.

For a graph $W$, let $SC(W)$ be the set of non-empty simple cycles, $L(W)$ be the set of lassos, and $SCL(W) = SC(W) \cup L(W)$.

Given a graph $G = (V,E)$, we can construct a polytope (with a polynomial size set of inequalities) whose vertices come with two types: $\lambda(C) \chi_C$ for $C \in SC(G)$ and $\lambda(C_1, P, C_2) ( f_L )$, where $L \in L(G)$.

Here $\lambda$ is some scalar which will be clear below (it can be bounded below by some fixed constant).

The existence of such a polytope is essentially the content of Lemma 2.1 in "On Cycle Cones and Polyhedra" by Coullard/Pulleyblank. This lemma describes a cone $\tilde{C}(G) \subset \mathbb{R}^E$ described by a set of $O(n^3)$ inequalities (with entries in $\{-1,0,1\}$). They prove that $\tilde{C}(G)$ is generated as a cone by the set $\{ \chi_C : C \in SC(G) \} \cup \{ f_L : L \in L(G) \}$.

I need one thing beyond what Coullard/Pulleyblank prove : Namely, that every vector of the form $\chi_C$, $C \in SC(G)$, or $f_L$, $L \in L(W)$, generates an extremal ray of $\tilde{C}(G)$.

It suffices to show that $\{ \chi_C : C \in SC(G) \} \cup \{ f_L : L \in L(G) \}$ is cone-independent, i.e no non-negative combination of some subset of these vectors suffices to write another one of them. Proof: (Main idea, look at the supports.) Suppose that we had a non-negative combination of such vectors to form $\chi_D$: $\chi_D = \sum \alpha_C \chi_C + \sum \beta_{C_1, P, C_2} ( \chi_{C_1} + 2 \chi_P + \chi_{C_2})$. By considering the support, the RHS could only use $C' \subset C$, or $C_1, P, C_2$ with $C_1 \cup P \cup C_2 \subset C$. We are forced to use only $\chi_C$. Suppose we had $\chi_{D_1} + 2 \chi_{Q} + \chi_{D_2} = \sum \alpha_C \chi_C + \sum \beta_{C_1, P, C_2} ( \chi_{C_1} + 2 \chi_P + \chi_{C_2})$. Again by considering the support, we would be forced to have all the $C \subset D_1 \cup Q \cup D_2$, hence $C \in \{D_1, D_2\}$. Similarly, we could only use $\chi_{D_1} + 2 \chi_Q + \chi_{D_2}$. So we would have an equation of the form $\chi_{D_1} + 2 \chi_{Q} + \chi_{D_2} = \alpha_1 \chi_{D_1} + \alpha_2 \chi_{D_2} + \beta ( \chi_{D_1} + 2 \chi_{Q} + \chi_{D_2})$. By independence of $\chi_{D_1}, \chi_Q, \chi_{D_2}$ (they are all edge disjoint), we conclude that $\beta = 1$, hence $\alpha_1 = \alpha_2 = 0$. QED

Hence: The extremal rays of $\tilde{C}(G)$ are in bijection with $SCL(G)$.

The polytope I'll use is obtained from their cone $\tilde{C}(G)$ by taking the vertex figure at the origin by intersecting with $H = \{ x : \sum_e x_e = 1 \}$. (This choice of hyperplane, or any similar one, means that we cannot maximize over the total number of edges -- see discussion in * below.)

Call this polytope $P(G)$. (This is not the polytope "$P(G)$" from the Coullard/Pulleyblank paper.)

The vertices of $P(G)$ are in bijective correspondence with the extremal rays of $\tilde{C}(G)$. (This is true for intersecting $H = \{ x : \sum_e x_e = 1 \}$ with any cone in the non-negative orthant. See ** below for a proof.)

Therefore, the vertices of $P(G)$ are in bijective correspondence with $SCL(G)$.

So $\lambda(C) = 1/ |C|$ and $\lambda( C_1, P, C_2) = \frac{1}{ |C_1| + |C_2| + 2|E(P)|}$.

Using this polytope $P(G)$, and the fact that $Vertices(P(G)) \cong SCL(G)$ are in bijective correspondence with $SCL(G)$, one could turn a polynomial time uniform sampler of the vertices of $P(G)$ into a machine that uniformly samples from $SCL(G)$. You just take a uniformly sampled vertex $x$, and output the set of edges $e$ such that $x(e) \geq \frac{1}{2|E|}$. This shows that the bijection $Vertices(P(G)) \cong SCL(G)$ is polynomial time computable.

The conclusion from this section is that if you are given a machine that takes $A$, $b$ and returns an $\epsilon$almost uniform sample from the vertices of $\{Ax = b, x \geq 0\}$, in time polynomial in $|A||b|$, then you get an algorithm that takes a graph $G$ and returns an $\epsilon$-almost uniform sample from $SCL(G)$ in time polynomial in $|G|$.

2) Let $H$ be some graph with two vertices $s,t$. We want to know if $H$ has a Hamiltonian s-t path. Such a problem is NP-complete. I'll show that an oracle for $\epsilon$-almost uniformly sampling from the vertices of $P(G)$ in 1) could be used to solve Hamiltonian s-t path on H. Because of the discussion in 1), if it is equivalent to assume we have an oracle for $\epsilon$-almost uniformly sampling from simple cycles and lassos of an arbitrary graph, since $P(G)$ and the bijection $Vertices(P(G)) \cong SCL(G)$ can be constructed in polynomial time in $G$.

First, add two lollipop graphs to $s$ and $t$ in $H$ to get a graph $H'$. Here's a link to a picture of this if it's unclear (correction: the $G$'s in the picture should be $H$'s.)

Now, $H'$ has a spanning lasso iff $H$ has a Hamiltonian s-t path. Moreover, $H'$ has no spanning simple cycles.

As in JVV 87' proposition 5.1, we replace edges of $H'$ with a chain of $d$ bigons, to get a graph $(H')_d$. We show that if there is a spanning lasso in $H'$, we can take $d$ (polynomially) large enough so that the probability that uniform element of $SCL( (H')_d)$ is a witness to the existence of some spanning lasso is very large.

There are some intricate details to keep track of, because of how some of these shapes can degenerate. To ward off the demons of imprecision and equivocation, I'll study this formally in the next section.

3) The correspondence works like this: If $e$ was replaced with $B_d(e)$ ($B_d$ is the chain of $d$ bigons), then if $X \in SCL( (H')_d)$, we define $\pi(X) = \{ e \in E( H' ) : X \cap B_d(e) \not = \emptyset\}$.

Given $X \in SCL( (H')_d)$, $\pi(X)$ might not always be a lasso or a simple cycle; we now consider these 'degenerate' cases, and classify and count them:

  1. $X$ may have been a bigon or a lasso contained entirely in some $B_d(e)$, in which case $| \pi(X) | = 1$. In this case we have $|\pi^{-1} ( \pi(X) )| \leq d + 2^{d+1}$.

  2. $X$ may have been a lasso such that one of its end loops was a bigon in some $B_d(e)$ -- to ease, communication let's call this situation 'a stolen bigon' (the bigon was stolen from $B_d(e)$). (A stolen bigon in $X$ doesn't always imply that $\pi(X)$ is degenerate, since the path $P$ could have almost looped around to itself, and stolen a bigon "at the last minute.")

    In the case that $\pi(X)$ degenerated, there are four shapes (up to homeomorphism) that it can have. To verify this, we observe:

    (Notation: If $Y$ is a graph, then $|H_0(Y)|$ is the number of components. $|H_1(Y)|$ is the dimension of the cycle space, i.e. the circuit rank. $leaves(Y)$ is the number of degree 1 nodes.)

    i) $|H_0( \pi(X))| = 1$: $\pi(X)$ is connected since, if $e, e' \in \pi(X)$, there is a path in $X$ from some something in $B_d(e)$ to something in $B_d(e')$, and this gives a path in $\pi(X)$.

    ii) $| \text{leaves}(\pi(X))| + |H_1( \pi(X))| \leq 2$. This is because each leaf or cycle in $\pi(X)$ uses a cycle of $X$. (The case of a leaf is clear. For the cycle, it either was a cycle in $X$, or it was obtained by a path that almost looped around to itself, but then ended with a stolen bigon, which uses a cycle of $X$.)

    The 4 shapes are the non-degenerate (not simple cycle or lasso) homeomorphism types of 1 dimensional, connected $CW$-complexes with $| \text{leaves}(\pi(X))| + |H_1( \pi(X))| \leq 2$:

    If there are two leaves, it's a path. If there is one leaf, there's either another one so it's a path, or there's a cycle on the other end. These two cases are treated in a) below.

    If there are no leaves, it might be circle, a lasso, or a circle with an interval glued to it by both endpoints. The first two cases are not degenerate (so we don't count them here, we count them below), and the second case is treated in b) below.

    a) $\pi(X)$ could be a (topologically) a lollipop, or $\pi(X)$ could be a path. We note that in both cases, $E( \pi(X) ) - V( \pi(X)) = H_1( \pi(X) ) - H_0( \pi(X)) \leq 0$. Therefore, $\pi(X)$ has at most $V(H') =: n$ edges.

    b) $\pi(X)$ could be a wedge of two simple cycles (meeting at a single point) , or, more generally, $\pi(X)$ could be a simple cycle with an edge with both endpoints glue onto it. There no such graphs that span $H'$ (because both of the lollipops need to be included, since the degree in these topological types is $\geq 2$ at every node, and this consumes both cycles in the lollipops we added to $H$ to get $H'$ , plus we must have the lollipop sticks to have $\pi(X)$ connected). Therefore, $\pi(X)$ has $< n$ vertices, so it has $\leq n$ edges, since $E - V = 1$ in these cases.

    Thus, above a particular $\pi(X)$, there are at most $(2n^4) (2^d)^n$ elements of $SCL( (H')_d)$ -- the coefficient $(2n^4) $ is to account for situations when there's some $e$ so that $X$ has stolen a bigon of $B_d(e)$ (see next paragraph).

    For each of these topological types, there are a limited number edges where a bigon can be stolen -- for example, for the path it must happen at the endpoints, or at it could happen in the case $b)$ on both sides of a vertex. We can generously bound these all by $2n^4$, since at most two edges $e \in E(H')$ can be the location of a stolen bigon, and the option to steal a bigon at an edge $e$ could at most double the number of configuraiton of $X \cap B_d(e)$, and there are at most $n^2$ edges. (More precision here just makes this more confusing, due to all the cases.)

We note that a spanning lasso in $H'$ has $|V(H')| + 1 =: n + 1$ edges, since $E(L) - V(L) = H_1(L) - H_0(L) = 1$ for any lasso $L$. Hence it has at least $(2^d)^{n+1}$ witnesses in $SCL( (H')_d )$. (Not exactly $(2^d)^{n+1}$), because of the stolen bigon multiplier, but this only makes it bigger.)

Now we count the non-degenerate cases: Every simple cycle of length $l$ has at most $2n^4 (2^d)^l$ elements in $SCL( (H')_d)$ that map down to it. Every non-spanning lasso with $l$ edges in $H'$ has at most $2n^4(2^d)^l$ elements that map down to it-- note that if it's non-spanning then $l \leq n$. (These coefficients again come from crudely bounding the count of where the bigon could be stolen.) Hence, like the degenerate cases, there most $2n^4 (2^d)^n$ elements in $SCL( (H')_d)$ corresponding to each one of these.

Hence, if $H'$ has a spanning lasso, then there $\geq (2^d)^{n+1}$ witnesses to it in $SCL( (H')_d)$. On the other hand, there are at most $( d + 2^{d+1}) |E(H')| + 2n^4 2^{n^2} (2^d)^n \leq 2^{dn} 4 n ^4 2^{n^2}$ elements of $SCL ( (H')_d)$ that do not provide a witness to a spanning lasso of $H'$. (Here $2^{n^2}$ is a very crude bound on $| \{ \pi(X) \subset 2^E : X \in SCL( (H')_d) \}|$.)

Let $A = \{ X \in SCL( (H')_d), \pi(X) \text{ is a spanning lasso of } H' \}$, and $B = SCL( (H')_d) \setminus A$. Then we have $|A| > 2^m |B|$ if $d = n^3 + 100 + m$. Thus, $\frac{A}{A + B} > \frac{A}{A + 2^{-m} A} = \frac{ 1}{1 + 2^{-m}}$.

In order to bound below the probability that an $\epsilon$-uniform sampler draws from $A$, we want $\frac{1}{1 + 2^{-m}} > 1/2 + \epsilon/2$. This is easily done by taking $m$ large enough (and this is independent of $d$ and $G$.)

Therefore, for any (constant) $\epsilon < 1$, by taking $d$ sufficiently large (say, $d > 100+ n^3 + g(\epsilon)$, where $g$ is the appropriate function), a uniform sample from $SCL( (H')_d)$ would provide a witness to a spanning lasso in $H'$ with probability $> .5 + \epsilon / 2$. This means that an $\epsilon$-almost uniform would provide a witness with probability $> 1/2 - \epsilon / 2 > \alpha > 0$, i.e. bounded below by some instance independent constant.

Therefore, given an algorithm $M$ that $\epsilon$-almost uniformly samples from the vertices of any given polytope $P$ in time polynomial in the matrix of inequalities defining $P$, we would obtain an algorithm in $RP$ to solve an $NP$-complete problem (whether $H$ had an $st$-path).

Conclusion: $\epsilon$-almost uniformly sampling from the vertices of a $\mathcal{H}$-polytope in time polynomial in the description is $NP$-hard for $\epsilon$ some fixed constant $< 1$, even if we assume that $A$ and $b$ only have entries from $\{-1,0,1\}$.

[*Note: the fact that we are intersecting with this particular hyperplane, or any similar one, means that we can't meaningfully maximize the function $\sum_e x_e$ ... so the reduction cannot be used to find a maximizer and construct a Hamiltonian path by linear programming -- phew! Instead, you can get at the Hamiltonian path by the probability concentration method. Which is good news for the soundness of this approach, because in this context linear functional optimization is easy -- it's just that we can't write the 'length' function as a linear functional on this polytope.

Here is a proof that it is impossible to extend the 'support' function as defined on the vertices to a linear functional. $X$ is a subset of edges of a graph. I've written the indicator as a linear combination of vertices of $P(G)$ in two ways. Recall that the lassos count the inner path twice.

Due to the rescaling (when we intersect with $H$), the coefficient in front of the decomposition of this shape into a sum of $3$ lassos is $8/2 = 4 $ (the eight is $3 + 2 + 3$), and the coefficient in front of the decomposition into 4 triangles is be $3$. When you put these coefficients, both linear combinations give the indicator of the shape $X$.

The support of each of those lassos is 7, and the support of each triangle is 3. If the support function could be extended linearly, it would lead to a contradiction, as we would have:

$4 ( 7 * 3) $ when computing with the Lassos and $3 *( 4 * 3)$ when computing with the triangles.

enter image description here


This addresses some of the concerns raised earlier. I think this line of reasoning also shows that maximizing the size of the support over the vertices of a polytope is NP-hard.]

[**Let $C$ be a cone with $ExtremalRays(C) = \{ \{ \lambda f_i : \lambda \in \mathbb{R}_{\geq 0} \} : i = 1 , \ldots, n \}$ where $f_i \in \mathbb{R}^E$, with all $f_i \geq 0$. Let $H = \{ x : \sum_e x(e) \}$, and $S(f) = \sum_e f(e)$. Let $P = C \cap H$. Then $Vertices(P) = \{ \frac{ f_i}{S(f_i)} : i = 1, \ldots, n \}$.

Proof: It is an equivalent hypothesis to say that $C$ has a minimal generating set $\{f_1, \ldots, f_n\}$, i.e. that this set generates the cone and is cone-independent. The set of points $\{\frac{ f_i}{S(f_i)} : i = 1, \ldots, n\}$ is in convex position -- if we had a convex dependence, then using that $S(f_i) > 0$, we would obtain a cone dependence. Moreover, $S(\frac{ f_i}{S(f_i)}) = 1$, so $\frac{ f_i}{S(f_i)} \in P$. Let $u \in P$ be arbitrary. Then we have $u = \sum \alpha_i \frac{f_i}{S(f_i)}$ in $C$. But in this case, $1 = S(u) = \sum \alpha_i$, so we get that $P \subset Conv( \{\frac{ f_i}{S(f_i)} : i = 1, \ldots, n\} )$. Thus, $Vertices(P) = \{\frac{ f_i}{S(f_i)} : i = 1, \ldots, n\}$. ]

  • $\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.