1
$\begingroup$

Suppose we have a linear programming about the vertex packing of a hypergraph G=(V,E), with size $n = \sum_{e \in E}|e|$. We introduce a variable $x_v$ for each vertex $v \in V$.

$$\max \sum_{v} x_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$ $$s.t. \sum_{v: v \in e} x_v \le 1, \ \forall e \in E$$ $$\ x_v \ge 0, \ \forall v \in V$$

Is it always possible to find an optimal solution such that the minimum non-zero variable has value at least $c \cdot 1/n$ for some constant $c$? (If representing the contraints as $\mathbf{Ax} \le \mathbf{1}$, there are $n$ entries as $1$ in $\mathbf{A}$ with remaining entries as $0$.)

$\endgroup$
4
$\begingroup$

No, it is not always possible. The illustration below shows an example in which the smallest non-zero value must be $1/2^{\Omega(n)}$.

enter image description here

The example is shown in the top of the illustration. Round nodes are vertices; square nodes are hyperedges, each with connections to its (two or three) vertices. Each vertex $v$ is labeled with its weight $x_v$ in the optimal LP solution, which is essentially unique.

In general, the hypergraph consists of the first three vertices (labeled $1/2$) and their three edges to their left, followed by $N$ copies of the gadget shown in the middle (vertically). The "inputs" to the gadget are the three vertices labeled $1/x$. The "outputs" are the three vertices labeled $1/2x$; these are also the inputs for the next copy of the gadget (if any). Above $N=3$, but in general $N$ is arbitrarily large. The sum of the hyperedge sizes is $n = \Theta(N)$, and the given solution has a non-zero weight of value $\Theta(1/2^N) = 1/2^{\Theta(n)}$. This solution is obtained greedily by assigning weights maximally, from left to right.

To answer the question in the post, we will show that the given solution is the unique optimal solution. The bottom part of the illustration above is for the proof (given below).

Lemma 1. The given LP solution is the unique optimum.

Proof sketch. Let $x$ be the LP solution given in the figure. By inspection $x$ is feasible. First we'll argue that $x$ is optimal, by giving a dual solution that achieves the same LP objective. The dual LP is "covering vertices by edges": $$\min \sum_e y_e ~:~ y_e \ge 0;~~(\forall v)~\sum_{e \ni v} y_e \ge 1.$$

We use the dual solution illustrated in the bottom part of the figure above, in green. We give each edge weight equal to the green label at the bottom of its column. This solution is obtained greedily, by assigning weights minimally from right to left. By inspection, at least for the example, the dual solution is feasible and has the same cost as the primal solution $x$. In general, by calculation, the cost achieved by the given primal solution $x$ is $$3[1/2 + N + 1/2^{N+2}],$$ while the cost achieved by the given dual solution is the same: $$3[(1/2 - 1/2^{N+2}) + 1/2^{N+1} + N].$$ Therefore the primal and dual solutions are optimal.

To finish we argue that the optimal primal solution is unique. Let $x^*$ be any optimal primal solution. By complimentary slackness and the fact that all values are non-zero in the optimal dual solution, $x^*$ must make all primal constraints tight.

Let $x^*_1, x^*_2, x^*_3$ be the variables of the first three vertices, given weight $1/2$ by $x$. That the first three constraints are tight implies $x^*_1 + x^*_2 = 1$ and $x^*_1 + x^*_3 = 1$ and $x^*_2 + x^*_3 = 1$, which implies that $x^*_1 = x^*_2 = x^*_3 = 1/2$, the same as in $x$.

Given that, the same reasoning implies that $x^*$ gives each of the next three vertices weight $1/4$, also the same as in $x$. Given that, likewise, $x^*$ must give each of the next three vertices weight $3/4$, the same as in $x$. Continuing this reasoning inductively, $x$ and $x^*$ must be identical. $~~~\Box$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your reply! But here n is the total occurrence of vertices in the graph, i.e., $n = \sum_{e \in E} |e|$. In this family of examples, $n = \Theta(k^2)$. $\endgroup$ – Xiao Apr 29 at 1:08
  • 1
    $\begingroup$ Oh, right, I was assuming $n$ was the number of vertices in the graph. I've rewritten the answer completely to show the desired bound. I think it's interesting --- this example shows that to represent an optimal solution requires at least $\Theta(n)$ bits of precision. I guess for large $n$ most practical solvers won't be able to get the exact optimum. $\endgroup$ – Neal Young Apr 29 at 21:16
  • $\begingroup$ Nice! It is exactly the counter example for ruling out the possibility of bounding the smallest non-negative value by $\Omega(1/n)$. Just a small correction for exchanging 1/4 and 3/4 in the optimal edge cover. $\endgroup$ – Xiao Apr 30 at 15:18
  • $\begingroup$ I corrected the 1/4 (good catch). Once you've checked that the answer is correct, can you please mark it as correct by checking the check box to the left at the top of the answer? That's how stack exchange keeps track of what questions have been answered. Thanks. $\endgroup$ – Neal Young Apr 30 at 15:29

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.